https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net # 그냥 문제만 읽어봐도 MST를 사용해서 푸는 문제임을 알 수 있다. 1. 처음에 M개의 도로를 (a, b, c)로 입력받고 build에는 (c, a, b)로 저장해준다. ( build.sort()를 했을때 c부터 정렬되게 하기 위해서) 2. total_cost에 모든 도로..
https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net # N이 100만이하이고, M이 100만이하이므로 단순히 M에서 찾고자하는 문자열을 하나하나 비교해서 풀면 O(N * M)이므로 시간초과가 난다. 해설들을 보니 M을 한번만 순회해서 찾는 O(M)방법도 많고 빠르긴 한데 KMP알고리즘을 공부하기 위해 KMP를 사용해서 풀었다. (KMP 알고리즘은 O(N + M)에 동작한다. # k..
https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net # Trie(트라이) 자료구조를 사용해서 푸는 문제이다. (물론 그냥 내장함수 startswith을 사용해도 풀리긴 한다) * insert함수: string 문자열의 한 글자씩 트리의 children에 저장해주고 마지막 노드에는 전체 문자열인 string을 저장해준다. * search함수: string 문자열을 하나씩 돌며 트리의 children을 계속 방문한다. 문자열을 ..
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net # 사이클 단어에 눈돌아가서 DFS로 풀려다 실패했다. 단방향 그래프라서 그런건지, 그냥 플로이드-와샬 알고리즘을 사용해서 풀면되는 간단한 문제이다. # dist에 각 정점들 사이의 거리를 입력해주고 플로이드-와샬 알고리즘을 사용해 모든 dist값들을 최단경로로 갱신해준다. # ans에 inf값을 넣어주고 dist배열을 모두 확인하며 dist[i][j]와 dist..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net # DFS로 '사이클'을 찾으면 되는 문제이다. 코테나 다른 그래프 문제중에 사이클을 찾는 문제들을 자주 볼 수 있는데, 생각보다 코드로 구현하기 힘들다. 재귀가 함수 안에서 함수를 계속 부르고 그런것이 가시적이지 않아서 그런 것 같다. 쨋든, 사이클을 찾는 방법은 자주 쓰이니 이해하고 외워두는 것이 좋다! # 배열의 인덱스는 0부터 시작하기 때문에 편하게 숫자를 보기위해 graph에 [0]을 맨앞에 ..
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net # Union-Find와 BFS 등 여러 풀이가 있는 문제이다. I. Union-Find union, find, check함수는 well-known이니 따로 설명하지 않겠다. 1. 우선 처음에 N, M을 입력받고 진실을 아는 사람수 t와 그 사람들 리스트 tp를 입력받는다. tp에 있는 사람들 번호에 해당하는 know_truth[i]를 True로 바꿔준다. 그리고 M줄에 걸쳐 각 파티마다 오는 사람의 수 p..
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net # BFS/DFS + 시뮬레이션 문제이다. BFS나 DFS 중 아무거나 선택해서 풀면 되는데, BFS가 편해서 BFS로 풀었다. 1. 매 시간마다 m을 돌면서 m[i][j]가 0이 아니고 방문하지 않은 지점이라면 iceberg를 1증가시키고 bfs(i, j, visited)를 실행한다. # bfs함수: 상하좌우를 탐색하며 m[nx][ny]가 0이면 diff[(x, y)] += 1을 해줌으로써..
https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net # 처음에 그냥 union-Find문제인 줄 알고 풀었는데 요구하는 바가 약간 달랐다. 단순히 한 사람이 다른 몇명과 친구인지가 중요한게 아니라 문제에서 요구하는 A-B, B-C, C-D, D-E 이 4가지의 경우를 만족하는지 확인하는 문제이다. 따라서, DFS를 사용하여 꼬리에 꼬리를 무는 식으로 풀었다. # DFS함수: cnt와 x를 넘겨받아 cnt가 4가 되면 문제에서 요구하는 친구관계가 성립되었으므로 1을 출력하고 프로그램을 종료한다. graph[x]안의 원소들을 돌면서 i원소를 방문하지 않았으..
모르는 사이에 조금씩 조금씩..
