IT/Python4 이코테 2021]3. DFS & BFS https://youtu.be/7C9RgOcvkvo 스택(stack): 선입후출 예시 코드 stack=[] 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) # 최하단 원소부터 출력 큐(queue) 파이썬에서 단순히 list 자료형으로도 queue를 기능적으로 구현할 수 있으나, 시간복잡도가 높아 비효율적으로 동작할 수 있기 때문에, deque 라이브러리를 사용하는게 좋다 from collections import deque # 큐(Queue) 구현을 위해 deq.. 2022. 10. 3. 이코테 2021] 3. 스택, 큐, 재귀함수 https://youtu.be/7C9RgOcvkvo 그래프 탐색 알고리즘 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 ex) DFS, BFS : 코딩 테스트에서 매우 자주 등장하는 유형 스택 자료구조 먼저 들어온 데이터가 나중에 나가는 형식(선입후출) 입구와 출구가 동일한 형태 파이썬에서의 스택 : 리스트(List) stack = [] stack.append(5) # 삽입 stack.append(2) stack.append(3) stack.append(7) stack.pop() print(stack[::-1]) # 최상단 원소부터 출력 == 먼저 나가고자 하는 원소부터 print(stack) # 최하단 원소부터 출력 == 가장 먼저 들어온 순서부터 큐 자료구조 먼저 들어 온.. 2022. 10. 3. 이코테 2021] 2. 구현 강의 노트 https://youtu.be/2zjoKjt97vQ 구현(Implementation) 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 알고리즘 대회에서 구현 유형의 문제란? 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭 구현 유형의 예시 알고리즘은 간단한데, 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루거나, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아 사용해야 하는 문제 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix) 의 의미로 사용된다. for i in range(5): for j in range(5): print('(',i,',',j,')',end=' ') print() 시뮬레이션 및.. 2022. 10. 3. 이코테 2021] 2. 그리디 강의 노트 https://youtu.be/2zjoKjt97vQ 그리디 알고리즘 (=탐욕법) \ 현재 상황에서 지금 당장 좋은 것만 고르는 방법 \ 정당성 분석이 중요! ex) 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶을 때, Q: 단순히 매 상황에서 가장 큰 값만 고르는 법 : 그리디 알고리즘 문제점: 최적의 해를 보장할 수 없을 때가 많음 but 코테에서 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨 거스름 돈 문제 문제 해결 아이디어 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 됨 Ex) 1,260원 : 500 / 100 / 50 / 10 => 2/2/1/1 정당성 분석: 최적의 해를 보장하.. 2022. 10. 3. 이전 1 다음
