생각하는 아져씨

문제는 다음과 같다. 🚦 문제 유형 - Graph Traversal (그래프 탐색) - DFS/BFS ✏️ Solution 제목에 DFS/BFS 가 명시된 문제로, 전형적인 DFS/BFS 알고리즘을 그대로 사용해 풀었다. from collections import deque import sys input = sys.stdin.readline n, m, v = map(int, input().split(' ')) graph = [[] for i in range(n+1)] for _ in range(m): f, s = map(int, input().split(' ')) graph[f].append(s) graph[s].append(f) visited = [False]*(n+1) visited2 = [False..

문제는 다음과 같다. 🚦 문제 유형 - Graph Traversal (그래프 탐색) - DFS/BFS ✏️ Solution DFS/BFS 문제로, DFS를 이용해 풀었다. n = int(input()) m = int(input()) # 연결된 그래프 리스트 만들기 graph = [] for i in range(n+1): graph.append([]) for i in range(m): f, s = map(int, input().split(' ')) graph[f].append(s) graph[s].append(f) visit = [False] * (n+1) # dfs def dfs(start, graph, visit): visit[start] = True for i in graph[start]: if vi..

DFS/BFS 들어가기 전 탐색은 그래프, 트리 등 자료구조 안에서 자주 다룬다. DFS와 BFS를 이해하려면 기본 자료구조인 스택과 큐 그리고 재귀함수를 이해하고 있어야 함 스택: FILO(First In Last Out) 큐: FIFO(First In First Out) 스택과 큐를 사용할 땐 Overflow와 Underflow를 고려해야 함 파이썬에서는 스택 → 파이썬 리스트 큐 → collections 모듈에서 제공하는 deque 자료구조 재귀함수: 자기 자신을 다시 호출하는 함수 재귀함수는 내부적으로 스택 자료구조 이용 (가장 마지막에 호출한 함수가 끝나야 그 앞의 함수 호출이 종료되기 때문이다.) 꼭 종료조건을 구현해줘야 함 반복문 보다 코드가 간결 DFS(Depth-First Search) ..

구현 머릿 속에 떠오르는 아이디어를 소스코드로 바꾸는 과정이다. 어떤 문제든 모든 범위의 코딩 테스트 문제는 구현 문제에 포함된다. 보통, 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다. 알고리즘은 간단한데 코드가 길어지는 문제 특정 소수점 자리까지 출력하는 문제 문자열을 한 문자 단위로 끊어서 파싱해야 하는 문제 완전 탐색, 시뮬레이션은 둘 다 구현이 핵심이 되는 경우가 많기 때문에 이 장에서 다룬다. 구현 시 고려해야 할 메모리 제약 사항 (Python) 파이썬에서 리스트 크기데이터 개수(리스트 길이) 메모리 사용량 1,000 약 4KB 1,000,000 약 4MB 10,000,000 약 40MB 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없..

Greedy 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 이용하는 알고리즘으로 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 따라서 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. (그리디 알고리즘의 정당성) 보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘 이므로, 그 기준을 알게 모르게 제시해준다. EX) ‘가장 큰 순서대로', ‘가장 작은 순서대로' 와 같은 기준 → 자주 정렬 알고리즘과 짝을 이뤄 출제된다. 다익스트라 최단경로 알고리즘, 크루스칼 알고리즘 모두 그리디 알고리즘에 속한다. ..

"이것이 코딩테스트다" 알고리즘 유형별 기출문제 - 그리디 Q6 이 문제는 그리디 알고리즘 접근 방식으로 해결할 수 있다. 하지만 그리디 알고리즘의 초보인 나에게 꽤 어려운 문제였다. 일단, 정확성 풀이에 집중한 나머지 효율성을 고려하지 못했다. 또한 효율성을 고려하려니 그리디 알고리즘의 아이디어가 떠오르지 않았다. 문제 설명 평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다. 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음..