[이코테] 예제3 - 퀵정렬(Quick Sort)(168p) (한줄평) 예제 문제지만 quick sort가 익숙치 않아 복습이 꼭 필요!!! 풀이2는 파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드다. 전통 퀵 정렬의 분할 방식과는 조금 다른데, pivot과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간면에서는 조금 비효율적이다. 하지만 더 직관적이고 기억하기 쉽다는 장점이 있다. (풀이1) 일반적인 코드 풀이 시간: 30분 이내 1) 문제 해결 아이디어 Pivot(기준)을 설정하여 정렬을 수행한 후 Pivot을 기준으로 왼쪽 리스트, 오른쪽 리스트에서 각각 정렬을 수행(왼쪽: pivot보다 작은 수들, 오른쪽: pivot보다 큰 수들) 1. 리스트의 원소가 1개인 경우 종료 2. Pivot(기..
[이코테] 예제2 - 삽입 정렬(Insertion Sort)(164p) 풀이 시간: 1) 문제 해결 아이디어 정렬된 데이터 리스트에서 적절한 위치를 찾은 뒤에 그 위치에 삽입 (첫번째 데이터는 정렬되어있다고 가정, 2번째 데이터부터 정렬 시작) 평균 시간 복잡도: O(n**2) 공간 복잡도: O(n) 2) 소스코드 # 선택 정렬(Insertion Sort) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] # 오름차순 정렬 # 1번 인덱스부터 시작 for i in range(1, len(array)): # 0 ~ i 인덱스 정렬 for j in range(i, 0, -1): # 현재값이 왼쪽값보다 크면 탈출 if array[j] > array[j - 1]: break # 현재값이 왼쪽..
[이코테] 예제1 - 선택 정렬(Selection Sort)(159p) 풀이 시간: 10분 이내 1) 문제 해결 아이디어 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복 (최솟값을 맨 앞에 있는 값과 바꾸고 그 다음 최솟값을 앞에서 2번째 값과 바꾸는 과정을 반복) 평균 시간 복잡도: O(n**2) 공간 복잡도: O(n) swap: 리스트에서 두 변수의 위치를 변경하는 작업 파이썬에서는 간단하게 swap를 할 수 있음(tmp 사용할 필요X) arr = [1, 2, 3, 4, 5] # 0번째 & 1번째 값 서로 바꾸기 arr[0], arr[1] = arr[1], arr[0] 2) 소스코드 # 선택 정렬(Selection Sort) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] #..
[이코테] 문제2 - 미로 탈출(152p) 풀이 시간: 40~45분 이내 1) 문제 해결 아이디어 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다. 상하좌우로 연결된 모드 노드의 길이가 1로 동일하므로 (1, 1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결 가능함 1. 종료 조건 설정 항상 출구값을 리턴하기 때문에 종료 조건이 없어도 결과는 똑같다. 다만 종료 조건을 넣어주면 해당 좌표가 출구지점이 될 떄 까지만 탐색을 진행한다. 2. 탐색 조건에서 시작점 제외 상하좌우 탐색 시, 시작점은 갔던 곳이므로 탐색하지 않도록 조건을 설정하였다. 책의 코드처럼 시작점일 때도 탐색하게 해도 결과값은 달라지지 않지만 값이 3으로 덮어쓰여지게 된다. 1. 시작..
[이코테] 문제1 - 음료수 얼려 먹기 풀이 시간: 30분 이내 1) 문제 해결 아이디어 이 문제는 DFS 혹은 BFS로 해결 가능하다. 특정 지점에서 DFS/BFS를 수행하여 이동 가능한 모든 지점에 대해 방문 처리를 한다. dfs 문제는 재귀 함수를 이용하여 해결한다. 재귀 함수의 종료 조건은 해당 좌표가 범위를 벗어났을 경우다. 현재 좌표를 아직 방문하지 않았다면 방문 처리를 하고 상하좌우에 해당하는 좌표를 매개변수로 하여 dfs를 호출한다. 1. 해당 지점이 아직 방문하지 않은 곳이라면 방문 처리 2. 상하좌우 지점 재귀 호출로 탐색 2) 소스코드 n, m = map(int, input().split()) # 세로, 가로 graph = [list(map(int, input())) for _ in ..
[이코테] BFS 예제 풀이 시간: 10분 이내 1) 문제 해결 아이디어 BFS 예제 문제로 책 147p 참고 BFS 구현을 위해 큐(deque 라이브러리) 이용 2) 소스코드 from collections import deque # BFS 메서드 def bfs(graph, start, visited): # 큐 구현을 위한 deque 라이브러리 사용 queue = deque([start]) # 현재 노드 방문 처리 visited[start] = True # 큐가 빌 때가지 반복 while queue: # 큐에서 하나의 원소를 뽑아 출력 v = queue.popleft() print(v, end=' ') # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입 for i in graph[v]: if..
[이코테] DFS 예제 풀이 시간: 5~7분 이내 1) 문제 해결 아이디어 DFS 예제 문제로 책 142p 참고 DFS 구현을 위해 재귀함수 이용 2) 소스코드 # DFS 메서드 def dfs(graph, v, visited): # 현재 노드 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드 재귀 호출 for i in graph[v]: # 인접 노드가 방문되지 않았다면 if not visited[i]: dfs(graph, i, visited) # 각 노드가 연결된 정보(2차원 리스트) graph = [ [], # 노드 번호가 1번부터 시작하므로 비워두는게 좋음 [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7..
게임 개발 1) 문제 해결 아이디어 전형적인 시뮬레이션 문제 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 좋음 2차원 리스트 선언시 리스트 컴프리헨션을 이용하는 것이 좋음 2) 소스코드 (풀이1) 나의 풀이 현재 방향 기준에서 왼쪽, 반대(후진) 방향을 리스트로 만듦 n, m = map(int, input().split()) # 맵 크기 a, b, d = map(int, input().split()) # 시작 좌표, 방향 # n * m 맵 입력 # 0: 육지, 1: 바다, 2: 가본 곳 arr = [list(map(int, input().split())) for _ in range(n)] x, y = a, b # 현재 위치 arr[x][y] = 2 ..
