ajaaCoding

📌퀵 정렬가장 많이 사용되는 정렬 알고리즘기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작 피벗: 큰 수와 작은 수를 교환할 때 교환하기 위한 기준퀵 정렬을 수행하기 전 피벗을 어떻게 설정할 것인지 미리 명시 피벗을 설정하고 리스트를 분할하는 가장 대표적인 방식: 호어 분할 방식1. 리스트에서 첫 번째 데이터를 피벗으로 정한다.2. 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.3. 큰 데이터와 작은 데이터의 위치를 서로 교환하는 것을 반복한다.4. 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 경우, 작은 데이터와 피벗의 위치를 교환한다.5. 분할 완료: 피벗을 기준으로 피벗 왼쪽에는 피벗보다 작은 데이..

📌삽입 정렬특정한 데이터를 적절한 위치에 삽입삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 효율적선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸어서 비효율적 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정 삽입 정렬은 두 번째 데이터부터 시작, 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단삽입하는 과정을 N-1번 반복하게 되면 모든 데이터가 정렬(첫 번째 데이터는 이미 정렬이므로 N번이 아닌 N-1번) 📌삽입 정렬의 특징정렬이 이루어진 원소는 항상 오름차순 유지따라서 특정한 데이터가 삽입될 위치를 정할 때(삽입될 위치를 찾기 위해 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이..

📌정렬특정한 기준에 따라 데이터를 순서대로 나열하는 것 📌선택 정렬데이터가 무작위로 여러 개 있을 때, 가장 작은 데이터를 선택해서 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정 반복 매번 가장 작은 것을 선택한다 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬 완료마지막(N번째) 데이터는 가만히 두어도 이미 정렬된 상태 📌코드array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[..

📌문제예제 5-11 미로 탈출동빈이는 N x M 크기의 직사각형 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다.동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한번에 한칸씩 이동할 수 있다.괴물이 있는 부분은 0, 괴물이 없는 부분은 1이다.이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 📌풀이(1, 1) 지점에서부터 BFS 수행시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색 📌코드from collections import dequen, m = map(int, input().split())# 2차원 리스트의 맵 정보 입력받기graph = []for i in range(n): graph.appe..

📌문제예제 5-10 음료수 얼려 먹기 문제N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 📌풀이얼음틀을 그래프 형태로 모델링하여 DFS로 해결1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에 값이 0이면서 아직 방문하지 않은 지점이 있다면 방문2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행3. 1~2번 과정을 모든 노드에 반복하여 방문하지 않은 지점의 수를 셈 📌코드n, m = map(int, ..

📌BFS너비 우선 탐색 (Breadth First Search)가까운 노드부터 탐색하는 알고리즘 BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석인접한 노드를 반복적으로 큐에 넣도록하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색 진행 📌BFS 동작 방식1. 탐색 시작 노드를 큐에 삽입하고 방문 처리2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복  📌BFS 코드from collections import dequedef bfs(graph, start, visited): #큐 구현을 위해 deque 라이브러리 사용 queue=deque([..

📌DFSDepth-First-Search깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 📌그래프 표현 방식1. 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식2. 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식  위 그래프를 각 방식으로 표현한다면 다음과 같다 📌인접 행렬 방식2차원 배열에 각 노드가 연결된 형태를 기록하는 방식파이썬에서는 배열을 리스트 자료형으로 표현할 수 있으므로 인접행렬을 리스트로 구현함INF = 99999999 # 무한의 비용 선언# 2차원 리스트를 이용해 인접 행렬 표현graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0]]print(graph) 연결되어 있지 않은 노드끼..

📌재귀함수자기 자신을 다시 호출하는 함수DFS와 BFS를 구현하려면 재귀함수도 이해해야 함 📌재귀함수 코드def recursive_function(): print("재귀함수를 호출합니다.") recursive_function()recursive_function() 📌재귀함수의 종료 조건재귀함수의 종료 조건을 꼭 명시해야 함자칫 종료 조건을 명시하지 않으면 함수가 무한 호출 될 수 있음 📌코드def recursive_function(i): # 100번째 출력했을 때 종료되도록 종료 조건 명시 if i == 100: return print(i, "번째 재귀 함수에서", i + 1, "번째 재귀 함수를 호출합니다.") recursive_function(i +..

📌탐색많은 양의 데이터 중에서 원하는 데이터를 찾는 과정보통 그래프, 트리 등의 자료구조 안에서 탐색 📌탐색 알고리즘DFS, BFS이를 이해하기 위해서는 먼저 기본 자료구조인 스택, 큐에 대해 이해해야 함 📌오버플로, 언더플로오버플로: 자료구조에 데이터가 이미 가득 찬 상태에서 삽입 연산을 할 때 발생언더플로: 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 할 때 발생 📌스택박스 쌓기처럼 아래에서부터 위로 차곡차곡 쌓는 구조선입후출(First In Last Out) , 후입선출(Last In First Out) 구조 파이썬에서 스택을 이용할 때 별도의 라이브러리 사용할 필요 없음기본 리스트에서 append()와 pop() 메서드 사용 append(): 리스트의 가장 뒤쪽에 데이터 삽..

📌문제예제 4-4 게임 개발게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고 바다는 갈 수 없다. 매뉴얼1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면..