Algorithm
[프로그래머스(파이썬/Python)] 보석 쇼핑(2020 카카오 개발자 인턴십)
https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 카카오의 효율성 문제를 풀면 눈물이 납니다. 이 문제를 풀 때도 1) O(N^2)으로 몇 가지 트릭을 넣은 풀이, 2) 이분 탐색으로 O(N*logN), 두 가지 방법을 시도해보았지만 모두 다 효율성 테스트를 통과하지 못했습니다... 사실, 이 문제에서 투 포인터를 써야겠다는 생각은 바로 들었지만 뭔가 계속 구현이 꼬이고 몇 가지 테스트 케이스가 틀리고를 반복하다보니 다른 방법으로 회피한 것 같은 느낌도 있었습..
Algorithm
[프로그래머스(파이썬/Python)] 멀리 뛰기
https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 프로그래머스 Level3 문제치고 정말 쉬운 DP문제입니다. DP 문제인 정당성은 N칸을 점프하는 경우의 수가 그 이전 칸(N-1, N-2)의 경우의 수에서 더해지는 방식이기 때문에 전체 문제의 최적해가 부분 문제의 최적해를 보장한다는 점에 있죠. N번째 칸에 도착하기 위해서는 N-1번째 칸에서 1칸 점프..
Algorithm
[프로그래머스(파이썬/Python)] 배달
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 전형적인 다익스트라 알고리즘 문제입니다. 먼저, 문제에서 임의의 두 지점 사이 가는 경로가 여러 개 주어질 수 있다고 했으므로 가장 짧은 거리만 배열에 저장하도록 처리를 해줘야 합니다. 이는 기존에 저장된 cost값과 현재 input으로 주어진 cost값을 비교하면 되겠죠? 다익스트라를 구현할 때는 우선순위 큐(Priority Queue..
Algorithm
[프로그래머스(파이썬/Python)] 순위
https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 이 문제를 해석할 때 가장 중요한 포인트는 "어떤 상황에서 순위가 결정되는가?"에 대한 이해입니다. 순위가 결정되려면 자신이 결투를 해서 이기는 사람, 지는 사람을 카운트할 때 자신을 제외한 n-1명의 정보가 모두 있어야 합니다. 따라서 results 배열로 주어진 승패 정보를 통해 먼저 각 사람이 이길 수 있는 사람 리스트를 DFS 탐색으로 만들 수 있고, 이 리스트를 바탕으로 역으로 생각해볼 때 이긴 사람의 리스트에 포함된 사람은 해당 사람에게 진 사람이 되기 때문..
Algorithm
[프로그래머스(Programmers)] 게임 맵 최단거리
https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr BFS로 풀 수 있는 전형적인 문제입니다. 최단거리를 구해야하기 때문에 너비 우선 탐색을 진행해주고 도착점에서 결과값이 1이면 거리가 갱신되지 못한 것이므로 -1을 리턴하고, 그 외에는 도착점의 값을 리턴해주면 됩니다. [풀이] from collections import deque dx, dy = [1,-1,..
