Tech.it

PS Featured

[PS] BOJ 2110 / 공유기 설치

문제 링크: https://www.acmicpc.net/problem/2110 결정 문제를 잘 정의하면 어렵지 않게 풀 수 있습니다. 풀이 매개변수 탐색 문제의 내용을 요약해보면, $N$개의 집 중에서 최소 $C$개의 공유기를 놓을 수 있도록 하는 인접한 두 공유기 사이의 거리의 최대값을 구하면 됩니다. 구해야 하는 것은 '인접한 두 공유기

PS Featured

[PS] BOJ 1948 / 임계 경로

문제 링크: https://www.acmicpc.net/problem/1948 주어진 방향 그래프에서의 최장 경로를 찾고, 그 경로를 구성하는 간선의 개수를 세는 문제입니다. 풀이 최장 경로 찾기 보통의 그래프 탐색 문제는 최단 경로를 찾지만, 이번 문제에서는 가중치의 합이 가장 큰 경로를 찾아야 합니다. 이를 최장 경로라고 부르겠습니다. 먼저 입력 데이터로 그래프를 구성해야

PS Featured

[PS] BOJ 27297 / 맨해튼에서의 모임

문제 링크: https://www.acmicpc.net/problem/27297 정렬을 활용해 중앙값을 찾는 문제입니다. 풀이 맨해튼 거리 N차원의 두 점 $A = (A_1, A_2, \cdots, A_N)$와 $B = (B_1, B_2, \cdots, B_N)$ 사이의 맨해튼 거리 $d_AB$는 다음과 같습니다. $d_{AB} = \sum_{i = 1}^{N}

Life Featured

[월말정산] 25년 10월의 이야기

10월 회고입니다. 무엇을 했나요? 0) 여유로운 한 달이었습니다. 훈련도 끝났고, 남은 전투 휴무와 추석 연휴가 있어 굉장히 오랫동안 쉴 수 있었습니다. 월말부터는 말년 휴가가 시작해, 이제 군생활도 끝이 다가오네요. 1) 1일 1백준을 실천하고 있습니다. 이제는 매 월말 정산마다 반복해서 적고 있는 내용입니다. 10월 31일 기준으로는 스트릭이 149일이나 되었네요! (작성일 기준으로는

PS Featured

[PS] BOJ 13911 / 집 구하기

문제 링크: https://www.acmicpc.net/problem/13911 다익스트라 알고리즘을 활용해 최단 거리를 구하는 문제입니다. 다만, 약간의 테크닉을 요구합니다. 풀이 다익스트라 알고리즘 다익스트라는 주어진 그래프에서 두 정점 사이의 최단 거리를 구하는 알고리즘입니다. 임의의 한 정점에서 시작해, 가장 거리가 가까운 정점을 찾아가며 전체 정점의 최단 거리를 갱신하는 방식으로 동작합니다. 자세한 설명은

PS Featured

[PS] BOJ 1953 / 팀배분

문제 링크: https://www.acmicpc.net/problem/1953 이분 그래프를 활용하는 문제입니다. 풀이 이분 그래프란? 서로 인접한 두 정점을 다른 색상으로 칠할 때, 전체 그래프의 모든 정점이 두 가지 색으로 표현되는 그래프를 말합니다. 그래프 탐색을 통해 그래프의 각 정점을 2가지 색상으로 칠해 주어진 그래프가 이분 그래프인지 아닌지를 알 수 있습니다.

PS

[PS] BOJ 1707 / 이분 그래프

문제 링크: https://www.acmicpc.net/problem/1707 주어진 그래프가 이분 그래프인지 아닌지를 판단하는 문제입니다. 이분 그래프의 개념에 대해 이해하기에 좋은 문제입니다. 풀이 이분 그래프란? 서로 인접한 두 정점을 다른 색상으로 칠할 때, 전체 그래프의 모든 정점이 두 가지 색으로 표현되는 그래프를 말합니다. 주어진 그래프가 이분 그래프인지 판단하기 이 그래프가

PS

[PS] BOJ 6603 / 로또

문제 링크: https://www.acmicpc.net/problem/6603 백트래킹의 기본적인 구조만 이해한다면 쉽게 풀 수 있습니다. 풀이 $K$개의 원소를 가지는 집합 $S$에서, 6개의 숫자를 오름차순으로 고르는 모든 경우를 출력하는 문제입니다. ($6 < K < 13$으로 크지 않습니다.) 입력에서 집합 $S$의 원소는 항상 오름차순으로 주어지기 때문에, 항상

PS

[PS] BOJ 8905 / 리트

문제 링크: https://www.acmicpc.net/problem/8905 재밌게 풀었던 백트래킹 문제입니다. 풀이 리트 변환 규칙 문제에서 언급한 리트 표기의 규칙은 다음과 같습니다. * 각 알파벳을 리트로 나타낼 때, 최대 $K$개의 문자로 나타낼 수 있습니다. * 한 문자를 리트로 바꾸는 방법은 한 가지입니다. * d를 앞서 [)로 바꿨다면, 다른 d를 |>로

PS

[PS] BOJ 25711 / 인경산

문제 링크: https://www.acmicpc.net/problem/25711 누적 합을 어떻게 활용할 지 잘 생각해야 합니다. 풀이 누적 합 계산하기 문제에서는 $Q$개의 질문이 주어지고, 각 질문마다 $i$번 산장에서 출발해 $j$번 산장에 도달하기 위해 소모되는 체력을 계산해야 합니다. 매 질문마다 거리를 직접 계산하는 방식으로는 질문을 처리하는 과정의 시간

PS

[PS] BOJ 17383 / 옥토끼는 통신교육을 풀어라!!

문제 링크: https://www.acmicpc.net/problem/17383 아이디어만 떠올리면 구현은 어렵지 않은 문제입니다. 풀이 최적화 문제 생각해보기 문제를 처음 보면 각 문제를 어떻게 배치해 풀어야 하는지 고민이 되지만, 문제가 아닌 시간 간격에 초점을 둬봅시다. tncks0121는 항상 각 문제가 풀리는 시간의 차이에만 신경을 씁니다. 문제를 어떻게 푸는지는 상관 없이, 한

PS

[PS] BOJ 2512 / 예산

문제 링크: https://www.acmicpc.net/problem/2512 오랜만에 푸는 매개변수 탐색 문제입니다. 풀이 이분탐색과 매개변수 탐색 돌아보기 1) 이분 탐색은 무엇인가? 이분 탐색은 정렬된 배열 안에서 $O(\log N)$의 시간 복잡도로 배열 안에서 값을 찾는 방법입니다. 2) 결정 문제와 최적화 문제 이분 탐색을 이용해 풀 수 있는 문제

PS

[PS] BOJ 21772 / 가희의 고구마 먹방

문제 링크: https://www.acmicpc.net/problem/21772 백트래킹으로 고구마를 최대한 많이 먹어봅시다. 풀이 백트래킹 가희는 1개의 시작점에서 시작해, 주어진 격자 그래프를 탐색하며 $T$초 이내 ($1 \leq T \leq 10$)에 고구마를 최대한 많이 먹으려고 합니다. $T$가 작은 수 이므로, 백트래킹을 통해 가능한 경우를 모두 찾아서 최댓값을 구하면

PS

[PS] BOJ 1613 / 역사

문제 링크: https://www.acmicpc.net/problem/1613 플로이드-워셜을 통해 모든 정점들 사이의 연결 관계를 파악하는 문제입니다. 풀이 플로이드-워셜 오랜만에 푸는 플로이드-워셜 문제인 만큼, 개념을 다시 정리해 봅시다. 플로이드-워셜은 모든 정점에서 다른 모든 정점으로의 최단 경로를 계산하는 알고리즘입니다. 3중 반복문으로 동작하기 때문에, $V$개의 정점에 대해, 시간 복잡도는 $O(V^

PS

[PS] BOJ 14938 / 서강그라운드

문제 링크: https://www.acmicpc.net/problem/14938 다익스트라 문제입니다. 풀이 다익스트라 오랜만에 푸는 다익스트라 문제인 만큼, 다익스트라 알고리즘의 개념을 다시 정리해 봅시다. 다익스트라 알고리즘은 정점을 기준으로 최단 경로를 찾는 알고리즘이며, 한 개의 정점에서 다른 모든 정점으로의 최단 경로를 계산합니다. 아래는 우선순위 큐 기반의 다익스트라 구현입니다. from heapq import heappop,

PS

[PS] BOJ / N과 M

N과 M 문제 시리즈의 풀이를 모아왔습니다. N과 M (6) / BOJ 15655 * N개의 자연수 중에서 M개를 고른 수열 * 고른 수열은 오름차순 * 주어지는 $N$개의 자연수는 모두 서로 다른 수 * 같은 수 중복 사용 X 고른 수열이 오름차순으로 나오기 위해서는 입력 받은 수를 정렬한 뒤 순차적으로 백트래킹을 통해 수열을 구성하면 된다. 또,

PS

[PS] BOJ 1759 / 암호

문제 링크: https://www.acmicpc.net/problem/1759 백트래킹 문제입니다. 백트래킹을 거쳐 완성한 암호가 답이 될지 안될지를 잘 판단해야 합니다. 풀이 올바른 암호의 조건 문제에서 요구하는 올바른 암호의 조건은 다음과 같습니다. * 암호의 길이는 $L$입니다. * 암호는 미리 주어진 $C$개의 알파벳으로만 구성됩니다. * 암호는 반드시 사전순으로 증가하는 순서로 구성되어야 합니다. * abc는

PS

[PS] BOJ 4485 / 녹색 옷 입은 애가 젤다지?

문제 링크: https://www.acmicpc.net/problem/4485 그래프 탐색 문제입니다. 풀이 우선순위 큐 기반의 BFS 문제 내용을 요약하면, 결국 최소 비용으로 $(0, 0)$에서 $(N-1, N-1)$까지 갈 수 있는 경로를 찾는 문제입니다. 지도의 크기는 최대 $125 \times 125$이고, 격자 그래프 상의 문제이므로, 굳이 간선 정보를 만들어 다익스트라로

PS

[PS] BOJ 1865 / 웜홀

문제 링크: https://www.acmicpc.net/problem/1865 벨만-포드 알고리즘을 활용하는 문제입니다. 풀이 벨만-포드 이해하기 벨만-포드 알고리즘의 기본적인 설명은 이전 글을 참고해주세요. 벨만-포드 알고리즘은 다익스트라 알고리즘과 같이 한 개의 정점에서 다른 모든 정점으로의 최단 경로를 계산합니다. 따라서, 출발점에서 도달할 수 없는 정점들에 대해선 경로가 계산되지 않으며, 이러한 정점들을 거치는 음의

PS

[PS] BOJ 10216 / Count Circle Groups

문제 링크: https://www.acmicpc.net/problem/10216 분리 집합을 활용하는 문제입니다. 풀이 분리 집합 활용해 그룹 합치기 각 부대의 연결 관계를 파악하며, 만약 두 부대의 통신 영역이 닿거나 겹칠 경우 분리 집합을 사용해 같은 집합으로 합쳐주면 됩니다. 두 부대가 연결되는 경우 각 부대는 중심 좌표 $(x, y)$와 통신

PS

[PS] BOJ 1393 / 음하철도 구구팔

문제 링크: https://www.acmicpc.net/problem/1393 옛날 학생 시절에 배운 "수선의 발" 개념을 사용하면 어렵지 않게 계산할 수 있습니다. 풀이 수선의 발? 어느 한 직선과 직선 위에 있지 않은 점 P가 있을 때, 점 P에서 직선 위에 수직이 되도록 내린 점을 수선의 발이라고 합니다. 여러 방법으로

PS

[PS] BOJ 30508 / 고인물이싫어

문제 링크: https://www.acmicpc.net/problem/30508 그래프 탐색과 누적합을 모두 활용하는 문제입니다. 풀이를 떠올리면 구현은 어렵지 않습니다. 풀이 단계별로 생각하기 1. 하수구에서부터 BFS 진행해서 전체 타일에 물이 빠진 칸 파악하기 2. 누적합 계산해서 (r, c) 지점까지 물이 빠진 칸의 수 세기 3. H x M 크기로 모두 물이

PS

[PS] BOJ 4195 / 친구 네트워크

문제 링크: https://www.acmicpc.net/problem/4195 분리 집합을 활용해 풀 수 있는 문제입니다. 단, 두 문자열 간의 연결 관계가 주어지므로 맵을 활용해야 합니다. 풀이 분리 집합 기반의 Union-Find 알고리즘 분리 집합은 흔히 다익스트라 구현에서 사이클 여부를 판단하기 위해 사용하는 자료구조로, 여러 원소들을 단일 집합으로 합치고, 임의의 두 원소가

PS

[PS] BOJ 7562 / 나이트의 이동

문제 링크: https://www.acmicpc.net/problem/7562 격자 그래프 상에서의 그래프 탐색 문제입니다. 풀이 격자 그래프 상의 그래프 탐색 이제는 익숙한 문제 유형입니다. DFS 또는 BFS를 사용해, 2차원 배열 내의 각 좌표의 방문 여부를 기록하며 목적지를 찾아가면 됩니다. 다만, 상하좌우로의 단순한 이동이 아닌 나이트의 이동이므로 다음 좌표를 적절히 계산해주면

PS

[PS] BOJ 11657 / 타임머신

문제 링크: https://www.acmicpc.net/problem/11657 최단 경로를 찾는 문제입니다. 단, 간선의 가중치가 음수로도 주어집니다. 풀이 최단 경로? 1개의 정점에서 다른 모든 정점으로의 최단 거리를 계산해야 합니다. 다익스트라를 먼저 떠올렸지만, 다익스트라 알고리즘은 음의 간선을 포함하는 경우 최단 경로를 찾을 수 없습니다. 음의 간선을 포함하는 그래프에서 최단 경로를 구하기