로니의 개발 이야기

다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간의 효율성을 비약적으로 향상시키는 방법입니다. 이미 계산된 결과는 별도의 메모리 영역에 저장하여 필요할 때 꺼내서 사용하도록 합니다. 다이나믹 프로그래밍의 구현은 탑다운(Top-down), 보텀업(Bottom-up) 방식으로 구성됩니다. 다이나믹 프로그래밍은 동적 (실행되는 도중에를 의미한다) 계획법이라고도 부릅니다. 다이나믹 프로그래밍을 이용해서 문제를 해결할 때, 사용하는 배열 이름을 캐시(cahse), 메모(memo), 테이블(table), DP 혹은 D라고 설정합니다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 ..

이진 탐색과 순차 탐색 일단, 이진 탐색과 순차 탐색을 비교해봅시다. 종류 설명 이진 탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색은 이처럼 탐색 범위를 좁혀 나가기 때문에 순차 탐색보다 더 적은 시간 복잡도를 가질 수 있습니다. 이진 탐색 동작 예시 아래와 같이, 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 확인해보겠습니다. [Step 1] 시작점 : 0, 중간점 : 8, 끝점 : 18 (소수점 이하는 제거)로 지정할 수 있습니다. 찾고자 하는 값보다 중간점의 위치의 값이 크다..

퀵 정렬(Quick) : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 퀵 정렬의 특징 가장 많이 사용된다. 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 된다. 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다. 퀵 정렬 동작 예시 Step 0 : 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '9'가 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다. Step 1 : 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '0'이 선택..

삽입 정렬 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다. 삽입 정렬 과정 Step 0 : 정렬할 데이터를 준비한다. Step 1 : 첫 번째 데이터 '5'가 정렬되어 있다고 판단, 두 번째 데이터인 '1'이 '5'의 왼쪽이나 오른쪽으로 들어갈지 결정한다. 결과적으로 '5'의 왼쪽으로 '1'이 들어가게 된다. Step 2 : 이어서 '4' 가 어디로 들어갈지 판단한다. '4'는 '5'의 왼쪽인 두번째 위치로 들어갈 것이다. Step 3 : 이어서 '3'이 어디로 들어갈지 판단한다. '3'은 '5'의 왼쪽으로 이동, '4'의 왼쪽으로 이동을 통해서 다음과 같이 위치할 것이다. Step 4 : 마지막으로 '2'가 어디로 들어갈지 판단한다. '2'는 3번의 이동을 통해서 다음과 같이 '3'의 왼쪽..

1. 정렬 알고리즘? 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 데이터의 개수가 적을 때 데이터의 개수가 많으면서 범위가 한정되어 있을 때 이미 데이터가 정렬되어 있을 때 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 선택 정렬 과정 Step 0 : 정렬할 데이터를 준비한다. Step 1 : 처리되지 않은 데이터 중 가장 작은 '1' 을 선택해 가장 앞의 '5' 와 바꾼다. Step 2: 처리되지 않은 데이터 중 가장 작은 '2' 를 선택해 가장 앞의 '5' 와 바꾼다. Step 3: 처리되지 않은 데이터 중 가장 작은 '3' 을 선택해 가장 앞의 ..

1. BFS (Breadth-First Search) 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 동작 과정에서 큐 자료구조를 이용한다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에 방문하지 않은 노드를 모두 큐에 한 번에 삽입하고 방문 처리한다. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다. 그림으로 과정을 나타냈을 때, 다음과 같다. 이러한 과정을 반복하였을 때, 전체 노드의 탐색 순서(스택에 들어간 순서)는 다음과 같다. python 코드로 구현하면 다음과 같다.

1. DFS : Depth-First Search 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료 구조, 재귀 함수를 이용한다. 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번 과정을 수행할 수 없을 때까지 반복한다. 과정을 그림으로 나타내면 다음과 같다. 이러한 과정을 반복하였을 때, 전체 노드의 탐색 순서(스택에 들어간 순서)는 다음과 같다. python 코드로 구현하면 다음과 같다.

스택 자료 구조 ? : 스택 자료 구조는 먼저 들어온 데이터가 나중에 나가는 형식의 자료 구조이다. 스택은 입구와 출구가 같은 형태로서, 아래와 같이 시각화 할 수 있다. 스택 자료 구조의 동작은 선입후출이기 때문에, 나중에 삽입된 데이터 부터 삭제되는 것을 아래의 예시에서 볼 수 있다. 이를 바탕으로 python 코드로 구현한 그림이다.

큐 자료 구조? : 큐 자료 구조는 먼저 들어온 데이터가 먼저 나가는 형식의 자료 구조이다. 큐는 입구와 출구가 모두 뚫려 있는 터널 같은 형태로서, 아래와 같이 시각화할 수 있다. 큐 자료 구조의 동작은 선입선출이기 때문에, 먼저 삽입된 데이터부터 삭제되는 것을 아래의 예시에서 볼 수 있다. 이를 바탕으로 python 코드로 구현한 그림이다. from collections import deque; # 큐(queue) 구현을 위해 deque 라이브러리 사용 queue = deque() # 삽입(1) - 삽입(3) - 삭제() - 삽입(2) queue.append(1) queue.append(3) queue.popleft() queue.append(2) # 먼저 들어온 순서대로 출력 print(queue)..

1. 구현 알고리즘 간단하게 말해서, 풀이를 떠올리는 것은 쉽지만 코드로 구현하기 어려운 문제의 유형을 말한다. 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용되는데, 시뮬레이션 및 완전 탐색 문제에서 2차원 공간에서의 방향벡터가 자주 활용된다. 2. 구현 알고리즘 출제 유형 알고리즘은 간단한데 코드가 지나치게 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 2. 구현 해법 및 연습 문제를 풀어나갈 수 있는지 생각한다. 이를 코드로 구현하는 과정을 단계로 나누어서 정리한다. (주석으로 정리) 단계별로 하나씩 차근차근 코드를 작성한다. 문제를 접했을 때 ..