코딩테스트/Python 문제풀이
[백준] 시험 감독
https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 사칙연산을 활용하는 문제입니다. 우선 문제부터 요약하면, N개의 시험장에 학생들이 들어있습니다. 이 때, 학생들을 총감독관 1명과 부감독관 여러명을 이용하여 감시하려고 할 때, 필요한 감독의 총 수를 return해야 합니다. 이 때, 총감독관은 시험장마다 반드시 한명 있어야 하고, 부감독관은 없거나 여러명일 수 있습니다. 우선 각 시험장의 ..
[백준] A와 B
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 그리디 알고리즘을 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, A,B로만 된 영어단어 S와 T가 주어지는데, 1. 문자열의 뒤에 A를 추가한다. 2. 문자열을 뒤집고 뒤에 B를 추가한다. (뒤집는 것의 의미는 ABBABA면 ABABBA로 뒤지는 것임) 이렇게 두 방법을 이용해 S를 T로 바꿀수 있다면 1을 없다면 0을 출력해야 합니다. T에서 S로 ..
[백준] 조합
https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. n,m의 input에 대해 nCm을 계산한 결과를 return하면 됩니다. nCm = n!/(m!*(n-m)!) 이므로, 만약 factorial을 매번 1~특정수 만큼 곱해서 만들면 중복되는 연산들이 존재합니다. 이 과정을 줄이기 위해 factorial dp array를 구성하고, factorial결과를 미리 담아놓고 가져오는 형태로 중복된 계산을 피하도록 구현하면 됩니다. 실제 구현은 아래와 같습니다. import sys n, m = list(map(int, sys.s..
[백준] 트리의 순회
https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net stack을 이용하는 문제입니다. 문제부터 간단하게 요약해보면, inorder와 postorder의 배열이 주어지면 이 두개를 사용하여 preorder 배열을 return해야 합니다. 사실 이 문제의 해결방법은 대표적으로 두가지가 있을 것 같습니다. 1. inorder와 postorder를 이용해 tree를 실제로 구현한 후, 해당 tree를 이용하여 preorder를 return하는 방법 2. tree를 구현하지 않고 i..
[백준] N과 M (4)
https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복조합을 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N과 M을 입력받아서, 1~N까지의 숫자중 중복을 허용해서 M개를 뽑는 경우들을 print 하는 것이 문제입니다. 파이썬의 기본 itertools 라이브러리안의 combinations_with_replacement를 사용하여 문제를 해결하였습니다. 실제 구현은 아래와 같습니다. import sys import itertools N..
[백준] A → B
https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 그리디 알고리즘을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, a, b를 입력받아 a에 1. 2를 곱한다 2. 1을 수의 가장 오른쪽에 추가한다 이렇게 두가지 연산을 통해 만드는 최소횟수 + 1을 return해야 합니다. 만약 만들 수 없을 경우, -1을 return해야 합니다. 간단한 풀이와 주의해야하는점 하나만 이야기하려 합니다. 우선 문제의 아이디어는 거꾸로 생각하면 됩니다. ex) 2 → 4 → 8 → 81 → 162 의 경우에서 162가 결국 어떤 수로부터 나왔어야 하므로, 위의 두가지 연산중 이전의 ..
[백준] 벽 부수고 이동하기
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net bfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약해보면, N*M의 0과 1로 표현된 array가 주어집니다. 이때 1은 벽을 의미하는데 (1,1)에서 (N,M)으로 이동할 때, 벽을 최대 1개까지 부수고 이동이 가능합니다. 이 때, 최단거리를 출력하는 문제입니다. 만약 최단거리가 없다면 -1을 출력해야합니다. 이 문제는 기존 bfs에서 주로 두는 visited a..
[백준] 내려가기
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 다이나믹 프로그래밍을 이용하여 푸는 문제입니다. 우선 문제부터 간단하게 요약하면, 1 2 3 4 5 6 7 8 9 9 7 1 위의 그림과 같이 array가 주어집니다. 이때, 가장 위에서 원룡이가 내려가게 되는데, 바로 아래방향에 있는 수로 넘어가거나, 그 수와 붙어있는 수로만 이동할 수 있다는 조건이 있습니다. 이때, 가장 아래까지 도달했을 때, 얻을 수 있는 최대 점수와 최소 점수를 return 해야 합니다..