코딩테스트/Python 문제풀이

[백준] 거짓말

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 집합 자료구조를 활용하는 문제입니다. 우선 문제부터 간단하게 요약해보면, 파티에서 지민이는 거짓말을 해야하는데, 이 때 이미 진실을 알고있는 사람들의 집합이 이미 주어집니다. 이 때, 지민이가 거짓말을 할 수 있는 파티의 최대 갯수를 구해야 합니다. 진실을 모르던 사람이라도 각각 다른 파티에서 진실과 거짓 두가지 모두를 듣게 되면, 진실을 알게 되므로 이런 상황 또한 고려해 주어야합니다. 일단 다른 사람들의..

[백준] 구슬 탈출 2

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net bfs를 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 5 5 ##### #..B# #.#.# #RO.# ##### 다음과 같이 row, column이 첫줄에, 그리고 이후로는 구슬이 움직이는 공간이 2d array로 주어집니다. 이 때, 상하 좌우로 구슬을 기울여 빨간 구슬이 빠져나오게 하는 최소 횟수를 구해야 합니다. 이 때, 10번 ..

[백준] 사전

https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. 우선 문제부터 간단히 요약하면, a의 갯수 M, z의 갯수 N이 주어질 때, 사전형태로 나열 했을 경우, K 번째 문자열을 return 해야 합니다. 메모리제한이 생각보다 작게 걸려 있어서 combination을 저장해서 하는 방식에서는 메모리 초과가 나왔는데 두가지 방법 모두 설명해 보겠습니다. 우선 조합을 이용하기 위해 피보나치 수열을 dp table로 구성해서..

[백준] 1로 만들기 2

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. 우선 문제부터 요약하면, 3으로 나누거나, 2로 나누거나, 1을 빼는 총 3종류의 연산을 할 수 있을 때, 연산을 해서 1을 만들 수 있는 횟수의 최솟값을 return 해야 합니다. 또한 이렇게 최소 횟수로 진행되는 경우에 등장하는 숫자도 return 해야 합니다. 이 문제는 숫자를 return해야 하는 과정이 조금은 까다로운데 설명해 보도록 하겠습니다. Dynamic programming의 코드를 작성 할 때는 2가지의 방법을 이용하는데 top-down, b..

[백준] 내리막 길

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net DFS와 다이나믹 프로그래밍을 사용하는 문제입니다. 문제부터 간단하게 요약하면, 다음과 같이 2d array에서 각 숫자들은 높이를 의미합니다. 가장 왼쪽 위에서 가장 오른쪽 밑으로 도달하는 경로의 수를 구해야 하는데, 이 때, 높이가 높은 곳에서 낮은 곳으로 이동하는 경우의 수를 return 해야 합니다. .우선 아이디어는 다음과 같습니다. 특정 칸에 도착을 했다고 가정해봅시다. 이 때, 그 이후에 ..

[백준] 동전 1

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 다이나믹 프로그래밍을 사용하는 문제입니다. 메모리를 많이주지 않아, 불필요한 할당을 하니 처음에 메모리 초과가 나왔는데 둘다 설명해 보도록 하겠습니다. 우선 문제부터 요약하면, n가지 종류의 동전으로 가치합을 k로 만드는 경우의 수를 return 해야 합니다. 1,2,5의 가치를 가진 동전으로 10의 가치를 만드는 경우는 10가지 이므로 10을 return 해야 합니다. 우선 아이디어는 다음과 같습..

[백준] 포도주 시식

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. 우선 문제부터 요약하면, 포도주가 시식대에 놓여있는데 이중에서 3개를 연속해서 마실수 없을 때, 최대한 많은 포도주를 마시고 싶을 때, 마신 포도주의 양을 return 해야 합니다. 프로그래머스의 도둑질 문제와 유사합니다. 대표적인 dp문제인데 주로 2개짜리에 대한 이러한 문제는 유명하게 알려져 있습니다. 이 문제 또한 경우를 조금만 더 쪼개서 풀면 됩니다..

[프로그래머스] 이중우선순위큐

https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr heap을 두개 이용하는 문제입니다. 우선 문제부터 요약하면, 숫자를 넣고, 최댓값을 없애고, 최솟값을 없애는 총 3가지 명령어가 있습니다. 이때, 모든 명령어들을 처리하고 난 후의 상태를 return 해주는 문제입니다. 실제 명령어가 생긴 형태는 다음과 같고 좀더 자세한 내용은 실제 문제 링크를 이용해서 읽어 보는 것을 추천합니다. 아이디어는 두 heap을 어떻게 동기화 시킬 것이냐가 중요합니다. 잘못된 풀이들에는 1. del[index] 로 마지막 것을 그냥 없애줌 (min heap에서 가장 마지막 index가 최댓값이 아님) 2. r..