백준

이분 탐색 문제이다. 이 문제는 총 M대의 놀이기구가 있을 때, N명이 순서대로 놀이기구를 탈 때, 마지막 사람이 타게 되는 놀이기구의 인덱스를 맞추는 문제이다. 문제를 봤을 때, 프로그래머스의 입국심사와 비슷한 느낌이 있었지만, 차이점이 있다고 느꼈고 나는 입국심사를 푼 테크닉을 바탕으로 약간의 아이디어를 추가하여 이문제를 풀었다. 이문제는 N명의 사람은 빈 놀이기구에 순서대로 들어가고, 각 놀이기구 마다 소요되는 시간이 다르다. 여기서 조심해야 할 점은 입국심사와는 다르게 사람들이 최소 시간을 위해 놀이기구 선택을 하는 것이 아닌, 여러 개가 비어있다면 단순히 인덱스가 작은 놀이기구부터 탄다는 점이다. 내가 문제를 푼 아이디어는 아래와 같다. 1. N-M명을 태울 때는 최소 시간을 위해 놀이기구를 선..

이분 탐색 문제이다. 이 문제는 문제 설명 자체도 간단하지만 더 간략히 정리하자면, N*N크기의 이차원 배열에서 각 값은 row*col의 값을 가질 때(최소 인덱스를 1로 둠) T번째 수의 값을 구하는 것이다. 결국 T번째 수의 값을 이진탐색으로 찾아낼 수 있는 가를 구하는 문제이다. 역시 중간값 검증을 하여, 지금 탐색하고 있는 수가 몇 번째 수인지 찾아내는 것이 문제를 푸는 포인트인 것 같다. 1 2 3 2 4 6 3 6 9 N이 3인 이차원 배열은 이렇게 되고, 마치 구구단과 비슷한 모양이 된다. 이 배열에서 6은 몇번째로 큰 수인지 확인하기 위해서는 어떻게 해야 할까? 1행에서 6보다 작은 수는 3개, 2행에서 6보다 작은 수 역시 3개, 3행에서 6보다 작은 수는 2개로 총 8번째로 큰 수이다...

이분 탐색 문제이다. 이전 문제들과 마찬가지로 중간값 검증을 어떻게 할 것인지, 범위를 어떻게 할지 가장 중요했다. 이분 탐색으로 내가 찾고 싶은 값은 만들어진 구간의 최소 값이다. 즉 중앙값을 기준으로 구간을 만들 때 문제에서 원하는 구간 개수가 가능한지 검증한 후, 더 적게 나온다면 문제에서 원하는 구간 개수를 만들 수 있다는 뜻이므로, 최솟값을 찾기 위해 중간값을 줄이고, 더 많이 나온다면 중간값을 올리는 과정으로 문제를 해결하였다. 다시 정리하자면, 내가 원하는 값(중앙값)으로 구간을 나눌 때 M개 이하로 만들 수 있다면, 내가 정한 값으로 M개의 배열을 만들 수 있다는 것을 확실히 인지하여야 한다. 이를 이용하여 중앙값을 검증할 때, 내가 지정한 중앙값으로 배열의 최소 최대의 최대 차를 만들 수..

아직 각 알고리즘에 대한 이해 및 활용능력이 부족한 것 같아서, 기출에 나온 구현 문제보다는 알고리즘 연습을 할 것 같다. 첫 번째 알고리즘은 바로 이분 탐색이다. 이분 탐색은 학교 예제에서도 다뤄본 적 있는 알고리즘이라 비교적 쉽다고 생각했었는데 최근 프로그래머스 중 이분 탐색 문제(입국심사)를 풀어보고 정말 쉬운 게 없구나 느끼게 됐다. 사실 모든 알고리즘 문제들이 그렇겠지만, 이 문제를 어떤 알고리즘으로 풀지?라는 생각만 잡히게 된다면 어느 정도 쉽게 풀 수 있다. 특히 나는 알고리즘을 연습할 목적으로 백준의 이분 탐색 문제집을 풀었기 때문에 어떤 알고리즘으로 풀지라는 고민의 시간 없이 문제를 풀었기 때문에 그나마 쉽게 풀 수 있었다. 문제에 대해 설명하자면, 총 N개의 강의를 녹화할 때, M장의 ..

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

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

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

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