이진탐색 (Binary Search) 탐색 순차 탐색 (Sequential Search): 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 구현이 쉽고 시간이 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다. 리스트 내에서 특정한 값의 원소가 있는지 확인하거나 특정한 값을 가지는 원소의 개수를 세는 count() 메소드를 사용할 때도 내부적으로 순차 탐색이 수행된다. 최악의 경우 시간 복잡도: O(N) 이진 탐색 (Binary Saerch): 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하기 때문에 데이터를 매우 빠르게 찾을 수 있다는 특징이 있다. 탐색 시 위치를 나타내는 변..
정렬(Sort) 개요 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램 작성 시에 가장 많이 사용되는 알고리즘 중 하나이다. 예를 들어 이진 탐색을 하기 위해서는 전처리 과정으로 정렬이 필요하다. 선택정렬 데이터가 무작위로 여러 개 있을 때 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 방식이다. 가장 원식적인 방법으로 매번 가장 작은 것을 선택한다는 의미에서 선택 정렬 알고리즘이라고 한다. 선택 정렬의 시간 복잡도는 O(N²)이다. 소스코드는 다음과 같다. imp..
깊이 우선 탐색과 너비 우선 탐색 (DFS & BFS) 탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다. 두 알고리즘을 이해하기 위해서는 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다. 깊이 우선 탐색(DFS, Depth First Search): 동작 원리: 스택 구현 방법: 재귀 함수 사용 탐색 순서: 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5 (1부터 시작하고 작은 순서부터 탐색한다고 가정) 수행 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드..
구현 문제 개요 코딩 테스트에서 구현은 머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 흔히 문제 해결 분야에서는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미하는데 피지컬을 요구하는 문제라고도 할 수 있다. 여기서 피지컬이란 흔히 개발할 때 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도가 빠른 사람을 보고 피지컬이 좋다고 한다. 구현하기 어려운 문제들로는 아래와 같은 것들이 있는데 대체로 사소한 조건 설정이 많은 문제일 수록 코드로 구현하기가 까다롭다. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 특정 소수점 자리까지 출력해야하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는 파싱 문제 이 책에서는 완전 탐색, 시뮬레이션 유형을 모..
그리디 알고리즘(Greedy Algorithm) 개요 greedy 형용사 - 1. 탐욕스러운 2.욕심 많은 사전 상 Greedy는 위와 같은 의미를 가지고 있는 영어 단어이다. 그렇다면 그리디 알고리즘은 무엇일까? 국내에서 탐욕법, 욕심쟁이 알고리즘이라고도 부르는 그리디 알고리즘은 이름에서 유출할 수 있듯이 어떤 문제에 대해서 탐욕적으로 즉 "현재 상황에서 지금 당장 좋은 것만 고르는 방법"으로 문제를 해결하는 방법이다. 코딩테스트에서 만날 경우 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형 다익스트라 알고리즘의 경우 그리디 알고리즘이지만 암기가 필요한 유형 문제 출제 유형의 폭이 넓기 때문에 특이 케이스를 제외하고는 단수 암기를 통해 모든 문제를 대체하긴 어려움 창의력(문제를 풀기 위..
