코딩테스트 연습/Baekjoon (78) 썸네일형 리스트형 [Baekjoon] 백준 1753번: 최단경로 (c++) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. proirty queue를 가중치를 작은 순(오름차순) 정렬하도록 선언 2. pq의 첫번째 요소인 현재 노드를 u로, 두 번째 요소인 현재 가중치를 w로 설정하고 3. 현재 노드 u에 대하여 첫번째 요소 V, 두번째 요소 W 4. w + W 가 현재 dist[V]보다 작으면, dist[V] = w+W로 갱신한다. 5. pq에 다시 V를 기준으로 현재노드,.. [Baekjoon] 백준 16953번: A → B (c++) https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net A → B 로 갈때, A는 곱하기 2를 하는 방법과, 마지막 자리에 1를 붙이는 방법이 있다. A를 기준으로 B를 만들면, 곱하기2를 하는방법과 뒤에 1를 붙이는 방법으로 가지수가 나누어져서 최솟값을 구하기 위해서는 많은 경우를 생각해야 하기 때문에, B를 기준으로 A를 만드는 방법으로 진행했다. 1. B의 끝자리가 1이면, 끝자리 1을 제거함 2. 끝자리가 1이 아닌 짝수라면, B/2를 B에다가 저장함 3. 1번이나 2번 중 하나가 실행되었을 때, cnt++로 횟수를 세줌 4. 1~3번을 A == B일때까지 반복 후 c.. [Baekjoon] 백준 12871번: 무한 문자열 (c++) https://www.acmicpc.net/problem/12871 12871번: 무한 문자열 첫째 줄에 s, 둘째 줄에 t가 주어진다. 두 문자열 s와 t의 길이는 50보다 작거나 같은 자연수이고, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 최소공배수를 구하는 방법으로 문제를 풀었다. 1. a와 b의 길이에 대한 최소공배수를 구해서, 2. A에다가 a의부분문자열을 이어준 합을 저장하고, 그 합의 길이가 최소공배수에 도달할때 까지 반복한다. 3. B에다가 b의부분문자열을 이어준 합을 저장하고, 그 합의 길이가 최소공배수에 도달할때 까지 반복한다. 4. A와 B가 같으면 1출력, 다르면 0 출력 ex) aa aaa 의 경우, aaa와 aaaaa의 길이에 대한 최소공배수 = 15 , 문자.. [Baekjoon] 백준 14502번: 연구소 (c++) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net SSAFY 코테 준비 겸 한번 풀어봤는데,, 정답률 높아서 쉽게풀줄 알았지만,,, 쉽게는 못풀었다 ㅠ ㅠ 일단 벽을 3개 무조건 세워야 해서, 벽을 3개 세우는 모든 경우의 수를 생각해야함! 시간 제한은 2초에, 2차원 배열 크기는 (3 ≤ N, M ≤ 8) 이라서 시간초과는 무한루프 제외하고는 거의 안걸릴 듯 하다! **벽이 무조건 3개 일때만 실행해주게 해야함. if(cnt == 3) 조건 추가 후 2에 .. [Baekjoon] 백준 2644번: 촌수계산 (c++) https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 부모 자식간은 1촌, 형제간엔 2촌인데.... 1촌으로 착각해서.... 좀 헤맸다....ㅎㅎㅠㅠ 그냥 촌수는 노드간의 간선 개수 라고생각하면 됨! DFS를 이용해서, 노드 사이의 간선의 개수를 구하면 된다. 노드 사이 간선을 구하기위해 양방향으로 노드들을 저장했다. 1. num에 노드를 양방향으로 저장 2. 촌수를 계산하기 위해 입력받은 a, b를 DFS 실행 3. a가 b(=.. [Baekjoon] 백준 2667번: 단지번호붙이기 (c++) https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net DFS 정석 문제같은 느낌이었다. 1. 지도에서 1인곳을 방문하여, 이어진 칸 개수만큼 개수를 세고, 벡터에 개수를 저장한다. 2. 이어져있지 않은 곳은 또 따로 칸 개수를 세고 칸 개수를 저장해서, 3. 마지막에 벡터를 오름차순으로 정렬한 뒤 , 크기와 함께 요소들을 순서대로 출력해주면 된다. 코드(c++) #include #include #include #include using namespac.. [Baekjoon] 백준 2178번: 미로 탐색 (c++) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 쉽게 풀릴 줄 알았는데 실수를,,,많이 한 문제다 먼저 최단거리를 구할 때는 BFS로 탐색해야하는데, DFS를 써 버린 것. DFS는 재귀호출 하는 가지수가 너무 많아서 시간초과가 걸렸다. DFS DFS ⚭ BFS BFS - 검색 대상 그래프가 큰 경우(정점과 간선의 개수가 많은 경우) - 경로의 특징을 저장해둬야 하는 문제 • ( ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면.. [Baekjoon] 백준 10775번: 공항 (c++) https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net Union Find문제에 익숙해져서 그런지 솔루션을 찾으면 푸는데 크게 어려움은 없었다. 다만 문제 이해가 오래 걸릴뿐... 내가 푼 방법은 이렇다 게이트들을 모두 노드라고 생각하고, 1. 입력 g에 대하여 루트노드를 찾는다. Find(g) 2. 루트 노드 g_parent에 대하여, g_parent의 차선책을 g_parent-1로 지정한다. Union(g_pare.. 이전 1 2 3 4 ··· 10 다음
