Algorithm
[백준] 2281. 데스노트 - 파이썬
https://www.acmicpc.net/problem/2281 풀이 DP (Dynamic Programming) 문제. 나는 기본적으로 DP는 bottom-up 방식으로 푸는 것을 선호하고, 풀이도 bottom-up 방식으로 먼저 생각해내곤 하는데, 이 문제는 잘 생각이 나지 않아 시도하다 다시 top-down 방식으로 선회한 문제. top-down 방식으로 푸는 것이 훨씬 구현하기 수월했다. 먼저 기저 상태를 0으로 설정하고, memoization을 활용해 이미 계산된 dp[index]가 존재하면 (maxNum으로 초기화했으므로, maxNum보다 작으면 값이 담긴 것) 그 값을 return. dp[index]는 index+1번째의 이름을 '새로운 줄' 에 작성할 때, 남은 공간들의 제..
[백준] 1107. 리모컨 - 파이썬
https://www.acmicpc.net/problem/1107 풀이 이것저것 여러 방법을 생각해 봤으나, 마땅한 수가 생각나지 않았음. 문제 조건에서 채널이 500,000개 정도였기 때문에 Brute-Force로 시도해볼 만하다고 생각해서 Brute-Force로 실행. 다만 0~500,000 까지의 수를 모두 대입해 보기보다는, 고장난 버튼을 염두에 두고, 조합 가능한 모든 6자리까지의 경우의 수를 미리 만들어 두고, 그 이후 처리하는 것이 속도 면에서 이득이다. # 100에서 움직일 때와 버튼을 누르고 움직일 때, 둘 중 최솟값을 채택 channels[ch] = min(abs(goal - 100), len(str(ch)) + abs(goal - ch)) 0 ~ 500,000 까지의 모든 수를 대입한..
[백준] 1655. 가운데를 말해요
[백준] 1655. 가운데를 말해요 - 파이썬 https://www.acmicpc.net/problem/1655 풀이 1 일단 첫 시도는, 최소 힙을 사용. 입력받은 수들의 리스트를 저장 후, 반복문을 돌릴 때 마다 리스트를 알맞게 slicing하여 heapify, 그리고 매 반복마다 pop 후 heapify를 2/n회(가운데 값을 찾을 때 까지) 반복하여 중간값을 찾도록 코드를 짰다. 결과는 시간초과. python에서의 heapify() 는 O(N)의 time complexity를 가지고, heappop(), heappush() 는 각각 O(logN)의 time complexity를 가지므로, 간단히 계산해 봐도 최소 O(N^2) 이상의 complexity이고, 그냥 생각나는대로 대충 시도해봤기 때문에..
[프로그래머스] 67260. 동굴 탐험
2020 카카오 인턴십 - 67260. 동굴 탐험 Python 풀이 풀이 복잡한 알고리즘을 생각할 필요 없이, BFS로 탐색하면서 order (방문 순서) 만 처리해 주면 된다고 생각했다. 그리고 효율성을 위해 방문 체크는 Hash로 구성된 Set을 이용. 근데.. 각 루프마다 False 체크를 하니까 시간초과가 난다. def A(): for room in rooms: if room not in follow: return False return True 얘 때문 맞는듯.. Code from collections import deque def solution(n, path, order): pre = [i[0] for i in order] follow = [i[1] for i in order] visit =..
[프로그래머스] 67258. 보석 쇼핑
2020 카카오 인턴십 - 67258. 보석 쇼핑 Python 풀이 풀이 1 Two Pointer(투 포인터) 알고리즘을 이용해 풀이. 외국에선.. Two Pointer Technique(투 포인터 테크닉) 이라고 부르는 듯. start, end Pointer를 정하고, 처음엔 조건을 만족할 때까지 end += 1 그 이후, 조건을 만족하는 한 start += 1 그렇게 조건을 만족하는 [start, end]를 구함. 그 이후, 뒤쪽에 더 짧은 답이 존재할 수 있으니 end에 +1을 해주며, end < len(gems) 이하에서 반복. 그렇게 Two Pointer를 이용해 풀이하였으나, 시간 초과. Code def solution(gems): gemList = len(set(gems)) start = 0..
[프로그래머스] 67256. 키패드 누르기
2020 카카오 인턴십 - 67256. 키패드 누르기 Python 풀이 풀이 dictionary로 각 키패드의 행, 렬을 저장하고, 이를 이용해 키패드간의 거리를 계산하면서 if-else문을 통해 처리. Code from collections import deque def solution(numbers, hand): isRight = True if (hand == "right") else False keyPad = {1: [1, 1], 2: [1, 2], 3: [1, 3], 4: [2, 1], 5: [2, 2], 6: [2, 3], 7: [3, 1], 8: [3, 2], 9: [3, 3], '*': [4, 1], 0: [4, 2], '#': [4, 3]} def distanc..
[프로그래머스] 67257. 수식 최대화
2020 카카오 인턴십 - 67257. 수식 최대화 Python 풀이 풀이 우선, 이런 중위 표현식, 후위 표현식, 연산자 우선순위에 관한 문제들을 숱히 Stack으로 풀어 왔기에, Stack을 이용해 풀이해 보자 - 라고 생각했으나, 굳이 그럴 필요 없을 것 같아서 간단하게 생각하여 풀이했다. 우선순위 경우의 수가 최대 6가지밖에 없으니, 6가지 경우의 수를 모두 따져 보아 계산한다. 만약, 우선순위가 ['*', '-', '+'] 라면, '*' 를 모두 찾아 앞뒤로 계산 후 다시 그 index쪽에 집어넣고, 그 다음 '-' 도 같은 방법으로. 마지막으로 '+' 도 같은 방법으로 계산. 예를 들어, 아래와 같다면, ex..
[프로그래머스] 64062. 징검다리 건너기
2019 카카오 개발자 겨울 인턴십 - 64062. 징검다리 건너기 Python 풀이 풀이 일단, 효율성을 측정하는 문제이기 때문에, 한 명이 징검다리를 건널 때 마다 모든 돌에 -1을 하고, 그 때마다 k보다 간격이 큰 징검다리가 있는 지 검사하는 방식은 통할 리가 없음. def solution(stones, k): for i in range(1, 200000000): stones = list(map(lambda x: x-1, stones)) cnt = 0 for stone in stones: if stone < 1: cnt += 1 if cnt == k: return i else: cnt = 0 이런 식으로. 당연히 정확성만 통과, 효율성은 통과 하나도 못 함. 풀이 2 이것도 Union-Find로 ..