전체 글
BOJ 1445 · 일요일 아침의 데이트
알고리즘 분류 : 다익스트라 S부터 출발해서 F에 도착할 때까지, 쓰레기를 최소로 지나면서, 쓰레기의 옆을 최소로 지나는 방법을 찾는 문제다. 두 가지의 우선순위 조건 때문에, 다익스트라 알고리즘을 사용하는 것이 좋다. 다익스트라를 이용하기 위해, 입력으로 주어지는 문자열 맵에 상응하는 인접 행렬을 만든다.쓰레기가 있는 칸 'g'는 2500으로 두고, g에 인접한 4칸은 1로 둔다. 나머지 칸은 0으로 둔다.맵이 최대 50*50으로 주어지기 때문에, 쓰레기 칸('g')에 넉넉하게 큰 값을 주는 것이 좋다. 예를 들어, 쓰레기 칸에 3을 주면 쓰레기 옆 칸을 3번 이동한 것과 구분할 수 없기 때문이다.정답은 dist 배열에 있으며, 2500으로 나눈 몫이 쓰레기를 지난 횟수이며, 2500으로 나눈 나머지가..
BOJ 2665 · 미로만들기
알고리즘 분류 : BFS 미로를 이동하면서 검은 방을 흰 방으로 만드는 최소 횟수를 구해야 하는 문제다. 덱(Deque)과 BFS를 이용하여 해결할 수 있다. 이 문제는 BOJ 1261 '알고스팟' 문제와 유사하다. 흰 방을 이동할 때는 덱의 뒤에 넣고, 이동 거리는 이전과 같게 한다.검은 방을 이동할 때는 덱의 앞에 넣고, 이동 거리를 +1 업데이트한다.덱에서 이동 좌표를 꺼낼 때, 덱의 뒤에서부터 꺼낸다. C++ 소스코드 #include #include using namespace std; struct maze { int x, y; }; int n; int a[50][50]; int dist[50][50]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}..
BOJ 2529 · 부등호
알고리즘 분류 : 백트래킹 기본적으로 재귀 함수를 이용하여 브루트 포스로 구현할 수 있다. 재귀 함수를 호출하기 전에 부등호 체크를 하는 방식으로 백트래킹을 하여 시간을 단축할 수 있다. 하나의 숫자를 구하기 위해서 입력으로 주어진 길이(N)+1 만큼 재귀 함수를 호출해야 한다. 올바른 부등식은 숫자 개수가 부등호 개수보다 1개 더 많다.재귀 함수 종료 조건 : 숫자 개수(길이) == N+1수를 중복하여 사용할 수 없으므로, check 배열을 별도로 만들어서 사용 여부를 확인해야 한다.재귀 함수를 호출하기 전에, 다음 숫자가 부등식에 맞는지 살펴봐야 한다.예를 들어, 주어진 부등호가 > 라면, 0 2 > 1은 가능하다. 하지만 3 1 > 0은 불가능하다. 이런 경우, 3 < ..
BOJ 14889 · 스타트와 링크
알고리즘 분류 : 브루트 포스 두 팀으로 나눠서 두 팀의 능력치 차에 대한 최솟값을 구하는 문제다. 재귀 함수를 이용하여 구현할 수 있다. 재귀 함수는 두 팀으로 나누는 과정에 이용한다.팀을 구분하는 체크 배열 c를 둔다. 팀의 구분은 true와 false로 한다.재귀 함수 종료 조건은 인덱스가 N을 벗어났을 때이거나 팀 인원이 N/2 명이 되었을 때이다.팀 능력치의 총합은 N^2 for 문으로 구한다.Aij 는 i와 j가 같은 팀일 때의 능력치이며, Aij와 Aji는 값이 다를 수 있으므로 둘 다 더해야 한다.스타트 팀은 c[i] == true AND c[j] == true 이며, 링크 팀은 c[i] == false AND c[j] == false 이다. C++ 소스코드 #include #include..
BOJ 1748 · 수 이어 쓰기 1
알고리즘 분류 : 구현 입력으로 N이 주어질 때, 1부터 N까지 수를 이어 붙여서 나온 수의 길이를 구하는 문제다. 자릿수로 나눠서 생각하면 구현이 쉽다.N이 주어졌을 때, 1의 자리가 있는 수는 1부터 N까지이다. 따라서 1의 자리가 있는 수는 (N-1+1)이다.10의 자리가 있는 수는 10부터 N까지이다. 이를 구하면, (N-10+1) 이다.100의 자리가 있는 수는 100부터 N까지이다. 이를 구하면, (N-100+1) 이다.위의 과정을 N의 자릿수 만큼 반복한다. C++ 소스코드 #include int main() { int n; scanf("%d", &n); int ans = 0, i = 1; while (i
BOJ 13913 · 숨바꼭질 4
알고리즘 분류 : BFS N부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. BOJ 1697번 '숨바꼭질' 문제를 변형한 문제다. 최소 시간과 이동한 방법을 출력해야 한다. 이동한 방법은 이동 경로를 역순으로 추적하면 된다. 최소 시간은 이전 문제를 참고.이동 경로를 저장할 path 배열을 만든다.path[다음 좌표] = (현재 좌표) 방식으로 path 배열을 저장한다.K에 도착하면, path 배열을 K부터 시작해서 N까지 역순으로 출력한다. C++ 소스코드 #include #include #include using namespace std; const int MAX = 1e6; int n, k; int dist[MAX+1], path[MAX+1]; void bfs() { queue q; q..
BOJ 13549 · 숨바꼭질 3
알고리즘 분류 : BFS N부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. BOJ 1697 '숨바꼭질' 문제를 변형한 문제다. 최소 시간을 구해야 하는데, 이동 시간에 차이가 있다. 순간 이동(2*X)은 0초 걸리고, X+1, X-1 이동은 1초 걸린다. 0초와 1초 케이스로 나뉘므로, 덱(deque)을 이용하면 좋다.순간 이동(2*X)이 더 빠른 시간(0초)으로 이동할 수 있으므로, X+1, X-1 이동보다 우선순위를 가진다. 순간 이동을 할 경우, 다음 이동 좌표를 덱의 뒤에 넣는다.X+1, X-1 이동을 할 경우, 다음 이동 좌표를 덱의 앞에 넣는다.이동 좌표를 덱에서 꺼낼 때, 덱의 뒤에서부터 pop하면 순간 이동을 먼저 처리할 수 있다. C++ 소스코드 #include #inclu..
BOJ 12851 · 숨바꼭질 2
알고리즘 분류 : BFS N부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. BOJ 1697번 '숨바꼭질'에서 변형된 문제다. 최소 시간과 그 경우의 수를 구해야 한다. 최소 시간은 이전 문제를 참고한다.x에서 nx에 도착하는 경우의 수는 여러 가지 일 수 있으므로, dist[x]에 아직 방문하지 않은 상태(dist[x]==0)이거나, 이미 방문했더라도 이동 거리가 같다면(dist[nx] == dist[x]+1) 큐에 다음 좌표를 집어넣는다.경우의 수는 k에 도착할 때마다 카운트를 1 증가시킨다. C++ 소스코드 #include #include using namespace std; const int MAX = 1e6; int n, k; int dist[MAX+1]; void bfs() { q..