알고리즘 풀이/프로그래머스 (8) 썸네일형 리스트형 이분탐색 > 징검다리 https://www.welcomekakao.com/learn/courses/30/lessons/43236 이 문제도 아직 나한텐 어려운 것 같다.. 또 다른사람의 풀이를 보고나서야 답을 구할 수 있었음 ㅜㅜ 문제를 푸는 로직은 아래와 같다. 1. 이분탐색 문제에 맞게 구하려는 값의 최솟값과 최댓값을 정해야 한다. 구하려는 값은 n개만큼의 바위를 제거한 뒤에 남는 바위들 간의 거리의 최솟값중에 최댓값을 구하는 것이다. 즉, 바위간의 거리를 기준으로 삼아야하는 문제이다. 2. 바위간의 거리 중 최솟값은 1이며, 최댓값은 주어진 변수인 distance 로 설정하였다. 3. 중간값인 mid 를 구한다음에 바위의 위치가 담긴 배열을 순회하며 구한 mid 값보다 이전 바위의 거리가 작으면 제거하고, 같거나 크다면.. 이분탐색 > 입국심사 https://www.welcomekakao.com/learn/courses/30/lessons/43238# 이 문제는 결국엔 다른사람의 답을 보고서 이해하여 짠 코드이고, 문제를 푸는 로직은 아래와 같다. 1. 이분 탐색을 하기위한 최솟값과 최댓값을 구해야한다. 문제에 보면 입국심사를 기다리는 인원은 1명이상, 심사관이 소모하는 시간은 1분이상이므로 최솟값은 1이다. 최댓값은 가장 오래걸리는 심사대에서 n명이 모두 심사를 받는 경우이다. 2. 특정 시간에서 몇명이 심사를 받을 수 있는 지 계산하면 된다. 이를 최솟값부터 최대값까지 그대로 계산한다면 O(N)의 시간이 걸리지만, 이분 탐색을 실시하면 O(logN) 에 정답을 찾을 수 있다. 3. 이분 탐색을 실시하면서 3-1. mid 값의 시간일 때, 몇.. 스택/큐 - 주식가격 https://www.welcomekakao.com/learn/courses/30/lessons/42584 사실 문제이해가 제일 오래걸렸다... 1초, 2초 시점은 이해가 되지만 3초 시점이 왜 1이지..? 국어능력도 필요한 문제인 것 같다. 어쨌든 위 문제의 풀이방법은 아래와 같다. 1. 2중 for 문 중 첫번째 for 문은 처음부터 끝까지 주식의 가격을 순회한다. 2. 두번째 for 문에서 다음 날 가격 끝까지 주식의 가격을 순회한다. 3. 두번째 for 문에서 가격하락이 발생한 날을 찾는다. 만약 가격이 하락했다면 두 주식의 index 차이를 계산하여 정답에 push 하고, 가격하락이 되었다는 flag 를 true 로 설정해준다. 4. 3번 case 에 해당되지 않는다면(주식이 하락하지 않았다면).. 스택/큐 - 기능개발 https://www.welcomekakao.com/learn/courses/30/lessons/42586 문제를 푸는 로직은 아래와 같다. 1. 각 기능의 완료기간을 계산하고 queue 에 넣는다. (11~20 line) 이때 주의해야할 점은 딱 100이 되는 순간이 완료기간이므로 나머지 값 유/무 여부를 따져야한다. (15~18 line) 2. queue 를 순회하기 이전에 가장 맨앞의 작업이 완료되는 기간을 미리 저장해둔다. (22 line) 3. 이제 queue 순회하면서 작업 완료기간을 비교한다. 만약, 이전 작업보다 완료기간이 작으면 작업의 갯수를 증가시키고 (31 line) 이전 작업보다 완료기간이 큰 작업이 발견되면 작업 완료기간을 갱신하며 작업의 갯수도 1로 갱신한다. (26 ~29 li.. 스택/큐 - 탑 https://www.welcomekakao.com/learn/courses/30/lessons/42588 위 문제를 풀기 위해 아래 로직을 구현하였다. 그런데, 해당 문제의 범주가 스택/탑인데.. 내가 푼 방법은 사실 억지로 스택을 쓴 것 뿐이지 2중 for 문을 사용한 것과는 다를 것이 없다. 다른 사람의 코드를 아직 보진않았지만, 스택을 어떻게 써야 하는 문제인지 파악해보고 싶다. 1. 탑 index 와 탑의 높이를 stack 에 저장한다. 2. 저장 된 stack 을 pop 하면서 자신보다 앞에 있는 탑과 높이를 비교하며, 자신보다 높은 탑을 발견할 시 answer 에 push 3. answer 에는 정답이 거꾸로 들어가있으므로 reverse 연산을 수행 1 2 3 4 5 6 7 8 9 10 11.. 스택/큐 - 다리를 지나는 트럭 https://www.welcomekakao.com/learn/courses/30/lessons/42583 위 문제를 풀기위해 특별한 로직은 없는 것 같고, 아래에 코드풀이와 염두해두어야 할 점들을 적어놓았다. 1. 다리를 건너는 트럭을 계산하기 전에 다리를 지나는 트럭을 계산하여야한다. (예제 경과시간 3초를 보고 알 수 있듯이 다리를 지난 트럭을 먼저 계산한 후에, 다리를 건너는 트럭을 계산해야 한다.) 2. 다리를 오른 후 다리를 지날 때까지 시간의 흐름을 어떻게 계산해야하는 지 고민을 했었는 데, 27 line 의 계산을 떠올렸다. 3. 다리를 건너는 트럭을 구할 땐, 현재무게, 올라 탈 트럭의 무게와 다리가 견딜 수 있는 무게를 잘 연산하면 된다 (36 line ). 그리고 2번째 비교인 다리의.. 스택/큐 - 프린터 https://www.welcomekakao.com/learn/courses/30/lessons/42587# 위 문제를 푸는 데 아래 로직을 구현하였다. 1. queue (13 line) 에 프린터 대기목록을 저장한다. 2. 우선순위 소팅이 적용되지 않은 queue 를 순회하며, 최대 우선순위를 가진 프린터를 찾고 정보를 저장한다. 3. 2번에서 찾은 정보를 기반으로 우선순위 정렬 (35~40 line)을 하는 데, 이 정보를 vector (20 line) 에 저장한다. 그리고 위 처럼 문제를 풀지 않고, maxHeap 을 사용해도 문제를 풀 수 있을 것 같다. 나중에 시간되면 해보기로.. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2.. 스택/큐 - 쇠막대기 https://www.welcomekakao.com/learn/courses/30/lessons/42585 위 문제를 푸는 로직은 다음과 같다. 1. 여는 괄호( '(' ) 는 레이저이든 막대이든 상관없이 스택에 넣는다. 2. 닫는 괄호( ')' )는 레이저이거나 막대기의 끝을 나타낸다. 그렇기 때문에 2가지로 로직으로 나뉠 수 있다. 2-1. 바로 이전 괄호가 닫는괄호일 경우, 막대기를 나타내는 데 이 경우엔 막대기의 끝점을 나타내기 때문에 마지막에 잘린 부분을 정답에 더해준다. (18 line) 2-2. 바로 이전 괄호가 닫는괄호가 아닌 경우 즉, 여는 괄호인 경우엔 레이저를 나타내므로 현재 스택에는 끝점을 만나지 않은 막대기들만 남아있으므로 스택의 크기만큼 정답에 더해준다. (19 line) 1 2.. 이전 1 다음