알고리즘

heapq 라이브러리에 대해서 공부하기 전에 우선 heap에 대해 간략히 정리하자면, heap은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기반으로 한 자료구조이다. 최소 힙은 가장 부모 노드의 최솟값을 가지고, 자식 노드로 갈수록 값이 커지는 특성이 있다. 힙 자료구조의 장점은 힙 자체로 정렬이 되며 값을 추가, 삭제할 때도 정렬이 유지된다는 장점이 있다. 싸피교육때 힙 자료구조를 배우고 파이썬으로 구현은 해보았지만, heap을 이용하여 다양한 문제를 풀어보지는 못하여 heap을 꼭 알아야 하나?라는 생각에 공부를 미루고 있었는데, 다익스트라와 힙을 활용한 알고리즘 풀이 방식이 플로이드-와샬 알고리즘이 풀어내지 못한 문제를 거뜬히 풀어내는 것을 보고 힙도 공부할 필요가..

플로이드 와샬 알고리즘을 공부하면서, 백준에서 플로이드-와샬의 기본 문제를 풀어보았다. 처음 플로이드 와샬 알고리즘을 들어보았을 때 엄청 어려운 알고리즘일거같다고 느꼈지만 막상 코드 자체는 그리 복잡하지 않았다. 다익스트라처럼 최단거리를 알려주는 알고리즘인데, 다익스트라는 한점에서 다른 한 점까지의 최단거리를 구하는 알고리즘이지만 플로이드는 모든 점에서 모든 점까지의 최단거리를 알 수 있다. 또 다른 차이점은 플로이드는 이전에 구한 최소비용과 새로 구한 최소비용을 비교하면서 갱신하는 DP형태의 알고리즘이라면, 다익스트라 알고리즘은 최소비용인 경우만 갱신하는 그리디 형태의 알고리즘이다. ( 플로이드 알고리즘을 공부하면서 내가 아직 다익스트라와 힙 자료구조에 대해서도 공부가 부족함을 깨달았다.) 플로이드 와..

이 문제를 처음 본 순간 든 생각은 이게 왜 '이분 탐색'이지? 였다. 다른 방법으로 풀까 했지만 n이 1,000,000,000을 for 문으로 돌릴 자신이 없었기 때문에 결국 다른 풀이들을 레퍼런스 했다. 다른 블로그 글들을 보면서 내가 아직 이분 탐색을 제대로 이해하지못했고, 아직 많이 부족하다는 것을 깨달았다. 우선, 다른 풀이들을 보면서 나 스스로 한번 문제와 이분탐색을 정리해보았다. 이진 탐색은 정렬된 배열에서 내가 원하는 값을 가지고 있는 배열의 인덱스를 찾는 기법이다 즉, 이문제에서 우리가 찾고 싶은 것은 총 소요되는 최소 시간이기 때문에 시간을 인덱스로 생각해야 한다. 시간을 인덱스라고 생각하고 이분 탐색하듯이 LEFT와 RIGHT값을 찾아야 하는데, 시간은 무한하기 때문에 우리가 범위를 ..

나에게는 너무 어려운 구현 그 자체인 문제였다. 구현 문제를 풀 때, 항상 고민인 점이 '시간, 메모리 통과할까?'이다. 내가 아직 경험이 부족하여 시간에 대한 정확한 확신이 없어서 이런 일이 있는 것 같다. 이 문제를 풀 때도 손 코딩 단계에서 이렇게 해야 하나? 아니면 이렇게? 이 고민으로 한 시간은 족히 소모한 것 같다. 결국 손 코딩을 완전히 끝내지 말고 일단 그냥 풀어보자는 마음으로 키보드를 쳐봤는데 막상 치기 시작하니 금방 푼 느낌도 드는 것 같다. 문제를 간략히 설명하자면, 말그대로 재원이가 만든 게임을 진행하고, 게임 진행조건을 도달했을 때 소요된 턴을 출력하는 문제이다. 결국은, 문제에서 설명하는 게임을 구현해내는 문제이다. 게임 규칙은 문제에서 읽어보는 것이 가장 좋을 것 같고, 결국 ..

핑계지만 한동안 프로젝트를 진행한다고 알고리즘 문제를 풀지 못하였다. 아무래도 처음 진행해보는 프로젝트이다 보니 하루에 어느 정도 해야지라는 양을 가늠하지 못하고, 시간이 있을 때마다 프로젝트에 몰두한다고 나의 다른 스케줄을 잘 진행하지 못한 것 같다. 앞으로 프로젝트를 할 때는 프로젝트도 중요하지만 시간 배분을 조금 더 유동적으로 해봐야겠다. 문제 얘기를 해보자면 이번에 푼 문제는 Watering the Fields이다. 문제가 영어버전 밖에 없지만, 다행히 문제 길이도 길지 않고, 문제에서 하는 얘기도 딱 보이기 때문에 영어가 약한 나에게도 해석상에 큰 문제는 없었다. 문제 줄거리는 농부가 물을 받아놓기 위해 파이프를 연결해놓아야 한다는 내용이지만, 결국에는 문제에서 모든 파이프의 좌표가 주어지고, ..

오랜만에 백준을 풀었고, 오랜만에 시간 초과 늪에 빠졌다. 최대한 시간을 줄여 파이썬까지 통과해보고 싶었지만 아직 내실력에서는 Pypy통과가 최선이었다. 문제를 간략히 설명하자면, 존이 N개의 동영상 중 N-1개의 동영상 쌍을 만들어서 유사도를 구해놓았다. 동영상 쌍을 만들 때 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 만들었을 때, Q개의 질문(v번의 동영상과 유사도가 k이상인 동영상의 개수)의 답을 구하는 문제이다. 문제에서 가장 큰 힌트부분은 한 동영상에서 한 동영상으로 가는 경로가 반드시 하나인 점. 즉, 방향이 존재하지 않고 사이클이 없는 그래프인 트리구조로 만들 수 있다는 점이다. 나는 위 점에서 힌트를 얻어 딕셔너리를 활용하여 트리를 만들었고, 이를 이용한 BFS탐색..

달팽이 문제는 많이 기억에 남는 문제이다. 왜냐하면 싸피를 시작하며 처음 알고리즘을 알게 되었고, 알고리즘 스터디에서 문제를 풀 때, 나에게 절망을 준 문제 중 하나였기 때문이다. 그때 다른 분들이 조건을 찾아서 풀거나 delta기법을 이용하여 문제를 풀 때, 어떻게 그렇게 구현하지 생각하며 부러워했던 기억이 난다. 그래도 이제는 나도 그때 달팽이 문제보다 조금 어려워진 문제를 구현으로 바로 풀어내는 것을 보니 성장했다는 것이 체감되는 아주 기분 좋은 문제였다. 문제는 아마 알고리즘 문제를 풀어 보는 모든 사람들이 익숙한 문제일 것이다. 이문제가 다른점은 달팽이가 삼각형 모양으로 움직인다는 것이다. 문제를 보면 1번위치에서 출발해서 왼쪽 아래 꼭짓점, 오른쪽 아래 꼭짓점, 다시 위쪽 꼭짓점 방향으로 달팽..

사실 이 문제는 자신 있게 풀었다가 완전히 오답이 나서 내 접근 자체가 틀렸단 걸 느껴 질문하기를 통해 힌트를 보고 풀었다. 질문하기를 보니 나처럼 접근했다가 답을 틀린 사람이 많았던 것 같다. 우선 문제를 간단히 설명하자면 다단계 조직원들의 수입을 리스트로 반환하는 문제이다. 이런 식으로 다단계 조직원들의 구조가 이루어져 있을 때, 자신이 개당 100원짜리의 칫솔을 판매하거나 자신의 자식이(추천받은 사람) 수익을 얻어 자신이 수익을 받는다면 90%를 내가 가지고 10%를 자신의 부모(추천인)에게 보내주어야 한다. 여기서 나는 두가지 실수를 하였다. 1. 모든 자식노드의 수입이 정해진 후 자신의 수입을 정한다(트리의 후위 순회) -> 틀린 이유 : 수입을 받을 때마다 부모에게 보내주어야 함(10%를 보내..