성덕이의 개발공간

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능 데이터의 개수(N), 데이터 중 최댓값(K)일 때, 최악의 경우에도 시간복잡도 O(N+K)를 가진다. 1. 계수 정렬 동작 예시 [Step 0] 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 리스트를 생성한다. 총 9개가 필요하다는 말! 여기서 인덱스는 특정 데이터의 값이랑 동일시 한다. [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2], 15개, min = 0, max = 9 [Step 1] 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다. 여기선 7이므로 7인덱스를 1증가시킨다. [Ste..

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다. 1. 퀵 정렬 동작 예시 [Step 0] 현재 Pivot 값은 5이다. 왼쪽에서는 Pivot값 보다 큰 데이터를 선택하고 오른쪽에서는 Pivot값 보다 작은 데이터를 선택한다. 왼쪽은 5보다 큰 7을, 오른쪽에서는 5보다 작은 4를 선택한다. 이제 두 데이터의 위치를 서로 변경한다. [Step 1] 현재 Pivot 값은 5이다. 왼쪽에서는 9는 Pivot보다 크므로 선택, 오른쪽에서는 2가 5보다 작으므로 2를 선택 9와 2의 데이터 위치를 서로 변경한다. [Step 2] 9와 2의 위치가 바뀌었다. 왼쪽에서는 Pivot보다 큰 값을 다시 찾는다. 6을 발견하는데 이때 1..

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 데이터를 하나하나씩 확인 선택 정렬에 비해 난이도가 높지만 더 효율적 1. 삽입 정렬 동작 예시 [Step 0] 7은 그 자체로 정렬되어 있다고 판단하고 이 다음 데이터인 5가 어떤 위치로 들어갈지 판단한다. 7보다 작으면 7의 왼쪽(파란색 화살표) 7보다 크면 7의 오른쪽(회색 화살표) 로 들어간다. 5는 7보다 작으므로 왼쪽으로 들어갈 것이다. [Step 1] 5가 7의 왼쪽으로 삽입되었다. 다음으로 9가 어떤 위치로 들어갈지 판단한다. 9는 7보다 작으면 왼쪽으로 갔을 것이고 또 5보다 작았으면 왼쪽으로 갔을 것이다. 여기서는 7보다 크므로 그자리에 그대로 있는다. [Step 2] 그다음 위치에 있는 0을 비교한다. 0은 그 앞 수들보다 모두 ..

정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 선택 정렬이란 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 행위 1. 선택 정렬 동작 예시 [Step 0] 처리되지 않은 데이터 중 가장 작은 '0'을 선택해 가장 앞의 '7'과 바꾼다. [Step 1] 이렇게 [Step0]에서 '0'이 '7'과 자리가 바뀐것을 알 수 있다. 처리되지 않은 데이터 중 가장 작은 '1'을 선택해 가장 앞의 '5'와(0은 바꿨으므로 무시) 바꾼다. [Step 2] 처리되지 않은 데이터 중 가장 작은 '2'를 선택해 가장 앞의 '9'와 바꾼다. [Step 3] 처리되지 않은 데이터 중 가장 작은 '3'을 선택해 가장 앞의 '7'과 바꾼다. 최종적으..

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색 상, 하, 좌, 우로 연결된 모든 노드로의 거리가 1로 동일 초기값이 1인경우 한에서만 BFS를 진행한다. 옆의 있는 노드로 방문하여 1을 추가해준다. 시작위치와 마지막위치까지의 최단경로의 노드의 수를 정하면 되므로 2로 바꿔도 된다. 방문처리한 곳은 +1씩 중첩하여 더해준다. 결과적으로 마지막 노드에 있는 수만 뽑으면 된다. 4. 답안 #DFS 소스코드구현 def DFS(x,y): queue = deque() queue.append((x,y)) #큐가 빌 때까지 반복하기 while queue: x, y = queue.popleft() #현재 위치에서 4가지 방향으로 위치 ..

1. 문제 설명 0이 붙어 있는거 끼리 모여 하나의 덩어리를 이룬다. 여기서는 총 3개의 덩어리가 만들어진다. 2. 문제 조건 4(N), 5(M) 즉, 4 * 5 형태의 얼음판이 있다. 3. 문제 해결 아이디어 3*3이라고 가정할 때 서로 인접한 노드, 그래프 형식으로 만들 수 있다. 왼쪽상단을 시작점으로 잡으면 1을 만날때 동안 DFS or BFS로 접근한다. DFS를 활용하여 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문가능 모든 노드에 대하여 1~2번의 과정을 반복하여 결국 방문하지 않은 지점의..

BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. BFS는 큐 자료구조를 이용한다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. 1. BFS 동작예시 시작지점은 1이며 인접한게 여러개이면 번호가 낮은 노드를 가도록 해보자. 큐에서 1을 꺼내서 인접한 노드 '2', '3', '8'을 큐에 삽입하고 방문처리를 해준다. 그다음 인접한 '2'로 가서 큐에서 2를 꺼내고 2와 인접한 '7'를 방문처리한다. 마찬가지로 큐에서 3을꺼내고 인접한 4와 5노드를 방문처리를 한다. 그 다음 큐에서 ..

DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS는 스택 자료구조(혹은 재귀 함수)를 이용한다. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. 1. DFS 동작 예시 1번기준으로 인접한 노드로 방문을 해야하는데 (2,3,8)이 있다. 이경우 번호가 낮은 (2)를 먼저 방문할 것이다. 우선 시작노드가 1이므로 1을 방문처리하고 스택에 1을 삽입한다. 여러 개가 인접해있지만 가장 낮은 수부터 방문하기로 했으므로 2에 방문한다. 이에..

자기 자신을 다시 호출하는 함수 def recursive(): print("재귀함수") recursive() recursive() 단 파이썬의 경우 메모리 제한이 있어서 아무제약조건 없이 재귀함수를 무한으로 돌릴수는 없다. 재귀 함수의 종료 조건을 반드시 명시해야 한다. 종료 조건을 명시하지 않으면 무한히 호출할 수 있다. def recursive(i): if i == 100: return print("재귀함수") recursive(i+1) recursive(1) return 처럼 종료 조건 명시를 해야한다. 1. 팩토리얼 1.1 반복문으로 팩토리얼 구현 def factorial(n): result = 1 for i in range(1, n+1): ..

그래프 탐색 알고리즘 (DFS/BFS) 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 그래프 탐색 알고리즘은 DFS/BFS 코딩 테스트에서 자주 등장하는 유형 먼저 2가지 큐랑 스택의 기본 구조를 알고 있어야한다. stack = [] #삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack[::-1]) print(stack) #실행 결과 [1, 3, 2, 5] [5, 2, 3, 1] 파이썬에서는 표..