전체 글
[프로그래머스] 빛의 경로 사이클
https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 특별한 알고리즘이 쓰이는 문제는 아니고, 직접 탐색을 하는 문제입니다. 우선 문제부터 간단하게 요약해보면, 다음과 같은 grid에 빛을 쏩니다. 이때 각각에는 S, L, R이 적혀 있고, 빛을 직진, 왼쪽, 오른쪽으로 각각 발사시킵니다. 이때, 각각의 cycle의 길이를 오름차순으로 return하는 것이 문제입니다. 조금더 자세한 내..
[프로그래머스] 불량 사용자(DFS)
https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr DFS를 활용하는 문제입니다. 우선 문제부터 요약하면, 다음과 같이 제재된 아이디와 유저의 아이디가 들어오면, 유저의 아이디로 제재된 아이디를 몇가지 조합으로 구성할 수 있는가에 관한 문제입니다. 자세한 내용은 위의 링크를 읽어보는 것이 정확합니다. 간단한 예시 하나만 설명하면, 가장 첫번째의 예시는 ["fr*d*", "abc1**"] 이렇게 밴을 당하기 때문에..
[프로그래머스] 섬 연결하기(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는 모두 통과하나 잘못된 풀이도 첨부하겠습니다. (블로그 주인장과 다르거나 더 좋은 풀이법이 있을 수 있습니다. 댓글도 환영합니다.) 우선 문제부터 요약..