코딩테스트/Python 문제풀이
[백준] 2048 (Easy)
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 구현 문제입니다. 문제부터 아주 간단하게 요약하면, 흔히 우리가 플레이 하는 2048을 문제에서 주어진 조건에 맞게 implement 하는 문제입니다. 이 때, 총 5번의 이동을 거친후 남게 될 수 있는 가장 큰 숫자가 무엇인지를 return 해야 합니다. move 함수는 현재 보드의 상태와, 이동방향을 받아서 새로운 보드를 만들어주는 함수입니다. 이 move 함수만 ..
[백준] 웜홀
https://www.acmicpc.net/problem/1865 1865번: 웜홀첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net벨만포드(Bellman ford) 알고리즘을 사용해야하는 문제입니다. 우선 문제부터 간단하게 요약하면, 도로는 양의 간선으로 양방향으로 구성되고, 웜홀은 음의 간선으로 단방향으로 구성됩니다. 이렇게 그래프가 구성되었을 때, random한 출발지 A 에서 다시 A로 간선들을 타고 되돌아 왔을 때, 음의 weight를 가지는 것이 하나라도 존재하면, YES를 아니면 NO를 출력해야 합니다. ..
[백준] 곱셈
https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 분할정복을 이용하는 문제입니다. 문제부터 요약하면, A, B, C 가 주어질 때, A를 B번 곱한 수를 C로 나눈 나머지를 출력해야 합니다. 예전에 https://life318.tistory.com/22 [백준] 이항 계수 3(페르마 소정리, modular inverse, 분할정복) https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K..
[백준] 트리의 지름
https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net dfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, Tree의 정보가 주어지면, Tree 에서의 diameter를 구해야 하는 문제입니다. 실제로 문제를 한번 읽어보는 것을 추천합니다. Tree 자료구조란 사이클이 없는 하나의 연결 그래프 또는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프) 의 한 종류라고 합니다. 보통 diameter..
[백준] RGB거리
https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. 우선 문제부터 간단히 요약해보면, N개의 집들을 R, G, B 이렇게 세가지 색으로 색칠해야 하는데 이웃한 두 집들은 색이 달라야 합니다. 이 때, 각각의 집들을 각각의 색으로 색칠할 때 드는 비용이 주어집니다. 이 때, 모든 집들을 색칠할 때 드는 비용의 최솟값을 구하는 것이 문제입니다. 실제로 문제에서는 조건을 복잡하게 주기는 하..