Algorithm/BOJ
-
[BOJ] 계란으로 계란치기Algorithm/BOJ 2021. 1. 20. 16:27
[16987] 계란으로 계란치기 www.acmicpc.net/problem/16987 Solution N개의 각각의 계란이 한 번씩만 다른 계란을 칠 수 있을 때 깨지는 계란의 최대 갯수를 구하는 문제 처음에는 문제를 제대로 이해하지 못해서 i번째 계란은 i+1 이상의 순서의 계란만 깰 수 있다고 생각했다. 백트래킹으로 계란의 내구도(durability)를 복구하면서 모든 경우를 탐색해 답을 구할 수 있었다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 ..
-
[BOJ] 청소년 상어Algorithm/BOJ 2021. 1. 19. 20:20
[19236] 청소년 상어 www.acmicpc.net/problem/19236 Solution 백트래킹 문제인데 중간에 되돌려 놔야할 조건을 놓쳐서 또 엄청난 삽질을 했다.. 문제의 알고리즘의 큰 흐름은 다음과 같다 (1) 상어가 (sx, sy) 자리의 물고기를 먹는다 & 상어는 먹은 물고기의 방향을 가진다. (2) 각자 번호와 방향을 가진 물고기들이 작은 번호 부터 순서대로 자신의 방향으로 이동한다. (3) 상어는 자신의 방향으로 갈 수 있는 칸으로 한 번 이동할 수 있다. => dfs() 호출 (1) - (3) 과정이 반복되고, answer 변수에 상어가 먹을 수 있는 물고기 번호의 합의 최대값을 저장한다. 3번 과정에서 어떤 칸으로 가야 answer의 최댓값을 구할 수 있는지 알 수 없기 때문에 ..
-
[BOJ] 아기상어Algorithm/BOJ 2021. 1. 12. 19:09
[16236] 아기 상어 www.acmicpc.net/problem/16236 Solution 문제 조건 제대로 안 읽고 풀었다가 디버깅의 늪에 빠져벌임.. 문제 제대로 보자 1. 현재 상어 위치를 기준으로 BFS를 돌리고 상어가 먹을 수 있는 (=자신의 크기보다 작은) 물고기를 모두 fishes 리스트에 넣는다. 2. fishes 리스트를 문제 조건에 따라 가장 가까운 > x 좌표 > y좌표 기준으로 정렬하고 첫번째 물고기를 먹는다. 위 두 과정을 반복하다가 fishes 리스트의 길이가 0일 때, 즉 더이상 먹을 수 있는 물고기가 없을 때 while문을 종료한다. BFS 메서드에서 상어와 물고기 사이의 거리를 visited 배열에 저장한다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13..
-
[BOJ] 문제집Algorithm/BOJ 2020. 11. 30. 15:00
[1766] 문제집 www.acmicpc.net/problem/1766 Solution N개의 문제를 모두 풀어야하는데, 문제 풀이 순서에 있어 두 가지 조건을 고려해야한다. 첫째, 숫자가 작은 문제부터 풀어야한다. 둘째, 먼저 풀어야하는 길잡이 문제부터 풀어야 한다. 일반적인 위상정렬에서 q를 오름차순 pq로 바꾸어 쉽게 풀 수 있었다. 알고리즘 분류가 우선순위 큐로 되어있길래 풀었는데, 위상정렬 문제였다. 덕분에 위상정렬 공부까지 했음. 4ngeunlee.tistory.com/365 [Algorithm] 위상 정렬 위상 정렬 방향이 있는 그래프의 순서 정렬 위상 정렬이 가능하려면 DAG(Directed Acycle Graph, 방향성이 있으며 사이클이 없는 그래프)이여야 한다. 위상 정렬을 구현하는 ..
-
[BOJ] 행성 터널Algorithm/BOJ 2020. 11. 28. 17:20
[2887] 행성 터널 www.acmicpc.net/problem/2887 Solution 행성들을 잇는 최소 간선 트리를 만드는 간단한 문제이다. 처음에는 행성을 이을 수 있는 모든 간선을 미리 구해서 푸는 방식으로 접근했는 데 메모리 초과로 틀렸다. int x, y, z -> 12byte이고, 행성 개수가 최대 10만개이기 때문에 (10만 * 10만 / 2) = 약 50억으로 12byte * 50억이라하면 메모리가 초과될 수 밖에 없었다. 문제를 다시 한 번 살펴보면 행성의 x, y, z 좌표를 각각 비교해서 최소 비용을 구하는 것이므로 모든 행성간의 비용을 계산할 필요 없이 좌표 별로 오름차순으로 정렬한 뒤 바로 옆 행성만 비교하면 된다. 예를들어 행성 A, B, C의 x좌표를 기준으로 정렬한 결과..
-
[BOJ] 진우의 민트초코우유Algorithm/BOJ 2020. 11. 27. 17:12
[20208] 진우의 민트초코우유 www.acmicpc.net/problem/20208 Solution 집 - 민초s - 집 까지 체력을 유지하면서 돌아올 수 있는 경우 중 최대 민초집 수를 구하는 문제 permutation으로 민초집 수를 늘리면서 & 순서를 달리한 경로를 pick 배열에 저장했고, 체력을 유지한 채 집까지 돌아올 수 있는 최대 민초집 수를 answer에 저장하여 풀었다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61..
-
[BOJ] 인구 이동Algorithm/BOJ 2020. 10. 28. 14:16
[16234] 인구 이동 www.acmicpc.net/problem/16234 Solution 문제에 명시된 국경선을 map[][]에서 1*1 크기의 칸으로 정의하였고, 인접한 국가와의 인구차가 범위 안에 있을 경우에 0으로 표시했다. 모든 국경선에 표시한 뒤 bfs 함수로 연합이 되는 국가의 인구수의 합과 평균을 구해 map[][]에 표시했다. 조건을 만족하는 국경선이 없을 때 까지 while문은 반복된다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 ..
-
[BOJ] 택배Algorithm/BOJ 2020. 10. 24. 01:56
[1719] 택배 www.acmicpc.net/problem/1719 Solution 모든 정점에 대해 다익스트라 함수를 실행하여 update된 prev[]의 정보를 활용해서 첫 번째로 경유하는 정점을 찾았다. 돌아서면 까먹는 다익스트라 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90..