본문 바로가기

Problem Solving/백준

 (56)
백준 1967 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 트리의 기본 성질 중 하나를 알고 있으면 풀이를 도출하는 게 보다 수월하다. '트리는 어떤 정점을 루트(기준)로 삼아도 트리의 형태로 만들 수 있다.' 이 말이 무엇인지 이해하기 위해 아래 그림을 보자. 위의 그림은 문제에 나온 트리이다. 정점 1이 루트에 있다. 앞서 말한 '어떤 정점을 루트로 삼아도 트리의 형태가 된다'를 확인해보자. 위의 그림과 같이 같은 트리를 6번 정점..
백준 1918 후위 표기식 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 전형적인 스택 활용 문제이다. 스택을 사용할 수 있는 문제/경우들에는 항상 어떠한 순서나 우선순위와 같은 개념이 묻어있다. 스택이 비어있다면 스택에 값을 담고, 값이 있다면 우선순위를 체크하여 어떤 걸 처리할지 정한다. 이 문제처럼 괄호없이도 연산 순서를 표현하는 후위 표기식 표현이나 증가/감소 수열 구하기 등등 반드시 경험해야할 문제중의 하나라고 생각한다. 스택을 활용하게 되면 보통 O..
백준 9658 돌 게임 4 https://www.acmicpc.net/problem/9658 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 이 문제에 앞서 반드시 이전 포스팅(돌 게임 3)을 참조 부탁드린다. 이전 문제(돌 게임 3)에서처럼 이번에도 같은 로직을 적용할 수 있다. 이전 포스팅에서 SK, CY으로 그림 상의 테이블을 채웠는데, 이번엔 전자와 후자로 표현하겠다. 그게 더 올바른 의미이기 때문이다. 길이 1000+1의 DP배열을 먼저 만들어둘 수 있다. 이제 그 배열을 0과 1로 채울텐데 편의상 0이면 전자 승(상근이가 먼저 두므로 상근이의 승리) 1이면 후자 승(창영이의 승리)이 되겠다. 그리고 이전 포스팅에서도 거듭 강조했듯이 이 배열을..
백준 11726 2xn 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 이 문제를 아주 처음 본다면 약간 어려울 수도 있다. 하지만 마음을 가다듬고(?) 하나씩 케이스별로 그림을 몇 개 그려보면 패턴을 이해할 수 있게 된다. 아래의 그림을 보자. 위 그림은 n이 1~4일 때의 상황을 보여준다. n=3일 때는, n=2일 때의 모양에 긴 막대(보라색)를 붙인 2가지의 경우와 n=1일 때의 모양에 누워있는 막대 2개(파랑색)를 붙인 1가지의 경우의 합으로 구할 수 있다. n=4일 때도 마찬가지..
백준 11561 징검다리 https://www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net brute force/완전 탐색은 모든 경우의 수를 전부 따져보는 것을 말한다. 여러 알고리즘은 이러한 모든 경우의 수 중에서 확정적으로 들어낼 수 있는 부분을 걸러준다. 이분탐색은 답이 아니라고 확신하는 부분을 절반씩 들어내기에 빠르게 완탐(?!)이 가능해진다. 혹시나 이분탐색이 생소하다면 이 포스팅을 참조 부탁드린다. 이 문제는 왜 이분탐색으로 풀 수 있을까? 주어진 징검다리의 상한값이 1e16으로 너무너무 커서? 그것도 한가지 힌트가 되겠지만, 문제를 잘 생각해보면, 가장 많은 징검다리를 밟는 방법..
백준 1507 궁금한 민호 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 이 문제는 플로이드 와샬을 역으로 활용하면 된다. 조금 생각해보면 직관적으로 그 아이디어가 떠오를 것이다. 그리고 그게 맞다! 플로이드 와샬 알고리즘을 이용해 최단경로를 구할 때, 최소값으로 계속 갱신해준다. 이번에는 그러한 경우가 발생할 때마다 해당 경로를 지워주면 된다. 각 정점들을 연결하는 도로정보가 주어지는데, 이들을 모두 더할 경우, 모든 도로의 가중치 합의 2배가 된다. 그러므로 중..
백준 1633 최고의 팀 만들기 https://www.acmicpc.net/problem/1633 1633번: 최고의 팀 만들기 꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플 www.acmicpc.net 또다시 전형적인 다이나믹 프로그래밍 문제이다. 문제들 중에는 매 번 또는 매 정점마다 어떠한 처리를 하며 나아갈 때 가장 마지막에 어떤 결과값을 갖는지를 찾는 형식의 문제가 많이 있다. 앞서 말한 '매 번 또는 매 정점마다' m가지의 처리를 할 수 있고 정점이 총 n개 있다면 마지막의 결과값은 무엇인지를 찾는 문제. 이런 문제에 대한 풀이를 나이브(naive)하게 생각해본다면 그 시간복잡도..
백준 2293 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 다이나믹 프로그래밍의 필수적인 문제이다. 예제를 보면 3가지의 동전으로 10을 만들어야 한다. 문제를 풀 때, 머릿속으로 골똘히 생각해 보는 것도 중요하지만, 빈 종이에 케이스를 한번 어느 정도 쭈욱 써보는 것도 큰 도움이 된다. 쓰고 나면 경향성이나 패턴을 읽어낼 수 있는 경우가 있기 때문이다. 10을 만들기 위해서는 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 ..

티스토리툴바