본문 바로가기

알고리즘/Baekjoon

 (196)
bfs. [16953] [1. 문제 설명] https://www.acmicpc.net/problem/16953 [2. 풀이 접근] bfs 를 이용해서 A -> B 까지 이동하는 최단 길이를 찾는다. B 는 최대 10억 까지 주어지므로, 배열로 visit table 을 잡을 수 없다. => 메모리 제한 map 을 이용해서 visit table 로 사용한다. A -> B 로 가는 단방향 탐색으로도 시간 내에 해결 할 수 있어보이지만, A->B 와 B->A 로 이동하는 양방향 탐색으로 해결해 보도록 한다. 단방향 탐색으로 시간 내 해결 가능해 보이는 이유는 1.) 현재 값에서 2배씩 늘어남. 2.) 현재 값에서 10배 한 다음 +1 한 값으로 늘어 남. 값이 크게 크게 점프하므로, int 를 사용하면 오버플로우 때문에 오답이 발생 ..
최소신장트리. [14621] [1. 문제 설명] https://www.acmicpc.net/problem/14621 [2. 풀이 접근] 그래프 문제 관련 함정 같은 edge 인데, weight 가 다른 edge 가 여러 개가 입력으로 있을 수 있다. 크루스칼 알고리즘 같은 경우는 우선순위 큐를 사용해서, 최소 weight 가 아닌 edge 는 결과적으로 버려진다. 그러나 최소 신장 트리 문제가 아닌 경우에는, 반드시 최소 weight 인 edge 를 사용하도록 데이터 변경이 필요하다. 이번 문제에서 나름 함정(?) edge 를 구성하는 두 노드의 성향이 같은 경우, 이 edge 는 사용해서는 안된다. => 문제 조건이었다. [3. 코드]
최소 신장 트리. [6497] [1. 문제 설명] https://www.acmicpc.net/problem/6497 [2. 풀이 접근] 함정(?) 입력이 주어지는 방식 => 보통 몇개의 TC 가 있고, TC 개수 만큼 반복 수행 => 이 문제에서는 특정 입력이 들어오기 전 까지가 모두 TC 이다. u -> v 로 가는 경로가 여러 가지 일 수 있다. => 이 때, => 우선순위 큐 사용이 없으면, u v 로 연결되는 edge 의 cost 를 최소 값을 쓰도록 해야한다. => map 을 이용해서, 최소 cost 추적이 필요 함. => 문제에서 node 가 최대 2,000,000 개 이므로, 인접 행렬을 사용 할 수 없다. => 이 문제에서는 mst 를 구해야 하므로, 우선순위 큐를 사용하므로, 위와 같이 할 필요는 없다. [3. 코드]
bfs. [13460] [1. 문제 설명] https://www.acmicpc.net/problem/13460 [2. 풀이 접근] 까다로웠던 문제 게임판을 기울이는 것으로 인해, 구슬의 위치가 결정되는데 이 때, 어떤 구슬의 최종 위치는 다른 구슬의 현재 위치에 의해 결정된다. 즉, 두 구슬은 서로 종속적이다. 방문 순서 결정 테이블은 두 구슬의 위치 모두에 영향을 받는다. ... [3. 코드]
bfs. [16234] [1. 문제 설명] https://www.acmicpc.net/problem/16234 [2. 풀이 접근] [3. 코드]
bfs. [16236] [1. 문제 설명] https://www.acmicpc.net/problem/16236 [2. 풀이 접근] 코드 참조.. [3. 코드]
dfs. [9466] [1. 문제 설명] https://www.acmicpc.net/problem/9466 [2. 풀이 접근] [3. 코드]
dfs. [2644] [1. 문제 설명] https://www.acmicpc.net/problem/2644 [2. 풀이 접근] 그래프 구축 모든 부모 자식 간의 관계에 대해서, 그래프를 무방향 그래프로 구축해야 한다. 부모->자식으로 가는 방향 그래프로 구축한다면, 임의의 두 사람 u, v 에 대해서 촌수를 구할 수 없다. u 가 자식이고, v 가 부모인 경우, u->v 인 edge 는 존재하지 않기 때문이다. 따라서, 그래프는 무방향 그래프로 구축해야 한다. DFS 종료 시 처리 u 에서 dfs 를 시작하였는데, v 를 만나지 못했다면, 재귀를 종료하고 되돌아가는 시점에서, 현재까지 방문한 모든 정점에 대해서 다시 미방문 처리하지 않아도 된다. 이 정점들은 v 와는 아무 관련이 없기 때문이다. u 에서 dfs 시작 후, a..
dfs. [1987] [1. 문제 설명]] https://www.acmicpc.net/problem/1987 [2. 풀이 접근] [3. 코드]
KMP. [1305] [1. 문제 설명] https://www.acmicpc.net/problem/1305 [2. 풀이 접근] 간단한 방법 광고 문구 길이를 1부터 시작해서 반복 각 시작 위치부터 광고문구 길이를 n 이라 했을 때, 문자열이 반복되는지 확인해야 함 시간복잡도 = O(N3) 시간 초과. kmp 알고리즘 중 부분 매치 테이블을 이용한 풀이 핵심은, n 글자 일치 했을 때, 접두사==접미사인 가장 긴 문자열의 길이를 구하는 것 자세한 설명은 주석 참조 [3. 코드]

티스토리툴바