본문 바로가기

백준 문제 풀이

 (134)
백준 12893번 - 적의 적(C++) https://www.acmicpc.net/problem/12893 12893번: 적의 적 첫 줄에 용재 주위 사람의 수 N(1 ≤ N ≤ 2,000)과 적대관계의 수 M(0 ≤ M ≤ 1,000,000)이 주어진다. 두 번째 줄부터 M개의 줄에 거쳐 서로 적대관계에 있는 사람의 번호 A, B(1 ≤ A, B ≤ N)가 주어진다. www.acmicpc.net 문제를 처음 접했을 때 그래프 문제라는 것은 바로 파악할 수 있었다. 그러나 이 문제는 이분 그래프의 정석이라고 난이도 기여에서 말하던데 이분 그래프를 자세히 공부해본적이 없어서 조금 어려웠던 듯 하다. 우선 먼저 적대관계 그래프를 그려서 문제의 의미를 파악해보자. 1 2 2 3 3 4 4 5 입력이 들어온다면 위와 같은 적대 그래프가 만들어질 것이..
백준 1786번 - 찾기(C++) https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net KMP 알고리즘의 기본 문제이다. 문제에서도 친절하게 KMP알고리즘에 대해 설명하고 있다. https://tigerfrom2.tistory.com/400 문자열 찾기 - KMP 알고리즘 KMP 알고리즘이란? KMP 알고리즘이란 문자열에서 단어를 빠르게 골라낼 수 있는 알고리즘이다. 러프하게 생각하면 쉽게 문자를 찾아낼 수 있지만 이것은 아주 느리다. KMP의 아이디어 KMP의 중요한 tige..
백준 16928번 - 뱀과 사다리 게임(C++) https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 다익스트라, 그래프 등 많은 것을 고민했지만 그냥 bfs 풀이가 가장 쉬운 풀이이다. #include #include #include using namespace std; map jump; bool visited[101] = { false, }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL..
백준 1967번 - 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 가장 먼저 생각난 풀이는 플로이드-워셜 알고리즘이었다. 그러나 플로이드 워셜의 시간복잡도는 O(N^3)이기 때문에 불가능했다. 그래서 트리에서의 DP를 생각해보았지만 딱히 해결법이 생각나지 않았다. 가장 쉬운 방법은 모든 지점에서 dfs를 수행하는 것이다. 노드의 개수가 1만이기 때문에 O( (V + E )^2 ) = 2만 제곱 = 4천만으로, 해결이 가능하지만 이게 정해라면 ..
백준 9466번 - 텀 프로젝트 (C++) https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 위 문제를 보고 그래프 문제라는 것을 깨닫는 것이 첫번째 단계다. 여기서 1~7을 노드라고 생각하자. 그리고 아래 숫자들은 노드가 가리키는 또다른 노드라고 생각하면, 위 표는 아래같은 그래프로 나타낼 수 있다. 이제 이 문제가 파악이 될 것이다. 이 문제는 그래프로 나타낸 뒤 사이클을 파악하는 것이 핵심이다. 이제 이것을 어떻게 파악해야할까. 가장 쉬운 것은 모든 노드에서 dfs를 돌리면서 자기 자신으..
백준 1520번 - 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 길찾기 문제 + 경로 개수 찾기 문제이다. 만약 이 문제가 내리막길을 찾으면서 가장 빨리 도착해야겠다면 다익스트라 혹은 BFS문제였을 것이다. 그러나 이 문제는 경로의 개수 를 찾는 문제이다. 답만 찾으려면 dfs로 조건만 돌리면 되지만, 이렇게하면 4^500*500 으로 당연히 시간초과가 난다. 그러므로 메모이제이션을 통해 지금이 노드를 이용하면 마지막 노드까지 갈 수 있는지 없는지를 저장해놔..
백준 2651번 - 자동자경주대회 (C++) https://www.acmicpc.net/problem/2651 2651번: 자동차경주대회 전국 자동차 경주 대회가 매년 열리고 있다. 이 대회에서는 출발지점부터 도착지점까지 거리가 워낙 멀기 때문에 경주 도중에 각 자동차는 정비소를 방문하여 정비를 받아야 한다. 정비소들은 www.acmicpc.net 어떤 코테에서 봤던 문제인 것 같다. 역시나 코테의 문제들은 모두 백준에 존재한다. 많이 풀어보고 완벽하게 익히고 있어야한다. 먼저 이 문제를 봤을 때 떠올랐던 풀이는 다익스트라, 배낭문제, 다이나믹 프로그래밍이었다. dp[N][2] 를 선언하고 충전을 하였을 때와 안하였을 때를 넣으려고 했는데 생각보다 잘 안됐다. 이 문제를 해결하기 위해 필요한 건 글쎄,, 이런 문제를 풀어본 경험 혹은 아주 뛰어난 ..
백준 1623번 - 신년 파티 (C++) https://www.acmicpc.net/problem/1623 부모가 참가하지 않으므로 자식이 참가해도되고 안해도 된다. dp[2][1] => 내가 무조건 참가한다. 자식은 참가하지 못한다. 이것이 이루어진다. 이것을 코드로 바꿔보면 void dfs(int n) { dp[n][0] = 0; dp[n][1] = score[n]; for (int i = 0; i < node[n].size(); i++) { int next_n = node[n][i]; dfs(next_n); dp[n][1] = dp[next_n][0] + dp[n][1]; dp[n][0] = max(dp[next_n][0], dp[next_n][1]); } } 여기서 끝났으면 이 문제는 골드1 난이도가 아닐 것이다. 이 문제는 더 나아가서..

티스토리툴바