로그 남기기

Search Algorithm 이진 탐색에 앞서 순차 탐색에 대해 먼저 이해할 필요가 있다. Sequential Search 순차 탐색이란 리스트 안의 특정한 데이터를 찾기 위해 맨 앞에서부터 하나씩 확인하는 방법을 뜻한다. 이는 보통 정렬되어 있지 않은 리스트에서 많이 사용하는데, 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다. 이처럼 데이터 정렬 여부와 관계없이 항상 맨 앞에서부터 확인하기 때문에 시간복잡도는 O(N) 이다. Binary Search 반면 이진 탐색은 정렬된 데이터의 탐색 범위를 반씩 좁혀가며 확인한다. 시작점과 끝점, 중간점 3개의 변수를 사용하는데, 찾고자하는 데이터와 중간점 위치에 있는 데이터를 반복해서 비교한다. 한 번 확인할 때마다 확인하는 데이..

Dynamic Programming Algorithm 다이나믹 프로그래밍 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 기본적으로 아래의 조건을 만족할 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 이러한 조건을 만족하는 대표적인 문제로는 피보나치 수열이 있다. Top-down 피보나치 수열을 memoization 기법을 사용하여 해결해보자. 메모이제이션은 한 번 구한 결과를 메모리 공간에 저장해두고 같은 식을 다시 호출하면 저장해둔 결과를 그대로 가져오는 기법이다. 이렇듯 재귀 함수처럼 큰 문제를 해결하기 위해 작은 문제를 호출하는 것을 Top-down 방식이라고 한..

Sorting Algorithm 정렬은 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다. 정렬 알고리즘은 이진 탐색 의 전처리 과정이기도 하기 때문에 반드시 짚고 넘어가야 한다. 책에서는 다양한 정렬 알고리즘 중 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 언급했다. Selection sort 말 그대로 데이터를 선택해서 정렬하는 것이다. 오름차순 정렬을 하고자 할 때 전체 데이터에서 가장 작은 데이터를 맨 앞에 있는 데이터와 바꾸고, 그 다음으로 작은 데이터를 두 번째 데이터와 바꾸고… 이러한 연산을 반복하면 된다. 하지만 선택 정렬은 다른 정렬 알고리즘과 비교해 시간 복잡도가 커 비효율적이다. Insertion sort 삽입 정렬은 데이터를 하나씩 확인하며 필요할 때만 위치를 ..

탐색은 많은 양의 데이터 중 원하는 데이터를 찾는 과정으로 그래프나 트리 등의 자료구조에서 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있고, 이를 확실히 이해하려면 스택과 큐가 뭔지 알아야 한다. 스택과 큐의 핵심 함수는 삽입(push)과 삭제(pop)다. 따라서 항상 오버플로와 언더플로를 고려해야 한다. overflow : 저장 공간을 벗어나 데이터가 넘쳐흐르는 상황 underflow : 데이터가 들어 있지 않은 상태에서 삭제 연산을 수행하는 상황 Stack LIFO (Last In First Out) : 후입선출로 접시를 쌓는 모습을 연상하면 된다. 깨끗이 닦은 접시를 쌓아두면 맨 위 접시부터 사용한다. Queue FIFO (First In First Out) : 선입선출로 식당에 줄..

코딩 테스트에서 어떤 문제를 풀든 코드를 작성하는 과정은 필수기 때문에 구현은 모든 문제 유형을 포함하는 개념이라고 볼 수 있다. Implementation Algorithm 특히 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 를 구현 유형의 문제라고 본다. 알고리즘은 간단한데 코드가 굉장히 길어지는 문제, 문자열을 입력받아 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 등이 까다로운 구현 유형의 문제라고 할 수 있다. 저자는 이 책에서 완전 탐색과 시뮬레이션 두 개의 유형을 구현으로 묶었다. 완전 탐색 : 모든 경우의 수를 다 계산하는 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계식 차례대로 수행하는 방법 구현 알고리즘의 대표적인 예시인 상하좌우 문제를 살펴보자. 상하좌우 여행..

그리디 알고리즘은 단어 그대로 번역하여 탐욕 알고리즘으로도 소개된다. 탐욕적이라는 말이 무슨 뜻일까? Greedy Algorithm 그리디 알고리즘에서의 탐욕적이다 라는 말은 현재 상황에서 당장 좋은 것만 고르는 방법을 의미한다. 그래서 어떻게 보면 무식하게 문제를 푸는 방법이라고 볼 수 있다. 단지 매 순간마다 가장 좋아보이는 것을 선택하고, 이 선택이 나중에 어떠한 영향을 미칠지에 대해서는 전혀 고려하지 않는다. 코딩 테스트에서 나오는 그리디 알고리즘 문제들은 타 알고리즘과 비교했을 때 미리 외우고 있지 않아도 풀 수 있을 가능성이 높다고 한다. 하지만 문제 유형이 굉장히 다양하기 때문에 많은 유형을 접하면서 연습을 하는 것이 중요하다. 선택을 위한 기준 매 순간 좋은 것을 선택하기 위해서는 기준이 ..