코딩 버릇 여든까지 간다

떡볶이 떡 만들기 문제 풀이 문제 해결 아이디어 적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복해서 조정하면 된다. ‘현재 이 높이로 자르면 조건을 만족할 수 있는가? (최소한 M만큼의 떡을 얻을 수 있는가?)'를 확인한 뒤에 조건의 만족 여부(예 혹은 아니오)에 따라서 탐색 범위를 좁혀서 해결할 수 있다. M만큼의 떡을 얻을 수 없다면 높이값을 더 낮춰서 더 많은 양의 떡이 잘려나가도록 만들 수 있다. 매 높이마다 조건의 만족 여부를 확인해서 조건에 따라서 탐색 범위를 좁히는 방법으로 이진 탐색을 수행하여 최적의 해를 구할 수 있다. 절단기의 높이는 0부터 10억까지의 정수 중 하나이다. 이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 한다. (선형 탐색으로 시간 초과 판정..

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

선택 정렬과 기본 정렬 라이브러리 수행 시간 비교 from random import randint import time 정렬을 수행시킬 목적으로 랜덤한 10000개의 데이터를 이용한다. 파이썬 라이브러리 중 randint 함수를 사용한다. array = [] for _ in range(10000): array 함수에 총 100개의 데이터가 랜덤하게 1부터 100 사이의 값으로 담길 수 있도록 한다. start_time =time.time() ... end_time = time.time() 수행시간을 측정하기 위해 start time과 end time 변수가 실제 알고리즘 바깥쪽에 서론되어 있다. (선택 정렬 코드가 이들의 안쪽에 있다.) 선택 정렬을 수행한 결과를 출력하도록 만들려면 끝 시간에서 시작 시..

계수 정렬이란? (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가 있다. 코딩 테스트에서 매우 자주 등장하는 유형이다 (⭐️⭐️⭐️⭐️⭐️ 반드시 숙지하도록) 스택 자료구조 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. 예를 들어, 여러 개의 박스를 쌓을 때 (스택하고자 할 때) 아래쪽에서부터 차례대로 박스를 올려놓는다. 쌓아 올린 박스를 다시 내려놓고자 할 때는 가장 위쪽에 있는 박스부터 차례대로 ..