코딩테스트/Python 문제풀이
[프로그래머스] 섬 연결하기(Kruskal)
https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr Spanning Tree(신장트리)문제입니다. 이러한 신장트리 문제에서는 Prim이나 Kruskal 알고리즘을 사용한다고 합니다. (하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분그래프) 문제부터 간단하게 요약하면, 다음 그림과 같이 섬들을 연결하려 하는데, 모든 섬들을 연결하면서, 최소 비용으로 다리를 건설할 때 최소 비용을 return하는 문제입니다. 위의 그림과 같은 상황에서는 초록색 선들을 연결해서 건설하는 것이 가장 효율적..
[백준] 백조의 호수
https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net BFS를 사용하는 문제입니다. 생각보다 python으로 해결하기에 시간제한이 빡빡한 문제인 것 같습니다. 문제부터 요약해보면, ...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... ....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... ...XXXXXXXXXXXX.. ....XXX..X..
[백준] 가운데를 말해요
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net Heap을 사용하는 문제입니다. 문제부터 요약해보면, 숫자를 이야기 할 때 마다 이전에 이야기 한 숫자들과 종합해 오름차순으로 정렬 되었다고 생각할 때, 가운데를 return해야합니다. 예시를 문제에서 주었는데 만약 1,3,5,2를 이야기 한다면 [1] [1,3] [1,3,5] [1,2,3,5] 각각 이런 상황으로 정렬이 되기에 1,1,3,2를 return하여야 합니다. 자세한 e..
[백준] 평범한 배낭(Knapsack, DP)
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net Dynamic Programming을 사용하는 문제입니다. 문제부터 요약해보면, N개의 물건이 각각 W라는 무게와 V라는 가치를 가집니다. 이 때, 최대로 버틸 수 있는 무게 K가 주어지면, 얼마만큼의 최대 가치를 물건들을 통해 얻을 수 있는지를 return 하여야 합니다. 이 문제는 Knapsack problem으로 유명한 문제입..
[프로그래머스] 카드 짝 맞추기(BFS, DFS)
https://programmers.co.kr/learn/courses/30/lessons/72415 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr bfs와 dfs를 사용하는 문제입니다. 자칫 greedy같은 것을 사용하시는 분들이 있는데 이 방법은 옳은지 틀린지 모르겠으나 예외 케이스가 아마 존재할 것입니다. 실제 올바른 풀이를 먼저 제시하고, testcase는 모두 통과하나 잘못된 풀이도 첨부하겠습니다. (블로그 주인장과 다르거나 더 좋은 풀이법이 있을 수 있습니다. 댓글도 환영합니다.) 우선 문제부터 요약..
[프로그래머스] 배달(Dijkstra)
https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 다익스트라(Dijkstra)를 그대로 활용하는 문제입니다. 문제부터 간단하게 요약하면, N개의 마을로 이루어진 나라에서 서로 양방향으로 이동이 가능하고 걸리는 시간이 주어지는 그래프가 주어질 때, 1번 마을이 주어진 시간 내에 배달할 수 있는 마을의 수를 return하는 문제입니다. 위와 같은 상황에서 1번 마을이 3 이하의 시간으로 배..
[프로그래머스] 입국심사(이분탐색)
https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 이분탐색으로 푸는 문제입니다. 문제부터 간단하게 요약하면, 입국 심사를 기다리는 사람들이 times라는 array안의 element만큼의 시간이 각각 걸리는 심사위원들에게 심사를 받을 때, 가장 빠른 시간안에 모든 사람들이 심사를 받게 할 수 있는 시간을 구하는 것입니다. 예시입니다. 6명의 사람들이 2명의 심사위원에게 심사를 받을 때 걸리는 최소 시간은 28입니..
[프로그래머스] 신고 결과 받기
https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 문제부터 간단하게 요약하면, 신고를 처리하고, 처리결과를 메일로 발송하는 시스템에서, 정지기준이 주어질 때, 각 유저별로 본인이 신고한 사람에 대한 결과 처리 메일을 받은 횟수를 return 해주는 문제입니다. 문제의 규칙은 다음과 같습니다. solution(id_list, report, k)에 id_list : 이용자의 ID report : 각 이용자가..