PS/Algorithm

코딩테스트를 위한 Swift 필수 자료구조 구현하기

코딩테스트는 취업에 있어 꼭 필요한 과정 중 하나입니다. 저도 익숙하게 사용했던 Python 언어를 활용하여 코딩 테스트를 준비했었는데요. 하지만 최근에 점차 많은 회사들이 포지션에 맞게 코딩테스트 언어 제한을 두었습니다. Swift는 Type-Safe 언어이고 문법도 간결해서 iOS 개발할 때에 무척 편리하게 사용하고 있습니다. 하지만 Python과 달리 별도의 Built-in 자료 구조가 없어서 코딩테스트에 필요한 부분은 직접 구현해야 합니다. 이번 게시글에서는 Swift를 통해 필요한 자료구조를 직접 구현하는 방법에 대해 기술하고자 합니다. Queue Queue 는 FIFO 방식으로 동작하는 자료구조입니다. 프린터, 작업 대기열 같은 문제에 활용되고 더 나아가 SPFA 같은 최단 거리 알고리즘에 사..

네이버 체험형 인턴 코딩테스트 후기

큰 기대를 하지 않고 지원했던터라 코딩테스트에 대한 준비가 되어 있지 않았다. 😢 그래서 합격 메일을 받고 평소에 부족했던 알고리즘 파트을 중점적으로 복습했다. (DP, DFS/BFS, Greedy...) 코딩테스트는 Codility 로 치루어졌는데, 다른 코딩테스트 사이트와 다르게 모든 문제들이 영어로 되어있고, 테스트 케이스가 무척 제한적이였다. 따라서 입력 값 범위를 보고 자체적인 케이스를 테스트하는 것이 중요했다. ( 문제에 따라 빈 배열이나, MIN ~ MAX 값이 들어올 때 예외 처리 해주기 ) 그리고 시간 복잡도 영역도 점수에 큰 영향을 끼친다. 언어, 실행 환경에 따라 다르지만 보통 아래와 같은 INPUT 범위를 통해 사용할 수 있는 알고리즘을 추측해야 한다. 제한 시간이 1초 기준으로 입..

이분 탐색 ( Parametric Search, lower, upper Bound / Swift ) - 2

파라메트릭서치(Parametric Search) 조건에서 최소, 최대를 찾는 문제에서 결정 문제로 변경하여 탐색하는 알고리즘을 말합니다. 이전까지는 정렬되어 있는 배열에서 해당 값이 있는지 파악했지만, 파라메트릭서치에서는 조건이 가질 수 있는 최소, 최대 값을 결정하고 (start, end) 해당 하는 값이 조건에 만족하는지 파악하여, 구간별로 탐색하는 것을 의미합니다. 예시 문제 김OO 은 게임 승률이 50% 가 넘으려면 몇 판을 해야하는지 궁금합니다. 무조건 게임은 승리한다고 가정했을 때, 최소한으로 몇판을 이겨야 하는지 승수를 구하시오. ( 단 비기는 경우는 없다고 가정하고, 답은 Int 범위를 넘지 않는다. ) 총 게임 횟수: 50, 승리 : 1, 패배 : 49 위 경우에 일반적으로 게임 횟수 1..

이분 탐색 ( Binary Search / Swift ) - 1

이분 탐색은 정렬된 데이터에서 값을 빠르게 찾는 방법 중 하나입니다. 일반적인 방법으로 위와 같은 Int 배열에서 "9" 를 찾는다고 가정하면, O(n) 시간 복잡도를 가집니다. 이분 탐색은 첫 인덱스가 아닌 중간부터 값을 비교하여 탐색할 구간을 정합니다. start, mid, end 가 기준점이 되어 구간을 선택하고, 필요 없는 구간은 탐색하지 않기 때문에, O(logN) 의 시간 복잡도를 가집니다. 주의점으로는 "정렬되어 있는 데이터" 에서만 사용이 가능하다는 점입니다. 비정렬된 상태에서 사용될 때 정렬 알고리즘 + 이분 탐색 방법이 더 효율적일지, 혹은 선형 탐색 알고리즘이 더 나을지는 개발자의 판단이 필요합니다. 다음으로는 이분 탐색의 활용으로 파라메트릭서치(Parametric Search) 와 ..