$$config title: 배재대학교 PCCP 수업 keywords: - IT $$ # 수업자료 ## 취업철칙 - 블로그를 만드세요. - 블로그에 메모용 글을 많이 쓰세요. - 블로그에 알고리즘 풀이를 자주 쓰세요. ## 관련링크 - [개발자용 블로그 플랫폼 - 벨로그](https://velog.io/) - [프로그래머스 - 파이썬 입문](https://school.programmers.co.kr/learn/courses/2/2-무료-파이썬-입문) - [프로그래머스 - 파이썬을-파이썬답게](https://school.programmers.co.kr/learn/courses/4008/4008-파이썬을-파이썬답게) - [프로그래머스 - 알고리즘, 레벨 0](https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=0&languages=python3&page=1) - [프로그래머스 - 알고리즘, 레벨 1](https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=1&languages=python3&page=1) - [프로그래머스 - 알고리즘, 레벨 2](https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=2&languages=python3&page=1) - [프로그래머스 - 알고리즘, 레벨 3](https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=3&languages=python3&page=1) - [repl.it - 새 파이썬 개발환경 - https://replit.com/new/python3](https://replit.com/new/python3) # 추천자료 ## 최신 네카라쿠배 출제유형 | 빈도 | 유형 | | -- | -- | | 19% | DFS/BFS | | 19% | 문자열 | | 16% | 단순구현 | | 13% | 해시 | | 06% | 완전탐색 | | 06% | DP | | 06% | 다익스트라 | | 03% | 재귀함수 | - [출처 - 네카라쿠배 코딩 테스트 유형과 준비 방법](https://youtu.be/mIf-ZqfK4EA) ## 알고리즘 개념 - [DFS BFS 깊이 너비 우선탐색 알고리즘 5분만에 이해하기](https://youtu.be/BsYbdUnKZ-Y) - [그리디 탐욕 Greedy 알고리즘 설명 7분만에 이해하기](https://youtu.be/_IZuE7NIeW4) - [DP 동적계획 다이나믹 프로그래밍 알고리즘 설명 10분만에 이해하기 (정수 삼각형 문제풀이)](https://youtu.be/0bqfTzpWySY) - [문제](https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=python3) - [스트링 String 알고리즘 설명 5분만에 이해하기 문자열](https://youtu.be/E-wokROz5UE) - [해시 Hash 알고리즘 설명 5분만에 이해하기](https://youtu.be/zFL29ydL9D8) - [브루트 포스 완전 탐색 알고리즘 3분만에 이해하기](https://youtu.be/ZNa9-86uVEA) ## 추천영상 - [완주하지 못한 선수 프로그래머스 파이썬 문제 풀이 #해시](https://youtu.be/cJ9xdW_hqR4) - [문제](https://school.programmers.co.kr/learn/courses/30/lessons/42576?language=python3) - [전화번호 목록 프로그래머스 파이썬 문제 풀이 #해시](https://youtu.be/4-iyppqNCyg) - [문제](https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=python3) - [소수 찾기 프로그래머스 파이썬 문제 풀이 #완전탐색](https://youtu.be/m3kCKV8oc1g) - [문제](https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=python3) - [의상 프로그래머스 파이썬 python 문제 풀이 #해시](https://youtu.be/bTMV-VeaTws) - [문제](https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=python3) - [[카카오 코딩테스트] 신규 아이디 추천 - 파이썬 python 문제 풀이 #문자열](https://youtu.be/wXXnYCZ5VcQ) - [문제](https://school.programmers.co.kr/learn/courses/30/lessons/72410?language=python3) - [프린터 프로그래머스 파이썬 python 문제 풀이 #스택/큐](https://youtu.be/ZMfuDnUfdAc) - [문제](https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=python3) - [체육복 프로그래머스 파이썬 python 문제 풀이 #그리디](https://youtu.be/yiNIJuVvSbY) - [문제](https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=python3) - [분수의 덧셈(Lv0) - 파이썬 python 프로그래머스 문제 풀이 #단순구현](https://youtu.be/2sW6O3PEjHg) - [문제](https://school.programmers.co.kr/learn/courses/30/lessons/120808?language=python3) - [콜라 문제 (Lv1) - 파이썬 python 프로그래머스 문제 풀이 #단순구현](https://youtu.be/ShXeNmIHtB0) - [문제](https://school.programmers.co.kr/learn/courses/30/lessons/132267?language=python3) - [피보나치 재귀함수 DP 한 번에 해결해 드립니다. #재귀함수](https://youtu.be/5C0IxOYVrhg) - [문제](https://www.acmicpc.net/problem/10870) - [DFS와 BFS (1260, 실버 3) - 파이썬 python 백준 문제 풀이 #DFS #BFS](https://youtu.be/d3R1s_OmwAk) - [문제](https://www.acmicpc.net/problem/1260) - [유기농 배추 (1012, 실버 3) - 파이썬 python 백준 문제 풀이 #DFS](https://youtu.be/2QQd-WNoWzA) - [문제](https://www.acmicpc.net/problem/1012) - [숫자 카드 2 (10816, 실버 4) - 파이썬 python 백준 문제 풀이 #해시](https://youtu.be/QVoEbcK-eNI) - [문제](https://www.acmicpc.net/problem/10816) - [다트게임 (17682, Lv 1) - 파이썬 python 프로그래머스 문제 풀이](https://youtu.be/3JkCwrysh78) - [문제](https://school.programmers.co.kr/learn/courses/30/lessons/17682) - [나는야 포켓몬 마스터 이다솜 (1620, 실버 4) - 파이썬 python 백준 문제 풀이](https://youtu.be/2Ycb9zUaThY) - [문제](https://www.acmicpc.net/problem/1620) - [숫자의 합 (11720, 브론즈 4) - 파이썬 python 백준 문제 풀이](https://youtu.be/vGkQ6hB4GeI) - [문제](https://www.acmicpc.net/problem/11720) ## 가입해야 하는 사이트 - [개발자용 블로그 플랫폼 - 벨로그](https://velog.io/) - [repl.it - 새 파이썬 개발환경 - https://replit.com/new/python3](https://replit.com/new/python3) ## 알고리즘 공부 팁 - 알고리즘 공부를 절대로 효율적으로 하려고 하지마세요. - 재미를 따라가세요. - 쉬운문제를 많이 푸세요. - 백준 안풀어도 됩니다. 프로그래머스만으로 충분합니다. - 나중에 풀 문제 큐를 만드세요. ## velog 코드 메모용 글 템플릿 글 템플릿 ### 템플릿(#은 무시하세요.) ```` title : 제목 ```py # 소스코드 ``` ```` ### 예시 ```` title : 파이썬 함수, 리턴, 매개변수 ```py def add(a, b): return a + b rs = add(10, 20) print(rs) # 출력 : 30 ``` ```` ## 재귀함수 = 종료조건 + 점화식 ### 개념 - 재귀함수 = 종료조건 + 반복되는 패턴(점화식) - 먼저, A에게 100만원을 빌려달라고 부탁합니다. A는 자신이 가진 돈을 쓸 수 있는 만큼 써서 부족한 부분을 옆사람 B에게 빌립니다. - 하지만 B는 A에게 필요한 돈 전부를 제공하지 못할 수도 있습니다. 그럼 B는 자신이 가진 돈을 쓸 수 있는 만큼 써서 부족한 부분을 옆사람 C에게 빌립니다. - 이러한 과정이 계속 반복됩니다. B가 C에게, C가 D에게, D가 E에게, E가 F에게 돈을 빌리는 식으로 말이죠. 각 사람은 자신이 가진 돈을 쓸 수 있는 만큼 쓰고, 부족한 부분을 옆사람에게 빌립니다. - 만약 F까지 가서도 돈이 부족하다면, A는 100만원을 빌릴 수 없습니다. 하지만 F가 충분한 돈을 빌려준다면, 그 돈은 역순으로 E, D, C, B, A로 돌아가면서 각 사람이 빌렸던 돈을 청산하게 됩니다. - 이렇게 각 사람이 자신의 돈을 쓴 후 부족한 부분을 옆사람에게 빌리고, 빌린 돈을 역순으로 청산하는 과정이 바로 재귀의 개념입니다. - [영상 - 재귀함수가 뭔가요? (Feat. 하노이의 탑)](https://youtu.be/aPYE0anPZqI) ## 재귀로 팩토리얼 구현 ### 팩토리얼 ```py def factorial(n): if n == 0 or n == 1: return 1 else: fac_n_minus_1 = factorial(n-1) result = n * fac_n_minus_1 return result print(factorial(5)) ``` ## 재귀로 피보나치 구현 ### 피보나치 ```py def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 else: fib_n_minus_2 = fibonacci(n-2) fib_n_minus_1 = fibonacci(n-1) result = fib_n_minus_2 + fib_n_minus_1 return result print(fibonacci(10)) ``` ## 재귀로 이진탐색 구현 ### 이진탐색 ```py def binary_search(arr, low, high, x): if high >= low: mid = (high + low) // 2 if arr[mid] == x: return mid elif arr[mid] > x: return binary_search(arr, low, mid - 1, x) else: return binary_search(arr, mid + 1, high, x) return -1 # 정렬된 리스트와 찾고자 하는 값을 설정합니다. nums = [2, 3, 4, 10, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 700, 800, 1000, 1115] x = 800 # 이진 탐색 함수를 실행합니다. result = binary_search(nums, 0, len(nums)-1, x) if result != -1: print("Element is present at index", str(result)) else: print("Element is not present in array") ``` ## 재귀로 1부터 100까지의 합 구현 ### 1부터 100까지의 합 ```py def recursive_sum(n): if n <= 1: return 1 else: return n + recursive_sum(n-1) result = recursive_sum(10) print(result) # 결과: 55 ``` ## 재귀로 문자열 뒤집기 ### 문자열 뒤집기 ```py def reverse_string(s): if len(s) == 1: return s else: last_one = s[-1] rest = reverse_string(s[:-1]) return last_one + rest print(reverse_string("hello")) ``` ## DFS, 여러 드라마를 볼 때 하나의 드라마를 끝까지 다 보고 다른 드라마를 본다 ### 개념 - DFS = 하나의 드라마를 끝가지 보기 전까지는 다른 드라마는 안본다. - 드라마 A(총 10화), B(총 20화), C(총 30화)가 있을 때, DFS 방식으로 시청하면 다음과 같이 진행됩니다: - 먼저 드라마 A의 첫 번째 에피소드를 시청합니다. - 계속해서 드라마 A의 에피소드를 시청하며, 총 10화를 모두 볼 때까지 반복합니다. (즉, 깊이 우선으로 A 드라마를 정주행합니다) - 드라마 A를 모두 시청하였으므로, 다음으로 드라마 B의 첫 번째 에피소드를 시청합니다. - 마찬가지로 드라마 B의 에피소드를 계속 시청하여, 총 20화를 모두 볼 때까지 반복합니다. - 드라마 B를 모두 시청한 후, 마지막으로 드라마 C의 첫 번째 에피소드를 시청합니다. - 드라마 C의 모든 에피소드를 시청하여, 총 30화를 모두 볼 때까지 반복합니다. - DFS 방식은 위와 같이 한 방향으로 최대한 깊이 들어가서 탐색한 후 - 다음 경로를 탐색하는 방식입니다. 따라서 드라마 시청에 비유하자면, - 한 드라마의 모든 에피소드를 시청한 후 다음 드라마로 넘어가는 순서로 이해할 수 있습니다. ## 그래프는 정점(노드)와 간선의 집합입니다, DFS는 그래프를 탐색하는 방법 중 하나 ### 간단한 그래프(순환 무향 그래프) - ![img](https://showme.redstarplugin.com/d/FHGSxLOi) ```py graph = { 1 : [2, 3], 2 : [1, 4], 3 : [1], 4 : [2] } ``` ### 조금 복잡한 그래프(순환 무향 그래프) - ![img](https://showme.redstarplugin.com/d/i5GUr58A) ```py graph = { 1: [2, 3, 8], 2: [1, 7], 3: [1, 4, 5], 4: [3, 5], 5: [3, 4], 6: [7], 7: [2, 6, 8], 8: [1, 7] } ``` ## DFS 완전탐색, 방문한 순서대로 노드를 출력, 비순환 유향 그래프 - ![img](https://showme.redstarplugin.com/d/7PTxDTdT) ### 문제 ```py graph = { 1 : [2, 3], 2 : [4], 3 : [], 4 : [] } sol(graph) # 출력 # 1 # 2 # 4 # 3 ``` ### 정답 ```py graph = { 1 : [2, 3], 2 : [4], 3 : [], 4 : [] } def dfs(graph, node): print(node) for nei_node in graph[node]: dfs(graph, nei_node) def sol(graph): dfs(graph, 1) sol(graph) # 출력 # 1 # 2 # 4 # 3 ``` ## DFS 완전탐색, 방문한 순서대로 노드를 출력, 순환 무향 그래프, 이미 방문했는지 체크하는 로직 필수 - ![img](https://showme.redstarplugin.com/d/FHGSxLOi) ### 문제 ```py graph = { 1 : [2, 3], 2 : [1, 4], 3 : [1], 4 : [2] } sol(graph) # 출력 # 1 # 2 # 4 # 3 ``` ### 정답 ```py graph = { 1 : [2, 3], 2 : [1, 4], 3 : [1], 4 : [2] } def dfs(graph, visited, node): print(node) # 값이 True 가 아니어도 됩니다. visited[node] = True # for nei_node in graph[node].keys(): 와 아래 코드는 결과가 같습니다. for nei_node in graph[node]: if nei_node in visited: continue dfs(graph, visited, nei_node) def sol(graph): visited = {} dfs(graph, visited, 1) sol(graph) # 출력 # 1 # 2 # 4 # 3 ``` ## BFS는 그래프를 탐색하는 방법 중 하나, DFS 와 달리 중심점에서 천천히 탐색범위를 키워감. - BFS = 드라마를 하나 완전히 보기 전에 다른 드라마를 섞어서 봅니다. - 드라마 A(총 10화), B(총 20화), C(총 30화)가 있을 때, BFS 방식으로 시청하면 다음과 같이 진행됩니다: - 먼저 드라마 A의 첫 번째 에피소드를 시청합니다. - 그 다음으로 드라마 B의 첫 번째 에피소드를 시청합니다. - 그리고 드라마 C의 첫 번째 에피소드를 시청합니다. - 그런 다음에 드라마 A의 두 번째 에피소드로 돌아와서 시청합니다. - 그 다음 드라마 B의 두 번째 에피소드를 시청합니다. - 그 후에는 드라마 C의 두 번째 에피소드를 시청합니다. - 이런 방식으로 각 드라마의 모든 에피소드를 돌아가며 시청합니다. 즉, 드라마 A의 모든 에피소드를 보기 전에 드라마 B와 C의 에피소드도 함께 본다는 것입니다. - 이를 시청 순서로 나열하면 다음과 같습니다: A1 -> B1 -> C1 -> A2 -> B2 -> C2 -> ... -> A10 -> B11 -> C11 -> ... -> B20 -> C21 -> ... -> C30 - BFS 방식은 위와 같이 너비 우선으로 각 경로를 동시에 조금씩 탐색하는 방식입니다. - 따라서 드라마 시청에 비유하자면, 여러 드라마를 번갈아가며 시청하는 순서로 이해할 수 있습니다. ## DFS와 BFS 비교, 쇼핑카드 찾기로 설명 ### DFS(깊이 우선 탐색) - 상황: 슈퍼마켓에서 장바구니가 필요합니다. 아무곳에나 놓여 있을 수 있는데, 장바구니를 찾기 위해선 모든 곳을 찾아봐야 합니다. - 사용: 슈퍼마켓의 한쪽 끝에서 시작해서 한 군데씩 꼼꼼히 찾아보며 진행합니다. 물건이 가득 차 있는 막대한 슈퍼마켓이라고 생각하면 됩니다. 한 곳을 완전히 탐색하고 나서야 다음 구역으로 넘어갑니다. - 장점: 가장 먼저 찾은 장바구니는 그 지역에 가장 가까운 장바구니일 가능성이 큽니다. 모든 곳을 찾아보지 않아도 되는 경우에 효율적입니다. - 단점: 다른 지역에 더 가까운 장바구니가 있을 수 있지만, 현재 탐색 중인 지역이 완전히 끝날 때까지 그것을 찾아내지 못합니다. ### BFS(너비 우선 탐색) - 상황: 같은 슈퍼마켓에서 장바구니가 필요합니다. 그런데 이번엔 최대한 빨리 장바구니를 찾아야 합니다. - 사용: 슈퍼마켓의 중앙에서 시작해서, 가까운 곳부터 조금씩 넓혀가며 찾아봅니다. 주변을 동그랗게 확장해나가며 찾는다고 생각하면 됩니다. - 장점: 시작 지점에서 가장 가까운 장바구니를 빠르게 찾을 수 있습니다. - 단점: 한 지역을 꼼꼼히 탐색하는 데에 비해 시간이 더 많이 걸릴 수 있습니다. ### 결론 - 결국, DFS는 탐색 범위를 좁히고자 할 때, BFS는 최소 거리를 찾고자 할 때 주로 사용됩니다. ## 데크 개념 및 사용법 ### 데크 - 파이썬의 collections 모듈에서 제공하는 deque (데크, double-ended queue)는 - 양방향에서 요소를 추가하거나 제거할 수 있는 더 유연한 자료형입니다. - 스택과 큐의 역할을 동시에 수행할 수 있습니다. ### 데크 사용법 ```py # 데크 생성 from collections import deque d = deque() # 오른쪽에 요소 추가 d.append('a') print(d) # deque(['a']) # 왼쪽에 요소 추가 d.appendleft('b') print(d) # deque(['b', 'a']) # 오른쪽에서 요소 제거 element = d.pop() print(element) # 'a' print(d) # deque(['b']) # 왼쪽에서 요소 제거 element = d.popleft() print(element) # 'b' print(d) # deque([]) # 요소의 개수 세기 d = deque(['a', 'b', 'a']) print(d.count('a')) # 2 # 오른쪽에 여러 요소 추가 d.extend(['x', 'y', 'z']) print(d) # deque(['a', 'b', 'a', 'x', 'y', 'z']) # 왼쪽에 여러 요소 추가 d.extendleft(['1', '2', '3']) print(d) # deque(['3', '2', '1', 'a', 'b', 'a', 'x', 'y', 'z']) # 데크의 크기 제한 설정 d = deque(maxlen=3) d.append(1) d.append(2) d.append(3) print(d) # deque([1, 2, 3]) # 크기 제한을 초과하는 요소 추가 (오래된 요소 삭제) d.append(4) print(d) # deque([2, 3, 4]) # 데크의 길이 print(len(d)) # 3 # 데크에 요소가 있는지 확인 if not d: print("Deque is empty") # 데크의 모든 요소 제거 d.clear() print(d) # deque([]) # 요소의 위치 찾기 (index는 0부터 시작) d = deque(['a', 'b', 'c']) print(d.index('b')) # 1 # 특정 위치에 요소 삽입 d.insert(2, 'x') print(d) # deque(['a', 'b', 'x', 'c']) # 요소의 존재 확인 if 'x' in d: print("Element found in deque") # 데크 회전 (양수 = 오른쪽, 음수 = 왼쪽) d = deque(['a', 'b', 'c']) d.rotate(1) print(d) # deque(['c', 'a', 'b']) # 데크 뒤집기 d = deque(['a', 'b', 'c']) d.reverse() print(d) # deque(['c', 'b', 'a']) # 리스트를 데크로 변환 l = ['x', 'y', 'z'] d = deque(l) print(d) # deque(['x', 'y', 'z']) # 데크를 리스트로 변환 l = list(d) print(l) # ['x', 'y', 'z'] ``` ## 리스트와 데크의 비교, 리스트는 구조적 변경이 느리지만 데이터 접근이 빠르다. 데크는 구조적 변경이 쉽지만 데이터 접근이 느리다. ## 데크의 각 기능별 리스트와의 속도비교, 리스트가 데이터 접근 속도가 빠르다는 것을 제외하면 나머지는 데크보다 비슷하거나 느리다. ```py # 데크 생성 - 리스트와 동일한 시간 복잡도를 갖습니다. from collections import deque d = deque() # 오른쪽에 요소 추가 - 리스트의 append와 같은 O(1)의 시간 복잡도를 갖습니다. d.append('a') print(d) # deque(['a']) # 왼쪽에 요소 추가 - 리스트보다 빠릅니다. O(1)의 시간 복잡도를 갖습니다. d.appendleft('b') print(d) # deque(['b', 'a']) # 오른쪽에서 요소 제거 - 리스트의 pop와 같은 O(1)의 시간 복잡도를 갖습니다. element = d.pop() print(element) # 'a' print(d) # deque(['b']) # 왼쪽에서 요소 제거 - 리스트보다 빠릅니다. O(1)의 시간 복잡도를 갖습니다. element = d.popleft() print(element) # 'b' print(d) # deque([]) # 요소의 개수 세기 - 리스트와 동일한 O(n)의 시간 복잡도를 갖습니다. d = deque(['a', 'b', 'a']) print(d.count('a')) # 2 # 오른쪽에 여러 요소 추가 - 리스트의 extend와 동일한 O(k)의 시간 복잡도를 갖습니다. d.extend(['x', 'y', 'z']) print(d) # deque(['a', 'b', 'a', 'x', 'y', 'z']) # 왼쪽에 여러 요소 추가 - 리스트보다 빠릅니다. O(k)의 시간 복잡도를 갖습니다. d.extendleft(['1', '2', '3']) print(d) # deque(['3', '2', '1', 'a', 'b', 'a', 'x', 'y', 'z']) # 데크의 크기 제한 설정 - 리스트에는 이 기능이 없습니다. d = deque(maxlen=3) d.append(1) d.append(2) d.append(3) print(d) # deque([1, 2, 3]) # 크기 제한을 초과하는 요소 추가 (오래된 요소 삭제) - 리스트에는 이 기능이 없습니다. d.append(4) print(d) # deque([2, 3, 4]) # 데크의 길이 - 리스트와 동일한 O(1)의 시간 복잡도를 갖습니다. print(len(d)) # 3 # 데크에 요소가 있는지 확인 - 리스트와 동일한 시간 복잡도를 갖습니다. if not d: print("Deque is empty") # 데크의 모든 요소 제거 - 리스트의 clear와 동일한 O(1)의 시간 복잡도를 갖습니다. d.clear() print(d) # deque([]) # 요소의 위치 찾기 (index는 0부터 시작) - 리스트와 동일한 O(n)의 시간 복잡도를 갖습니다. d = deque(['a', 'b', 'c']) print(d.index('b')) # 1 # 특정 위치에 요소 삽입 - 리스트보다 느립니다. O(n)의 시간 복잡도를 갖습니다. d.insert(2, 'x') print(d) # deque(['a', 'b', 'x', 'c']) # 요소의 존재 확인 - 리스트와 동일한 O(n)의 시간 복잡도를 갖습니다. if 'x' in d: print("Element found in deque") # 데크 회전 (양수 = 오른쪽, 음수 = 왼쪽) - 리스트에는 이 기능이 없습니다. d = deque(['a', 'b', 'c']) d.rotate(1) print(d) # deque(['c', 'a', 'b']) # 데크 뒤집기 - 리스트의 reverse와 동일한 O(n)의 시간 복잡도를 갖습니다. d = deque(['a', 'b', 'c']) d.reverse() print(d) # deque(['c', 'b', 'a']) # 리스트를 데크로 변환 - 리스트와 동일한 시간 복잡도를 갖습니다. l = ['x', 'y', 'z'] d = deque(l) print(d) # deque(['x', 'y', 'z']) # 데크를 리스트로 변환 - 리스트와 동일한 시간 복잡도를 갖습니다. l = list(d) print(l) # ['x', 'y', 'z'] ``` ## 데크를 스택처럼 사용하기, 큐처럼 사용하기 ### 데크로 스택 구현 ```py from collections import deque stack = deque() # 스택에 값 추가 stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # 스택에서 값 제거 (LIFO: Last In First Out) print('\nElements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('\nStack after elements are popped:') print(stack) ``` ### 데크로 큐 구현 ```py from collections import deque queue = deque() # 큐에 값 추가 queue.append('a') queue.append('b') queue.append('c') print('Initial queue:') print(queue) # 큐에서 값 제거 (FIFO: First In First Out) print('\nElements dequeued from queue:') print(queue.popleft()) print(queue.popleft()) print(queue.popleft()) print('\nQueue after elements are dequeued:') print(queue) ``` ## 집합을 나타내는 자료구조 Set, Set 안의 요소는 순서가 없고, 중복도 허용되지 않는다. ```py # Set 생성하기 # 빈 set 생성 s = set() print(s) # 출력: set() # 값이 있는 set 생성 s = {1, 2, 3} print(s) # 출력: {1, 2, 3} # Set에 값 추가하기 s.add(4) print(s) # 출력: {1, 2, 3, 4} # Set에서 값 제거하기 s.remove(2) print(s) # 출력: {1, 3, 4} # Set에서 임의의 원소 제거하기 s.pop() print(s) # 출력: {3, 4} # Set의 길이 구하기 print(len(s)) # 출력: 2 # Set에 특정 값이 있는지 확인하기 print(1 in s) # 출력: False print(4 in s) # 출력: True # s == {3, 4} # Set의 합집합, 교집합, 차집합, 대칭차집합 구하기 s1 = {1, 2, 3} print(s1 | s) # 출력: {1, 2, 3, 4} print(s1 & s) # 출력: {3} print(s1 - s) # 출력: {1, 2} print(s1 ^ s) # 출력: {1, 2, 4} # Set의 모든 원소 제거하기 s.clear() print(s) # 출력: set() # Set에서 특정 값 제거하기 (없는 값 제거 시 에러 발생하지 않음) s1.discard(2) print(s1) # 출력: {1, 3} s1.discard(4) print(s1) # 출력: {1, 3} # 두 Set이 같은지 확인하기 s2 = {1, 3} print(s1 == s2) # 출력: True # 하나의 Set이 다른 Set의 부분집합인지 확인하기 s1 = {1, 2} print(s1.issubset(s2)) # 출력: False # 하나의 Set이 다른 Set의 상위집합인지 확인하기 s2 = {1, 2, 3} print(s2.issuperset(s1)) # 출력: True # 두 Set이 서로소인지 확인하기 (공통 원소가 없는지) s3 = {3, 4} print(s1.isdisjoint(s3)) # 출력: True # Set을 리스트로 변환하기 l = list(s1) print(l) # 출력: [1, 2] # 리스트를 Set으로 변환하기 (중복 원소 제거) l = [1, 2, 2, 3, 3, 3] s = set(l) print(s) # 출력: {1, 2, 3} # Set 복사하기 s4 = s.copy() print(s4) # 출력: {1, 2, 3} # Set comprehension 사용하기 s = {i for i in range(10) if i % 2 == 0} print(s) # 출력: {0, 2, 4, 6, 8} # 여러 set의 합집합, 교집합 구하기 s1 = {1, 2, 3} s2 = {3, 4, 5} s3 = {5, 6, 7} print(s1 | s2 | s3) # 출력: {1, 2, 3, 4, 5, 6, 7} s1 = {1, 2, 3, 4} s2 = {2, 3, 4, 5} s3 = {3, 4, 5, 6} print(s1 & s2 & s3) # 출력: {3, 4} # set의 값 업데이트하기 s = {1, 2, 3} s.update({4, 5, 6}) print(s) # 출력: {1, 2, 3, 4, 5, 6} # set에서 여러 값 제거하기 s.difference_update({2, 3}) print(s) # 출력: {1, 4, 5, 6} # set의 원소를 정렬하기 s = {3, 1, 2, 5, 4} sorted_s = sorted(s) print(sorted_s) # 출력: [1, 2, 3, 4, 5] # 문자열을 set으로 변환하기 str = "hello" s = set(str) print(s) # 출력: {'h', 'e', 'l', 'o'} ``` ## 일반 그래프보다 쉬운 트리형태의 그래프를 BFS로 탐색 ![img](https://showme.redstarplugin.com/d/xbY6e1r7) ### 문제 ```py from collections import deque def bfs(graph, root): '''구현해주세요''' graph = { 1: [2, 3, 8], 2: [7], 3: [4], 4: [5], 5: [], 6: [], 7: [6], 8: [] } bfs(graph, 1) # 출력 # 1 2 3 8 7 4 6 5 ``` ### 정답 ```py from collections import deque def bfs(graph, root): # 빈 큐를 생성하고, 루트 노드를 큐에 추가합니다. queue = deque([root]) while queue: # 큐의 첫 번째 노드를 꺼냅니다. node = queue.popleft() # 현재 노드를 출력합니다. print(node, end=' ') # 현재 노드의 인접 노드들을 for nei_node in graph[node]: # 큐에 추가합니다. queue.append(nei_node) graph = { 1: [2, 3, 8], 2: [7], 3: [4], 4: [5], 5: [], 6: [], 7: [6], 8: [] } bfs(graph, 1) ``` ## 일반적인 그래프에 적용할 수 있는 BFS 탐색에는 꼭 이미 방문한 노드에 대한 스킵이 있어야 한다. - ![img](https://showme.redstarplugin.com/d/FHGSxLOi) ### 문제 ```py from collections import deque def bfs(graph, root): '''구현해주세요''' graph = { 1 : [2, 3], 2 : [1, 4], 3 : [1], 4 : [2] } bfs(graph, 1) # 출력 # 1 2 3 4 ``` ### 정답 ```py from collections import deque def bfs(graph, root): # 빈 큐를 생성하고, 루트 노드를 큐에 추가합니다. queue = deque([root]) visited = set() while queue: # 큐의 첫 번째 노드를 꺼냅니다. node = queue.popleft() if node in visited: continue visited.add(node) # 현재 노드를 출력합니다. print(node, end=' ') # 현재 노드의 인접 노드들을 for nei_node in graph[node]: # 큐에 추가합니다. queue.append(nei_node) graph = { 1 : [2, 3], 2 : [1, 4], 3 : [1], 4 : [2] } bfs(graph, 1) # 출력 # 1 2 3 4 ``` ## 클래스와 객체 ```py # 간단한 클래스 생성 class MyClass: x = 5 p1 = MyClass() print(p1.x) # 출력: 5 del MyClass, p1 # init 메소드를 이용한 초기화 class Person: def __init__(self, name, age): self.name = name self.age = age p1 = Person("John", 36) print(p1.name) # 출력: John print(p1.age) # 출력: 36 del Person, p1 # 객체 메소드 class Person: def __init__(self, name, age): self.name = name self.age = age def myfunc(self): print("Hello my name is " + self.name) p1 = Person("John", 36) p1.myfunc() # 출력: Hello my name is John del Person, p1 # self 매개변수 class Person: def __init__(mysillyobject, name, age): mysillyobject.name = name mysillyobject.age = age def myfunc(abc): print("Hello my name is " + abc.name) p1 = Person("John", 36) p1.myfunc() # 출력: Hello my name is John del Person, p1 # 객체 속성 변경 class Person: def __init__(self, name, age): self.name = name self.age = age p1 = Person("John", 36) p1.age = 40 print(p1.age) # 출력: 40 del Person, p1 # 상속 class Person: def __init__(self, fname, lname): self.firstname = fname self.lastname = lname def printname(self): print(self.firstname, self.lastname) class Student(Person): pass x = Student("Mike", "Olsen") x.printname() # 출력: Mike Olsen del Person, Student, x # 상속 - 자식 클래스의 init 함수 추가 class Person: def __init__(self, fname, lname): self.firstname = fname self.lastname = lname def printname(self): print(self.firstname, self.lastname) class Student(Person): def __init__(self, fname, lname): super().__init__(fname, lname) x = Student("Mike", "Olsen") x.printname() # 출력: Mike Olsen del Person, Student, x # 상속 - 속성 추가 class Person: def __init__(self, fname, lname): self.firstname = fname self.lastname = lname def printname(self): print(self.firstname, self.lastname) class Student(Person): def __init__(self, fname, lname): super().__init__(fname, lname) self.graduationyear = 2023 x = Student("Mike", "Olsen") print(x.graduationyear) # 출력: 2023 del Person, Student, x # 상속 - 메소드 추가 class Person: def __init__(self, fname, lname): self.firstname = fname self.lastname = lname def printname(self): print(self.firstname, self.lastname) class Student(Person): def __init__(self, fname, lname, year): super().__init__(fname, lname) self.graduationyear = year def welcome(self): print("Welcome", self.firstname, self.lastname, "to the class of", self.graduationyear) x = Student("Mike", "Olsen", 2023) x.welcome() # 출력: Welcome Mike Olsen to the class of 2023 del Person, Student, x ``` ### 문제 1 ```py class Person(): '''구현해주세요''' p1 = Person("Paul", 22) p2 = Person("Alice", 23) p1.introduce() # 출력 : My name is Paul, I'm 22 years old. p2.introduce() # 출력 : My name is Alice, I'm 23 years old. ``` #### 정답 ```py class Person(): def __init__(self, name, age): self.name = name self.age = age def introduce(self): print("My name is {}, I'm {} years old.".format(self.name, self.age)) p1 = Person("Paul", 22) p2 = Person("Alice", 23) p1.introduce() # 출력 : My name is Paul, I'm 22 years old. p2.introduce() # 출력 : My name is Alice, I'm 23 years old. ``` ### 문제 2 ```py class Car: '''구현해주세요.''' my_car = Car('Toyota', '2020') my_car.show_info() # 출력 # Brand: Toyota # Year: 2020 ``` #### 정답 ```py class Car: def __init__(self, brand, year): self.brand = brand self.year = year def show_info(self): print("Brand: {}".format(self.brand)) print("Year: {}".format(self.year)) my_car = Car('Toyota', '2020') my_car.show_info() # 출력 # Brand: Toyota # Year: 2020 ``` ### 문제 3 ```py class Animal: def __init__(self, name, age): self.name = name self.age = age class Dog(Animal): '''구현해주세요.''' my_dog = Dog('Max', 2, 'Bulldog') print(my_dog.name) # 출력: # Max print(my_dog.age) # 출력: # 2 print(my_dog.breed) # 출력: # Bulldog ``` #### 정답 ```py class Animal: def __init__(self, name, age): self.name = name self.age = age class Dog(Animal): def __init__(self, name, age, breed): super().__init__(name, age) self.breed = breed my_dog = Dog('Max', 2, 'Bulldog') print(my_dog.name) # 출력: # Max print(my_dog.age) # 출력: # 2 print(my_dog.breed) # 출력: # Bulldog ``` ### 문제 4 ```py class Rectangle: '''구현해주세요.''' my_rectangle = Rectangle(5, 7) print(my_rectangle.calculate_area()) # 사각형의 너비를 반환 # 출력 : 35 ``` #### 정답 ```py class Rectangle: def __init__(self, width, height): self.width = width self.height = height def calculate_area(self): return self.width * self.height my_rectangle = Rectangle(5, 7) print(my_rectangle.calculate_area()) # 사각형의 너비를 반환 ``` ## 단순한 정렬 ```py # 기본적인 리스트 정렬 nums = [3, 1, 4, 1, 5, 9, 2, 6] nums.sort() print(nums) # 출력: [1, 1, 2, 3, 4, 5, 6, 9] del nums # sorted 함수를 이용한 리스트 정렬 nums = [3, 1, 4, 1, 5, 9, 2, 6] sorted_nums = sorted(nums) print(sorted_nums) # 출력: [1, 1, 2, 3, 4, 5, 6, 9] del nums, sorted_nums # 리스트 뒤집기 nums = [1, 2, 3, 4, 5] nums.reverse() print(nums) # 출력: [5, 4, 3, 2, 1] del nums # sort()로 리스트 내림차순 정렬 nums = [3, 1, 4, 1, 5, 9, 2, 6] nums.sort(reverse=True) print(nums) # 출력: [9, 6, 5, 4, 3, 2, 1, 1] del nums # sorted()로 리스트 내림차순 정렬 nums = [3, 1, 4, 1, 5, 9, 2, 6] sorted_nums = sorted(nums, reverse=True) print(sorted_nums) # 출력: [9, 6, 5, 4, 3, 2, 1, 1] del nums, sorted_nums # 문자열 리스트를 알파벳 순서로 정렬 strs = ['banana', 'apple', 'kiwi', 'orange'] strs.sort() print(strs) # 출력: ['apple', 'banana', 'kiwi', 'orange'] del strs # 문자열 리스트를 알파벳 역순으로 정렬 strs = ['banana', 'apple', 'kiwi', 'orange'] strs.sort(reverse=True) print(strs) # 출력: ['orange', 'kiwi', 'banana', 'apple'] del strs # 튜플을 원소로 갖는 리스트 정렬 tuples = [(1, 'one'), (3, 'three'), (2, 'two')] tuples.sort() print(tuples) # 출력: [(1, 'one'), (2, 'two'), (3, 'three')] del tuples # 튜플을 원소로 갖는 리스트를 두 번째 요소를 기준으로 정렬 tuples = [(1, 'one'), (3, 'three'), (2, 'two')] tuples.sort(key=lambda x: x[1]) print(tuples) # 출력: [(1, 'one'), (3, 'three'), (2, 'two')] del tuples # 딕셔너리를 값에 따라 정렬 dicts = {'three': 3, 'one': 1, 'two': 2} sorted_dicts = sorted(dicts.items(), key=lambda x: x[1]) print(sorted_dicts) # 출력: [('one', 1), ('two', 2), ('three', 3)] del dicts, sorted_dicts # 딕셔너리를 키에 따라 정렬 dicts = {'three': 3, 'one': 1, 'two': 2} sorted_dicts = sorted(dicts.items(), key=lambda x: x[0]) print(sorted_dicts) # 출력: [('one', 1), ('three', 3), ('two', 2)] del dicts, sorted_dicts # 복합 리스트 정렬 complex_list = [3, 1, 4, [5, 6, 7], 2] complex_list.sort(key=lambda x: x if isinstance(x, int) else x[0]) print(complex_list) # 출력: [1, 2, 3, 4, [5, 6, 7]] del complex_list # 문자열 리스트를 길이에 따라 정렬 strs = ['aaaa', 'bb', 'ccc', 'd'] strs.sort(key=len) print(strs) # 출력: ['d', 'bb', 'ccc', 'aaaa'] del strs # 중복 제거 후 정렬 nums = [3, 1, 4, 1, 5, 9, 2, 6, 2, 6] nums = list(set(nums)) nums.sort() print(nums) # 출력: [1, 2, 3, 4, 5, 6, 9] del nums # sorted() 함수로 문자열 정렬 s = 'apple' sorted_s = ''.join(sorted(s)) print(sorted_s) # 출력: 'aelpp' del s, sorted_s # 중첩 리스트 정렬 nested_list = [[3, 2, 1], [6, 5, 4], [9, 8, 7]] nested_list.sort(key=lambda x: x[1]) print(nested_list) # 출력: [[3, 2, 1], [6, 5, 4], [9, 8, 7]] del nested_list # 중첩 리스트 내부 정렬 nested_list = [[3, 2, 1], [6, 5, 4], [9, 8, 7]] for sublist in nested_list: sublist.sort() print(nested_list) # 출력: [[1, 2, 3], [4, 5, 6], [7, 8, 9]] del nested_list # 중첩 리스트 내부와 외부 동시 정렬 nested_list = [[3, 2, 1], [6, 5, 4], [9, 8, 7]] for sublist in nested_list: sublist.sort() nested_list.sort(key=lambda x: x[0]) print(nested_list) # 출력: [[1, 2, 3], [4, 5, 6], [7, 8, 9]] del nested_list # 클래스 인스턴스 정렬 class Person: def __init__(self, name, age): self.name = name self.age = age people = [Person('John', 20), Person('Jane', 19), Person('Adam', 21)] people.sort(key=lambda x: x.age) for person in people: print(person) del Person, people ``` ## 숫자 리스트 정렬 ### 문제 1 - 다음과 같이 주어진 리스트를 활용하여 아래의 작업을 수행해주세요. ```py list1 = [2, 7, 9, 2, 4, 3, 8, 6, 1] ``` #### 작업 - 오름차순으로 정렬하고 결과를 출력하세요. - 내림차순으로 정렬하고 결과를 출력하세요. - 중복된 숫자를 제거한 후 오름차순으로 정렬하고 결과를 출력하세요. #### 정답 ```py list1 = [2, 7, 9, 2, 4, 3, 8, 6, 1] # 오름차순으로 정렬하고 결과를 출력하세요. list1.sort() print(list1) # 내림차순으로 정렬하고 결과를 출력하세요. list1.sort(reverse=True) print(list1) # 중복된 숫자를 제거한 후 오름차순으로 정렬하고 결과를 출력하세요. list1 = sorted(set(list1)) print(list1) ``` ## 튜플 정렬 ### 문제 2 - 다음과 같은 튜플 리스트를 활용하여 아래의 작업을 수행해주세요. ```py tuple_list = [ ('apple', 3), ('banana', 2), ('cherry', 1), ('apple', 4), ('banana', 1) ] ``` #### 작업 - 첫 번째 요소 (과일 이름)를 기준으로 오름차순으로 정렬하고 결과를 출력하세요. - 두 번째 요소 (숫자)를 기준으로 오름차순으로 정렬하고 결과를 출력하세요. #### 정답 ```py tuple_list = [ ('apple', 3), ('banana', 2), ('cherry', 1), ('apple', 4), ('banana', 1) ] # 첫 번째 요소 (과일 이름)를 기준으로 # 오름차순으로 정렬하고 결과를 출력하세요. tuple_list.sort() print(tuple_list) # 두 번째 요소 (숫자)를 기준으로 # 오름차순으로 정렬하고 결과를 출력하세요. tuple_list.sort(key=lambda row: row[1]) print(tuple_list) ``` ## 문자열 리스트 정렬 ### 문제 3 - 다음과 같은 문자열 리스트를 활용하여 아래의 작업을 수행해주세요. ``` str_list = ['Python', 'Java', 'C', 'JavaScript', 'Ruby', 'Go'] ``` #### 작업 - 문자열의 길이를 기준으로 오름차순으로 정렬하고 결과를 출력하세요. - 문자열을 알파벳 역순으로 정렬하고 결과를 출력하세요. #### 정답 ```py str_list = ['Python', 'Java', 'C', 'JavaScript', 'Ruby', 'Go'] # 문자열의 길이를 기준으로 오름차순으로 # 정렬하고 결과를 출력하세요. str_list.sort(key=len) print(str_list) # 문자열을 알파벳 역순으로 # 정렬하고 결과를 출력하세요. str_list.sort(reverse=True) print(str_list) ``` ## 정렬조건이 2개 이상인 경우 ```py # 숫자 리스트를 절대값 기준으로 정렬하는 예제입니다. nums = [3, -1, 4, -1, -5, 9, 2, -6] sorted_nums = sorted(nums, key=abs) print(sorted_nums) # 출력: [-1, -1, 2, 3, 4, -5, -6, 9] del nums, sorted_nums # 이름과 나이를 가진 사람 객체 리스트를 나이 순으로 정렬하는 예제입니다. class Person: def __init__(self, name, age): self.name = name self.age = age people = [Person('Alice', 30), Person('Bob', 30), Person('Charlie', 25), Person('Alice', 20)] people.sort(key=lambda person: person.age) for person in people: print(person.name, person.age) del Person, people # 나이가 같으면 이름으로 추가 정렬하는 예제입니다. class Person: def __init__(self, name, age): self.name = name self.age = age people = [Person('Alice', 20), Person('Bob', 30), Person('Charlie', 25), Person('David', 25), Person('Alice', 25)] people.sort(key=lambda person: (person.age, person.name)) for person in people: print(person.name, person.age) del Person, people # 이름이 같으면 나이가 큰 순으로 정렬하는 예제입니다. class Person: def __init__(self, name, age): self.name = name self.age = age people = [Person('Alice', 20), Person('Bob', 30), Person('Charlie', 25), Person('Alice', 25)] people.sort(key=lambda person: (person.name, -person.age)) for person in people: print(person.name, person.age) del Person, people # 나이로 먼저 정렬하고, 나이가 같으면 이름의 알파벳 역순으로 정렬하는 예제입니다. class Person: def __init__(self, name, age): self.name = name self.age = age people = [Person('Alice', 20), Person('Bob', 30), Person('Charlie', 25), Person('David', 25), Person('Alice', 25)] people.sort(key=lambda person: person.name, reverse=True) people.sort(key=lambda person: person.age) for person in people: print(person.name, person.age) del Person, people # 나이로 먼저 정렬하고, 나이가 같으면 이름의 알파벳 역순으로 정렬하는 예제입니다. class Person: def __init__(self, name, age): self.name = name self.age = age def __lt__(self, other): if self.age != other.age: return self.age < other.age return self.name > other.name # 이름이 같은 경우, 알파벳 역순으로 정렬합니다. people = [Person('Alice', 20), Person('Bob', 30), Person('Charlie', 25), Person('David', 25), Person('Alice', 25)] people.sort() for person in people: print(person.name, person.age) del Person, people ``` ## 정렬 2부 문제 1, 절대값 기준 정렬 ### 문제 1 - 다음과 같이 주어진 리스트를 활용하여 아래의 작업을 수행해주세요. ```py nums = [7, -9, -2, 4, 3, -8, 6, 1] ``` #### 작업 - 절대값 기준으로 오름차순 정렬하고 결과를 출력하세요. - 절대값 기준으로 내림차순 정렬하고 결과를 출력하세요. #### 정답 ```py # 주어진 리스트 nums = [7, -9, -2, 4, 3, -8, 6, 1] # 절대값 기준으로 오름차순 정렬 ascending_sorted_nums = sorted(nums, key=abs) # 절대값 기준으로 내림차순 정렬 descending_sorted_nums = sorted(nums, key=abs, reverse=True) print("오름차순 정렬: ", ascending_sorted_nums) print("내림차순 정렬: ", descending_sorted_nums) ``` ## 정렬 2부 문제 2, 객체정렬 ### 문제 2 - 다음과 같은 'Person' 객체 리스트를 활용하여 아래의 작업을 수행해주세요. ```py class Person: def __init__(self, name, age): self.name = name self.age = age people = [ Person('Alice', 30), Person('Bob', 35), Person('Charlie', 25), Person('Alice', 25), Person('David', 30) ] ``` #### 작업 - 이름으로 오름차순 정렬하고 결과를 출력하세요. - 나이로 오름차순 정렬하고 결과를 출력하세요. - 이름으로 오름차순 정렬 후, 같은 이름일 경우 나이가 더 많은 순으로 정렬하고 결과를 출력하세요. - 나이로 오름차순 정렬 후, 같은 나이일 경우 이름을 알파벳 역순으로 정렬하고 결과를 출력하세요. #### 정답 ```py class Person: def __init__(self, name, age): self.name = name self.age = age def __repr__(self): return f"Person(name='{self.name}', age={self.age})" people = [ Person('Alice', 30), Person('Bob', 35), Person('Charlie', 25), Person('Alice', 25), Person('David', 30) ] # 문제 : 이름으로 오름차순 정렬하고 결과를 출력하세요. people1 = sorted(people, key = lambda person: person.name) print(people1) # 문제 : 나이로 오름차순 정렬하고 결과를 출력하세요. people2 = sorted(people, key = lambda person: person.age) print(people2) # 문제 : 이름으로 오름차순 정렬 후, 같은 이름일 경우 나이가 더 많은 순으로 정렬하고 결과를 출력하세요. people3 = sorted(people, key = lambda person: (person.name, -person.age)) print(people3) # 문제 : 나이로 오름차순 정렬 후, 같은 나이일 경우 이름을 알파벳 역순으로 정렬하고 결과를 출력하세요. ## 먼저 이름을 기준으로 역순정렬을 한다. people4 = sorted(people, key = lambda person: person.name, reverse = True) ## 그 이후에 나이로 정렬하면, 나이가 같은 것들은 자연스럽게 원래의 순서(이름 역순)을 유지하게 된다. people4.sort(key = lambda person: person.age) print(people4) ``` #### 추가설명, 나이로 오름차순 정렬 후, 같은 나이일 경우 이름을 알파벳 역순으로 정렬하려면 2번 정렬 해야 함 - 2차 정렬을 할 때 나이가 같은 사람의 경우에는 순서를 바꾸지 않는다. 즉 1차의 정렬결과가 그들 사이에서 유지된다. ``` -- 원본 리스트 -- 순서 1 : [홍길동, 24살] 순서 2 : [홍길동, 25살] 순서 3 : [홍길순, 25살] -- 1차 정렬(이름 내림차순) -- 순서 1 : [홍길순, 25살] 순서 2 : [홍길동, 25살] 순서 3 : [홍길동, 24살] -- 2차 정렬(나이 오름차순) -- 순서 1 : [홍길동, 24살] 순서 2 : [홍길순, 25살] 순서 3 : [홍길동, 25살] ``` ## 객체정렬, lt 메서드 오버라이드 ### 문제 3 - 다음과 같은 'Student' 객체 리스트를 활용하여 아래의 작업을 수행해주세요. ```py class Student: def __init__(self, name, grade, score): self.name = name self.grade = grade self.score = score students = [ Student('Alice', 3, 85), Student('Bob', 2, 90), Student('Charlie', 2, 88), Student('Alice', 1, 95), Student('Paul', 3, 78), Student('David', 3, 78) ] ``` #### 작업 - 학년(grade)으로 오름차순 정렬 후, 같은 학년일 경우 점수(score)가 높은 순으로 정렬하고 결과를 출력하세요. - 점수(score)로 내림차순 정렬 후, 같은 점수일 경우 이름을 알파벳 역순으로 정렬하고 결과를 출력하세요. 이름까지도 같은 학생이 존재한다면 학년으로 정렬해주세요. #### 정답 ```py # 학년(grade)으로 오름차순 정렬 후, 같은 학년일 경우 점수(score)가 높은 순으로 정렬하고 결과를 출력하세요. class Student: def __init__(self, name, grade, score): self.name = name self.grade = grade self.score = score def __repr__(self): return f"Student(name='{self.name}, grade='{self.grade}', score='{self.score}')" def __lt__(self, other): if self.grade != other.grade: return self.grade < other.grade else: return self.score > other.score students = [ Student('Alice', 3, 85), Student('Bob', 2, 90), Student('Charlie', 2, 88), Student('Alice', 1, 95), Student('Paul', 3, 78), Student('David', 3, 78) ] students.sort() print(students) del Student, students # 점수(score)로 내림차순 정렬 후, 같은 점수일 경우 이름을 알파벳 역순으로 정렬하고 결과를 출력하세요. # 이름까지도 같은 학생이 존재한다면 학년으로 정렬해주세요. class Student: def __init__(self, name, grade, score): self.name = name self.grade = grade self.score = score def __repr__(self): return f"Student(name='{self.name}, grade='{self.grade}', score='{self.score}')" def __lt__(self, other): if self.score != other.score: return self.score < other.score elif self.name != other.name: return self.name > other.name else: return self.grade < self.grade students = [ Student('Alice', 3, 85), Student('Bob', 2, 90), Student('Charlie', 2, 88), Student('Alice', 1, 95), Student('Paul', 3, 78), Student('David', 3, 78) ] students.sort() print(students) del Student, students ``` ## 힙큐 개념 ```py # Python에서 heap은 `heapq` 모듈을 통해 사용할 수 있습니다. # 힙은 우선순위 큐를 구현하는 좋은 방법입니다. # 힙은 모든 부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리입니다. import heapq # 기본적인 heapq 사용 nums = [3, 1, 4, 1, 5, 9, 2, 6] heap = [] for num in nums: heapq.heappush(heap, num) # 힙에 원소 추가 print(heap) del nums, heap # heapq에서 가장 작은 원소 추출 nums = [3, 1, 4, 1, 5, 9, 2, 6] heap = [] for num in nums: heapq.heappush(heap, num) print(heapq.heappop(heap)) # 출력: 1 del nums, heap # 리스트를 힙으로 변환 nums = [3, 1, 4, 1, 5, 9, 2, 6] heapq.heapify(nums) print(nums) del nums # 힙에서 가장 큰 원소 추출 nums = [3, 1, 4, 1, 5, 9, 2, 6] heap = [] for num in nums: heapq.heappush(heap, -num) print(-heapq.heappop(heap)) # 출력: 9 del nums, heap # 힙을 이용한 K번째 최대 원소 찾기 nums = [3, 1, 4, 1, 5, 9, 2, 6] heap = [] k = 3 for num in nums: heapq.heappush(heap, num) if len(heap) > k: heapq.heappop(heap) print(heapq.heappop(heap)) # 출력: 3 (세 번째로 큰 원소) del nums, heap, k # heapq nlargest, nsmallest nums = [3, 1, 4, 1, 5, 9, 2, 6] print(heapq.nlargest(3, nums)) # 출력: [9, 6, 5] print(heapq.nsmallest(3, nums)) # 출력: [1, 1, 2] del nums # 객체를 가진 heapq class Person: def __init__(self, name, age): self.name = name self.age = age def __lt__(self, other): return self.age < other.age people = [Person('John', 20), Person('Jane', 19), Person('Adam', 21)] heap = [] for person in people: heapq.heappush(heap, person) while heap: person = heapq.heappop(heap) print(person.name, person.age) # 출력: Jane 19, John 20, Adam 21 del Person, people, heap ``` ## 힙큐 ## 힙큐 문제 1, 최소값, 최대값 추출 ### 문제 1 - 다음과 같이 주어진 리스트를 활용하여 아래의 작업을 수행해주세요. ```py nums = [15, 22, 7, -8, 33, 12, 42, -3, 18, 29, -11] ``` #### 작업 - heapq 모듈을 활용하여 nums 리스트를 최소 힙으로 변환하고 결과를 출력하세요. - 최소 힙에서 가장 작은 원소를 추출하고, 그 후의 힙의 상태를 출력하세요. - 변환한 힙에서 가장 큰 원소를 추출하고, 그 후의 힙의 상태를 출력하세요. #### 정답 ```py import heapq ### 문제 1 # 다음과 같이 주어진 리스트를 활용하여 아래의 작업을 수행해주세요. nums = [15, 22, 7, -8, 33, 12, 42, -3, 18, 29, -11] #### 작업 # heapq 모듈을 활용하여 nums 리스트를 최소 힙으로 변환하고 결과를 출력하세요. heapq.heapify(nums) print(nums) # 최소 힙에서 가장 작은 원소를 추출하고, 그 후의 힙의 상태를 출력하세요. smallest = heapq.heappop(nums) print(smallest) # 변환한 힙에서 가장 큰 원소를 추출하고, 그 후의 힙의 상태를 출력하세요. ## 부호반전 for i in range(len(nums)): nums[i] = -nums[i] ## 다시 정렬 heapq.heapify(nums) ## 최대값 가져오기(최소값을 가져오고 부호반전) largest = -heapq.heappop(nums) print(largest) ``` ### 문제 2 - 다음과 같이 주어진 리스트를 활용하여 아래의 작업을 수행해주세요. ```py nums = [3, 2, 5, 1, 8, 7, 4, 9, 6] ``` ## 힙큐 문제 2, 최소값, 최대값 여러개 추출 #### 작업 - heapq 모듈을 활용하여 nums 리스트에서 4번째로 큰 원소를 찾으세요. - heapq의 nlargest 함수와 nsmallest 함수를 활용하여 리스트에서 가장 큰 3개의 원소와 가장 작은 3개의 원소를 찾으세요. #### 정답 ```py import heapq nums = [3, 2, 5, 1, 8, 7, 4, 9, 6] k = 4 # heapq 모듈을 활용하여 nums 리스트에서 4번째로 큰 원소를 찾으세요. print(heapq.nlargest(k, nums)[-1]) # heapq의 nlargest 함수와 nsmallest 함수를 활용하여 리스트에서 가장 큰 3개의 원소와 가장 작은 3개의 원소를 찾으세요. print(heapq.nlargest(3, nums)) print(heapq.nsmallest(3, nums)) ``` ## 힙큐 문제 3, 객체 다루기 ### 문제 3 - 다음과 같은 'Car' 객체 리스트를 활용하여 아래의 작업을 수행해주세요. ```py class Car: def __init__(self, model, speed): self.model = model self.speed = speed def __lt__(self, other): return self.speed < other.speed cars = [Car('Sedan', 120), Car('SUV', 110), Car('Sports', 160), Car('Truck', 80), Car('Convertible', 140)] ``` #### 작업 - heapq 모듈을 활용하여 Car 객체 리스트를 속도(speed)를 기준으로 하는 최소 힙으로 변환하세요. - 생성한 힙에서 가장 빠른 차를 추출하고 그 후의 힙 상태를 출력하세요. #### 정답 ```py import heapq class Car: def __init__(self, model, speed): self.model = model self.speed = speed def __repr__(self): return f"Car(model='{self.model}', speed={self.speed})" def __lt__(self, other): # 이 부분의 괄호를 < 에서 > 로 바꿔야 합니다. return self.speed > other.speed cars = [Car('Sedan', 120), Car('SUV', 110), Car('Sports', 160), Car('Truck', 80), Car('Convertible', 140)] # heapq 모듈을 활용하여 Car 객체 리스트를 속도(speed)를 기준으로 하는 최소 힙으로 변환하세요. heapq.heapify(cars) # 생성한 힙에서 가장 빠른 차를 추출하고 그 후의 힙 상태를 출력하세요. print(heapq.heappop(cars)) ``` ## 다익스트라 개념과 구현 ![img](https://showme.redstarplugin.com/d/0Sz8eXsG) ```py import heapq def dijkstra(graph, start): # 1. 특정 지점까지의 거리를 무한대로 설정한다. distances = {node: float('inf') for node in graph} # 2. 시작점을 정한다. distances[start] = 0 # 3. 시작점을 큐에 넣는다. queue = [(distances[start], start)] while queue: # 4. 큐에서 가장 가까운 노드를 꺼낸다. current_distance, current_node = heapq.heappop(queue) # 5. 해당 노드를 방문했는지 확인한다. if current_distance > distances[current_node]: continue for nei_distance, nei_node in graph[current_node]: # 6. 현재 노드를 거쳐서 이웃 노드로 가는 거리를 계산한다. distance = current_distance + nei_distance # 7. 계산한 거리가 기존의 이웃 노드까지의 거리보다 작다면 if distance < distances[nei_node]: # 거리 값을 갱신하고 distances[nei_node] = distance # 우선순위 큐에 이웃 노드와 갱신된 거리를 넣는다. heapq.heappush(queue, (distance, nei_node)) return distances graph = { '서울': [(85, '천안'), (160, '대전'), (330, '부산')], '천안': [(85, '서울'), (70, '대전'), (305, '부산')], '대전': [(70, '천안'), (160, '서울'), (145, '대구')], '대구': [(145, '대전'), (100, '부산')], '부산': [(100, '대구'), (330, '서울'), (305, '천안')] } start_city = "서울" shortest_distances = dijkstra(graph, start_city) print("출발 도시 :", start_city) for city, distance in shortest_distances.items(): print(city + "까지 최단 거리 :", distance) ``` ### 초기 설정 - 모든 도시까지의 거리는 무한대(`inf`)로 설정됩니다. 시작 도시인 '서울'까지의 거리는 0입니다. ```python distances = {'서울': 0, '천안': inf, '대전': inf, '대구': inf, '부산': inf} queue = [(0, '서울')] ``` ### 첫 번째 업데이트 - '서울'과 직접 연결된 도시들('천안', '대전', '부산')까지의 거리가 각 도시까지의 직접 거리로 업데이트됩니다. ```python distances = {'서울': 0, '천안': 85, '대전': 160, '대구': inf, '부산': 330} queue = [(85, '천안'), (160, '대전'), (330, '부산')] ``` ### 두 번째 업데이트 - '서울'을 거쳐 '천안'으로 가는 경로를 통해 '대전'까지의 거리가 업데이트됩니다. - '서울'에서 '천안'으로 가는 거리(85)와 '천안'에서 '대전'으로 가는 거리(70)를 합하면 155이며, - 이는 이전에 계산된 '서울'에서 '대전'까지의 거리(160)보다 짧습니다. ```python distances = {'서울': 0, '천안': 85, '대전': 155, '대구': inf, '부산': 330} queue = [(155, '대전'), (160, '대전'), (330, '부산')] ``` ## 탐욕법 개념 ### 개념 - 탐욕법 (greedy algorithm)은 최적화 문제를 해결하는 알고리즘 중 하나입니다. - 이는 매 순간 최적의 선택을 하도록 하여 전체적으로 보았을 때 최적의 결과를 도출하려는 방법입니다. - 탐욕법은 다음과 같은 특징을 가집니다: - 각 단계에서 지역적으로 최적의 선택을 합니다. - 이 선택은 그 선택이 있을 때 당장은 최선의 해결책으로 보입니다. - 이러한 선택들을 통해 최종적으로 전역적인 해결책을 찾아냅니다. - 하지만 탐욕법이 항상 최적의 해결책을 제공하는 것은 아닙니다. - 일부 문제에 대해선 탐욕적인 선택이 최적의 해결책으로 이어지지만, - 그렇지 않은 문제들도 있습니다. 이러한 경우 다른 알고리즘을 사용해야 합니다. ## 탐욕법 문제 1, 최소한의 동전개수로 교환하는 방법 ### 문제 1 - 동전들이 있습니다. 각 동전의 금액은 각각 500원, 100원, 50원, 10원입니다. 주어진 금액을 최소한의 동전 개수로 교환하는 방법을 찾아주세요. #### 작업 - 주어진 금액을 입력 받아 최소한의 동전 개수로 교환하고 결과를 출력하세요. #### 코드 ```py def change_money(money): # TODO: 이곳에 코드를 작성하세요. pass # Test the function money = 1260 print(change_money(money)) # 예상 출력: {500: 2, 100: 2, 50: 1, 10: 1} ``` #### 정답 ```py def change_money(money): answer = {} coins = [500, 100, 50, 10] for coin in coins: count, money = divmod(money, coin) answer[coin] = count return answer # Test the function money = 1260 print(change_money(money)) # 예상 출력: {500: 2, 100: 2, 50: 1, 10: 1} ``` ## 탐욕법 문제 2, 최대한 많은 일을 수행하는 방법 ### 문제 2 - 주어진 시간 내에 가능한 많은 일을 하려고 합니다. - 각 일에는 시작 시간과 끝나는 시간이 있습니다. - 일은 시작 시간과 끝나는 시간이 겹치지 않게 일정을 짜야 합니다. - 주어진 일들 중에서 가장 많은 일을 할 수 있는 방법을 찾아주세요. - 힌트 : 끝나는 시간을 기준으로 오름차순을 한 후 진행해주세요. #### 작업 - 주어진 일들의 시작 시간과 끝나는 시간을 입력 받아 가능한 많은 일을 할 수 있는 일정을 출력하세요. #### 코드 ```py def schedule_jobs(jobs): # TODO: 이곳에 코드를 작성하세요. pass # Test the function jobs = [(5, 7), (12, 14), (1, 4), (6, 10), (0, 6), (3, 5), (8, 12), (2, 13), (5, 9), (3, 8), (8, 11)] print(schedule_jobs(jobs)) # 예상 출력: [(1, 4), (5, 7), (8, 11), (12, 14)] ``` #### 정답 ```py def schedule_jobs(jobs): # 끝나는 시간을 기준으로 작업들을 오름차순 정렬 jobs.sort(key=lambda x: x[1]) # 선택된 작업들을 저장하는 리스트 selected_jobs = [jobs[0]] for i in range(1, len(jobs)): # 현재 작업의 시작 시간이 선택된 마지막 작업의 끝나는 시간 이후인 경우 선택 if jobs[i][0] >= selected_jobs[-1][1]: selected_jobs.append(jobs[i]) return selected_jobs # Test the function jobs = [(5, 7), (12, 14), (1, 4), (6, 10), (0, 6), (3, 5), (8, 12), (2, 13), (5, 9), (3, 8), (8, 11)] print(schedule_jobs(jobs)) # 예상 출력: [(1, 4), (5, 7), (8, 11), (12, 14)] ``` ## 탐욕법 문제 3, k번째로 작은 요소를 찾는 효율적인 방법 ### 문제 3 - 주어진 배열에서 k번째로 작은 요소를 찾는 문제입니다. - 이 문제는 힙 큐를 사용하여 효율적으로 해결할 수 있습니다. - 힌트 : 힙에 k개 보다 많은 요소가 추가되었다면 pop 으로 제거하여 높은 효율성 추구 #### 작업 - 주어진 배열과 k를 입력 받아 k번째로 작은 요소를 찾아 출력하세요. ```py def find_kth_largest(nums, k): # TODO: 이곳에 코드를 작성하세요. pass # Test the function nums = [3,2,1,5,6,4] k = 2 print(find_kth_largest(nums, k)) # 예상 출력: 2 ``` #### 정답 ```py import heapq def find_kth_smallest(nums, k): # 배열에서 가장 작은 k개의 요소를 반환 return heapq.nsmallest(k, nums)[-1] # 가장 작은 k개의 요소 중 마지막 요소가 k번째로 작은 요소임 # Test the function nums = [3,2,1,5,6,4] k = 2 print(find_kth_smallest(nums, k)) # 예상 출력: 2 ``` ## DP 개념, DP는 메모의 활용이다. ### 개념 - 동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 분해하고, - 이 하위 문제의 결과를 저장하여 이용함으로써 전체 문제를 효율적으로 해결하는 알고리즘 설계 방법론입니다. - DP는 크게 두 가지 개념, 즉 최적 부분 구조(Optimal Substructure)와 중복된 하위 문제(Overlapping Subproblems)를 활용합니다. - 최적 부분 구조 - 큰 문제의 최적 해결 방법이 그것을 구성하는 작은 문제들의 최적 해결 방법으로부터 도출될 수 있음을 의미합니다. - 즉, 전체 문제의 최적해가 부분 문제의 최적해를 통해 구할 수 있다는 것입니다. - 중복된 하위 문제 - 동일한 하위 문제가 반복적으로 발생함을 의미합니다. - 이러한 중복을 피하기 위해, 한 번 계산된 하위 문제의 결과를 메모이제이션(Memoization) - 등의 방법을 통해 저장해 두었다가 재활용하는 방식이 특징입니다. - 예를 들어, 피보나치 수열을 계산하는 문제를 생각해보면, - 피보나치 수열의 n 번째 값을 구하기 위해서는 n-1 번째 값과 n-2 번째 값을 알아야 합니다. - 이때, n-1 번째와 n-2 번째 값을 각각 구하는 데 있어서 중복되는 계산이 많이 발생하는데, - 이를 동적 계획법을 사용하여 한 번 계산된 값을 재사용함으로써 효율적으로 해결할 수 있습니다. ## 피보나치에 DP 적용하기 ### 문제 ```py # 메모이제이션을 활용해서 피보나치를 구현해주세요. def fibonacci(n): '''구현''' # 테스트 print(fibonacci(10)) # 55 ``` ### 정답 ```py # 메모이제이션을 위한 딕셔너리를 전역 변수로 선언합니다. # 이 딕셔너리는 계산된 피보나치 수열의 값을 저장하는데 사용됩니다. fib_cache = {0: 0, 1: 1} # 첫 번째와 두 번째 피보나치 수는 0과 1로 초기화합니다. def fibonacci(n): # fib_cache는 이 함수 바깥에서 선언된 전역 변수입니다. # 따라서 이를 함수 내에서 변경하려면 global 키워드를 사용해야 합니다. global fib_cache # n이 fib_cache의 키로 존재하면, 이미 계산된 값이므로 이를 반환합니다. if n in fib_cache: return fib_cache[n] # n이 fib_cache의 키로 존재하지 않는다면, 아직 계산되지 않은 값이므로 피보나치 수를 계산합니다. fib_cache[n] = fibonacci(n-1) + fibonacci(n-2) return fib_cache[n] # 테스트 print(fibonacci(10)) # 55 ``` ## 특정 금액을 최소한의 동전들로 구성 ### 정답 ```py def coinChange(coins, amount): '''구현''' # 테스트 coins = [1, 3, 4] # 동전의 종류 amount = 6 # 목표 금액 coinChange(coins, amount) # 결과 출력 : 2 ``` ### 정답 ```py def coinChange(coins, amount): # dp 배열 초기화 dp = [amount + 1] * (amount + 1) # 0원을 만드는데 필요한 동전 개수는 0개 dp[0] = 0 # 모든 금액에 대해 for money in range(1, amount + 1): # 각 동전에 대해 for coin in coins: # 동전의 액면가가 현재 금액보다 작거나 같으면 if coin <= money: # 현재 금액을 만드는데 필요한 최소 동전 개수를 업데이트 dp[money] = min(dp[money], dp[money - coin] + 1) # 최종 금액을 만드는데 필요한 최소 동전 개수가 '무한대'라면 -1 반환 if dp[amount] > amount: return -1 else: return dp[amount] # 테스트 coins = [1, 3, 4] # 동전의 종류 amount = 6 # 목표 금액 coinChange(coins, amount) # 결과 출력 : 2 ```