sjmin

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net from collections import deque n, m, v = map(int, input().split()) graph = [[False] * (n + 1) for _ in range(n + 1)] for i in range(m): a, b = map(int, input().split()) graph[a][b] = True graph[b][a] = T..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net from collections import deque n, m = map(int, input().split()) # 2차원 리스트의 맵 정보 입력받기 graph = [] for i in range(n): graph.append(list(map(int, input()))) # 이동할 네 방향 정의(상, 하, 좌, 우) dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] def bfs(x,y): # 큐(Queue) ..

1. BFS(Breadth-First Search) 너비 우선탐색이라고 부르며, 가까운 노드부터 탐색하는 알고리즘이다. 선입선출 방식인 큐 자료구조를 이용하고, 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. BFS 동작 과정 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. cf) 방문처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다. 위 그래..

1. DFS(Depth-First Search) 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 2. 그래프(Graph) 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드간 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식 인접 행렬(Adjacency Matrix) 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이..

탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 데이터를 표현하고, 관리하고, 처리하기 위한 구조 스택(Stack)과 큐(Queue)를 구성하는 핵심 함수 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : 데이터를 삭제한다. 실제로는 스택(Stack)과 큐(Queue)를 사용할 때, 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야 한다. 오버플로(Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다. 즉, 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생한다. 언더플로(Underflow) : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행해 데이터가 전혀 없는 상태이다. 1. 스택(..

https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net import itertools n, m = map(int, input().split()) numbers = list(map(int, input().split())) result = 0 for number in itertools.combinations(numbers, 3): if result < sum(number)

1. 구현 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 2. 파이썬에서 리스트 크기 대체로 코딩 테스트에서는 128~512MB로 메모리를 제한하는데, 이럴 때는 메모리 제한을 염두해두고 코딩을 해야 한다. 아래는 우리가 흔히 사용하는 int 자료형의 데이터 개수이다. 데이터의 개수(리스트의 길이) 메모리 사용량 1,000 약 4KB 1,000,000 약 4MB 10,000,000 약 40KB 파이썬은 다른 언어에 비해 구현상의 복잡도는 낮지만, 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하자. 만약, 크기가 1,000 이상인 리스트가 있다면, 메모리 용량 제한..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net N = int(input()) P = list(map(int,input().split())) P.sort() count = 0 for i in range(N): for j in range(i + 1): count += P[j] print(count)

https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net a = 1000 - int(input()) change = [500, 100, 50, 10, 5, 1] count = 0 for coin in change: count += a // coin a %= coin print(count)

1. 그리디 어떤 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘(현재 상황에서 지금 당장 좋은 것만 고르는 방법) 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즈이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 자주 정렬 알고리즘과 짝을 이룬다. 거스름돈 문제로 예를 들면, '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것' 처럼 간단한 아이디어를 떠올려 문제를 해결할 수 있다. n = 1260 count = 0 # 큰 단위의 화폐부터 차례대로 확인 coin_types = [500, 100, 50, 10] for coin in coin_types: count ..