코딩 버릇 여든까지 간다

이진 탐색이란? 정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색할 수 있도록 해주는 탐색 알고리즘이다. 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이다. 가장 기본적인 형태의 데이터 탐색 알고리즘이다. 단순히 데이터를 하나씩 확인한다. 리스트에서 특정 데이터의 존재 여부를 검사할 때 별 다른 말이 없다면 기본적으로 순차 탐색을 이용한다. 이진 탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 리스트가 정렬되어 있을 때 사용 가능하다. 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 이진 탐색 동작 예시 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾아보자. 전체 탐색 범위에서 값이..

계수 정렬이란? (Counting Sort) 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다. 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다. 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장한다. 예시 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다. 정렬할 데이터: 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 배열에서 특정한 인덱스에 접근할 때 알고리즘 상으로 상수시간에 접근 가능하다고 보기 때문에 데이터를 하나씩 확인하며, 데이터와 동일한 인덱스에 카운트 값을 1씩 증가시키면서 해당 데이터가 몇 번 등장했는지 확인할 수..

퀵 정렬이란? 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다. 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다. 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다. 현재 피벗의 값은 ‘5’이다. 왼쪽부터 ‘5’보다 큰 데이터를 선택하므로 ‘7’이 선택된다. 오른쪽부터 ‘5’보다 작은 데이터를 선택하므로 ‘4’가 선택된다. 이 두 데이터의 위치를 서로 변경한다. ‘4’와 ‘7’ 값이 변경되었다. 현재 피벗의 값은 ‘5’이다. 왼쪽부터 ‘5’보다 큰 데이터인 ‘9’가 선택되고, 오른쪽부터 ‘5’보다 작은 데이터인 ‘2’가 선택된다. 두..

정렬(Sorting)이란? 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. (데이터가 적을 때, 데이터는 많지만 특정한 범위가 정해져 있을 때) 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 처리되지 않은 데이터 중 가장 작은 ‘0’을 선택하여 가장 앞의 ‘7’과 바꾼다. 처리된 데이터 ‘0’을 제외한 나머지 처리되지 않은 데이터 중 가장 작은 ‘1’을 선택하여 가장 앞의 ‘5’와 바꾼다. 마찬가지로 가장 작은 데이터 ‘2’와 ‘9’를 바꿔준다. 위 과정을 반복하여 다음과 같이 정렬을 한다. 동작 과정을 살펴보면, 탐색 범위는 반복할 때 마다 줄어들게 되고 ..

문제 1. 음료수 얼려 먹기 문제 해결 아이디어 이 문제는 연결 요소 찾기(connected component) 문제이다. DFS 혹은 BFS로 해결할 수 있으며 연결 요소 개수가 몇 개 인지 구하면 되는 문제이다. 얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링할 수 있다. 다음과 같이 3 X 3 크기의 얼음 틀이 있다고 가정해보자. 이와 같이 그래프 형태로 모델링을 해보면 상하좌우로 연결되어 있는 위치들은 서로 인접한 노드 형태로 표현할 수 있다. 특정 기점에서 DFS 혹은 BFS를 수행해서 이동 가능한 모든 경로에 대해서 방문처리를 진행할 수 있다. (왼쪽 상단에 있는 0에서 시작된다면 인접한 0 노드 2개가 방문처리 된다) 1인 노드는 이..

DFS (Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. (즉, 매번 최상단 노드를 기준으로 방문하지 않은 인접노드가 있으면 인접한 노드로 방문을 수행한다.) 2번 과정을 수행할 수 없을 때까지 반복한다. DFS 동작 예시 이 그래프는 무방향 그래프이다. 방문 기준은 번호가 낮은 인접 노드부터이다. 시작 노드는 1이..

재귀함수(Recursive Function)란? 자기 자신을 다시 호출하는 함수를 의미한다. 재귀함수는 실질적인 dfs를 실질적으로 구현하고자 할 때 자주 사용하는 방법이다. 단순한 형태의 재귀 함수의 예제를 살펴보자. ‘재귀 함수를 호출합니다.’ 라는 문자열을 무한히 출력하고자 할 때 어느 정도 출력하다가 최대 재귀 깊이 초과 메세지가 출력된다. 재귀 함수의 종료 조건 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다. 의도적으로 무한 루프를 이용하는 것이 아니라면 반드시 종료 조건을 명시하여 프로그램이 정해진 값을 반환할 수 있도록 만들어야 한다. 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있으므로 오류 발생 가능성이 있다. if i == 100:..

그래프 탐색 알고리즘: DFS/BFS 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 특정 조건에 맞는 데이터가 존재하는지, 존재한다면 어떤 위치에 존재하는지 등을 찾고자 하는 목적으로 다양한 탐색 알고리즘을 사용한다. 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다. 코딩 테스트에서 매우 자주 등장하는 유형이다 (⭐️⭐️⭐️⭐️⭐️ 반드시 숙지하도록) 스택 자료구조 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. 예를 들어, 여러 개의 박스를 쌓을 때 (스택하고자 할 때) 아래쪽에서부터 차례대로 박스를 올려놓는다. 쌓아 올린 박스를 다시 내려놓고자 할 때는 가장 위쪽에 있는 박스부터 차례대로 ..

문제 2. 시각 입력 조건: 첫째 줄에 정수 N이 입력된다. (0

구현이란? 머릿속에 있는 알고리즘과 생각을 소스코드로 바꾸는 과정이다. 아무리 알고리즘을 잘 세워도 실제 코드로 작성해서 프로그램으로 만들지 않으면 알고리즘은 동작하지 않는다. 알고리즘 문제는 곧 소스코드로 구현해야 하므로 구현 문제이다. 특정 문제를 구현 유형 문제라고 부를 때는 문제에서 요구하는 내용이 구현에 초점이 맞춰져 있거나 구현이 어려운 문제를 의미한다. 알고리즘 대회에서 구현 유형의 문제란? 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. 예를 들어, 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 알..