본문 바로가기

코딩일기/알고리즘75

[프로그래머스 : 레벨 4] 징검다리 : 이분탐색(Java) 이번 문제는 지난번 이분탐색 문제 풀때와는 다르게 방법이 약간 생각이 났지만 자세히는 어떻게 해야할지 몰라 결국 답지를 보게 되었다. 문제부터 살펴보자. 문제 설명 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다. 제거한 바위의 위치각 바위 사이의 거리거리의 최솟값 [21, 17] [2, 9, 3, 11] 2 [2, 21] [11, 3, 3, 8] 3 [2, 11] [14, 3, 4, 4] 3 [11, 21] [2, 12, 3.. 2021. 7. 2.
[프로그래머스 : 레벨3] 입국심사 : 이분탐색(Java) 이번 문제는 사실 문제를 보고 어떻게 풀어야 할지 감이 전혀 안잡혔다. 사실 안잡힌건 아니고 감은 잡혔지만 내가 생각한 방식으로 문제를 풀었다간 시간복잡도고 O(n)으로 나와서 제한사항에 나와 있는 엄청난 데이터를 상대로 하기엔 런아웃 에러가 날게 뻔했다. 그래서 어떻게 풀어야 할지 몰라 답지를 봤다. 일단 문제부터 살펴보자. 문제 설명 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수.. 2021. 6. 30.
[자료구조] 이분(이진)탐색 트리 구현 (Java) 이분 탐색트리란? 보통 우리가 어떤 걸 탐색하기 위해서 list 혹은 배열에 안에 있는것들을 순차적으로 방문하면서 데이터를 찾았다. 하지만 이 방법은 데이터의 양이 많을때 해당 방법을 사용하면 시간 복잡도가 커질수가 있다. 하지만 이분 탐색은 정렬되어 있는 정렬되어 있는 리스트에서 탐색 범위를 절반씩 감소시키는것이다. 따라서 데이터 가 많은 곳에서의 특정 데이터를 빠르게 검색하려면 이진 탐색을 사용하는것이 맞다. 하지만 위에서 언급했듯이 정렬되어 있는 리스트에서만 사용할수 있기 때문에 특정 상황에서는 사용하지 못할수도 있다. 이분 탐색의 알고리즘의 과정 상황 : 배열 {0,1,2,3,4,5,6,7,8,9} 에서 숫자 2를 찾으려고 한다. 1. 정렬된 배열(혹은 list)에서 start와 end index.. 2021. 6. 29.
[프로그래머스 : 레벨3] 여행경로 : DFS(Java) 이번문제는 여러 테스트케이스에서 생각을 하지 못해서 문제를 풀지 못했다. 그래서 결국 답지를 봤다. 일단 문제부터 살펴보자. 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 r.. 2021. 6. 22.

티스토리툴바