programing/Algorithm
-
[Programmers] 완주하지 못한 선수programing/Algorithm 2020. 10. 24. 17:34
완주하지 못한 선수 해시를 이용해서 푸는 문제. python3 def solution(participant, completion): pMap = dict() cMap = dict() for person in participant: if(person in pMap): pMap[person] += 1 else: pMap[person] = 1 for person in completion: if(person in cMap): cMap[person] += 1 else: cMap[person] = 1 for person in pMap: if(person not in cMap): return person elif(pMap[person] == cMap[person] + 1): return person 참가자와 완주자 ..
-
[Programmers] 크레인 인형뽑기 게임programing/Algorithm 2020. 10. 7. 22:32
2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 난이도 level 1 풀이 def solution(board, moves): basket = [] count = 0 for move in moves: for i in range(len(board)): puppet = board[i][move - 1] if(puppet == 0): continue basket.append(puppet) board[i][move - 1] = 0 length = len(basket) if(length >= 2 and basket[length - 1] == basket[length - 2]): basket.pop() basket.pop() count += 2 break return count
-
[Algorithm] BFS & DFSprograming/Algorithm 2020. 5. 26. 15:29
그래프 탐색 방법 그래프 탐색 방법중 대표적인 것이 BFSbreadth first search와 DFSdepth first sesarch이다. 너비우선 탐색(BFS) 특징 BFS는 탐색을 할 때, 자식을 차례대로 방문한다. 즉, 그래프 노드의 순서대로 방문한다. 이 순서를 지키기 위해 visited와 toVisit이라는 두 Queue를 활용한다. BFS는 완전 탐색을 하기 때문에, 트리 내에 해가 있다면 반드시 해를 찾을 수 있다. 또한 트리의 depth 차례대로 방문하는 특성때문에, 가중치가 모두 동일한 그래프에서 해를 찾는다면 그 해가 최적의 해라는 것을 보장한다. 따라서 이전 상태로 회귀하는 것은 필수가 아니다. 또한 DFS와는 달리, 방문해야 할 노드 목록과 방문한 노드 목록을 각 콜 스택이 공유..
-
[Algorithm] 순열 (Permutation)programing/Algorithm 2020. 1. 3. 12:42
안녕하세요, Einere입니다. (광고 차단 기능을 꺼주시면 감사하겠습니다.) 순열 function permutation(arr) { return arr.reduce( function(list, element) { const newList = []; list.forEach(function(seq) { for (let i = seq.length; i >= 0; i--) { const newSeq = [].concat(seq); newSeq.splice(i, 0, element); newList.push(newSeq); } }); return newList; }, [[]] ); }
-
[BJ] 2616 - 소형기관차programing/Algorithm 2019. 11. 30. 18:54
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 이번 포스트에서는 백준 Q2616 - 소형기관차에 대해 포스팅하겠습니다. 접근 방법 최대한 많은 승객을 싣게 했을 때, 그 승객의 수를 출력하는 문제입니다. 욕심덩어리 기관차네요. 이렇게 특정 조건을 만족하면서 최대 혹은 최소와 관련된 문제가 나온다면 탐욕(greedy) 알고리즘인 경우가 많으며, 또한 탐욕 알고리즘과 같이 딸려오는 개념이 동적 프로그래밍(dynamic programming)이죠. 물론 해당 문제의 분류는 DP입니다. 저는 이 문제를 보고 0-1 knapsack 문제와 매우 유사하다고 생각했습니다. 어찌됬건 각 객차를 선택하거나 선택하지 않거나로 나눌 수 있기 때문이죠. (기타 자잘한 부분은 각종 제약조건으로 검..
-
[BJ] 2869 - 달팽이는 올라가고 싶다programing/Algorithm 2019. 11. 16. 20:00
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 오늘은 백준의 2869번 문제인 달팽이는 올라가고 싶다에 대해 알아보도록 하겠습니다. 접근 방법 문제 분류 자체가 이진탐색이긴 합니다만, 그걸 활용하기 위해서는 이진탐색을 이용한 풀이 로직을 이해해야 합니다.. 그런데 저는 이해가 잘 안되더라구요..ㅎㅎ 차라리 일반항으로 바로 찾아버리는게 낫다고 생각했습니다. 따라서 제가 생각하는 키 포인트는 다음과 같습니다. 달팽이는 요구하는 높이에 다다르면 더이상 미끄러지지 않는다. 즉, 높이를 기록한 배열에서 밤에 미끄러진 결과를 반영한 높이를 기록하는게 아니라, 그 날 최대로 올라간 높이를 기록해야 합니다. 일반항 : 낮과 밤에 정해진 만큼 올라가고 내려가기 때문에, 높이를 기록한 배열은..
-
[BJ] 2805 - 나무 자르기programing/Algorithm 2019. 11. 9. 21:37
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 이번 포스트에서는 백준 2085번 문제인 나무 자르기에 대해 알아보겠습니다. 접근 방법 해당 문제는 자른 후 남는 나무의 길이가 최소가 되도록 나무들을 자르는 문제입니다. 따라서 절단 높이는 최대한 높아야 합니다. 단순하게 제일 높은 나무 높이부터 0까지 1cm단위로 테스트해봐도 됩니다만.. 문제는 역시 시간복잡도입니다. 따라서, 탐색에서 시간복잡도가 $n\log{n}$인 이진 탐색을 사용합니다. 제가 생각하는 키 포인트들은 다음과 같습니다. 이진 탐색 : divide and qonquer를 이용한 탐색입니다. 대표적으로는 병합 정렬(merge sort), 퀵 정렬(quick sort)이 있습니다. 재귀 : 이진 탐색이라면 자연..