# 답 from collections import deque N, M = map(int, input().split()) board = [input() for _ in range(N)] chk = [[False] * M for _ in range(N)] dy = (0, 1, 0, -1) dx = (-1, 0, 1, 0) def is_valid_coord(y, x): return 0
Algorithm
그래프 구성 - 정점 (Vertex 또는 Node) - 간선 (Edge) 그래프의 연결 요소 Connected Component - 서로 완전히 분리된 요소들을 '연결 요소'라고 합니다. - 위 그림은 각각의 그래프 2개가 아닌, 연결 요소 2개로 이뤄진 그래프 1개 입니다. 그래프의 분류 1. 그래프의 방향성 방향 그래프 방향이 정해져 있음 무방향 그래프 어느 방향으로 가도 상관 없음 (양방향 그래프) 2. 그래프의 순환성 순환 그래프 순환하는 부분이 한 군데만 있어도 순환 그래프 비순환 그래프 순환하는 부분이 전혀 없음 * DAG (Directed Acycilc Graph) : 방향성 비순환 그래프 * 트리 (Tree) : 무방향 비순환 그래프 더보기 ※ 트리 Tree - 위와 같은 모양을 한 그래프..
# 원리 종료 시간이 제일 빠른 회의부터 차례대로 고르면 됩니다. 만일 종료 시간이 동일한 회의가 여러 개라면, 그 중 아무거나 골라도 됩니다. 종료 시간이 동일하다면 회의 시간이 필연적으로 겹치기 때문입니다. 단, 종료 시간과 시작 시간이 동일한(회의 시간이 0인) 회의는 예외입니다. 예를 들어 시작 시간과 종료 시간이 아래와 같은 회의 4개가 있다고 가정해봅시다. 회의 시작 시간 종료 시간 A 7 10 B 8 10 C 9 10 D 10 10 종료 시간이 동일한 회의 A, B, C 중에서는 그 어느 회의를 골라도 상관이 없습니다. 회의 D 또한 회의 A, B, C와 종료 시간이 동일하지만, D는 시작 시간과 종료 시간이 동일하기 때문에 예외로 생각해야합니다. 회의 A, B, C 중 하나가 끝나고 나면 ..
탐욕법 Greedy Algorithm - 항상 현재 상태에서 최선의 경우만 탐욕스럽게 고르는 전략입니다. - 완전탐색과 달리 모든 경우를 살펴보지는 않습니다. - 그리디 문제들은 특별한 배경지식이 없더도 문제에서 규칙성을 찾으면 풀 수 있는 편입니다. - 다만 난이도를 아주 쉬운 문제부터 매우 어렵게까지, 출제자 마음대로 만들 수 있습니다. - 그리디 문제의 진짜 어려운 부분은 바로 '이 문제가 그리디 문제인지 판별하는 것'입니다. 탐욕법 대표 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 위 '회의실 배정'문제는 활동 선택 문제(Activity sel..
# 팁 1 이 문제를 풀면서 알게 된, 이 문제를 풀 때 도움이 되는 팁 몇 가지를 소개해보겠습니다. 첫 번째 팁은 위와 같이 입력 형식으로 2차원 배열이 주어졌을 때, 이를 편리하게 입력받는 방법입니다. n = int(input()) board = [list(input()) for _ in range(n)] 이렇게 코드를 작성하면, n개의 행으로 이뤄진 2차원 배열을 입력받을 수 있습니다. 행의 개수가 n개이면 되지 열의 개수까지 n개일 필요는 없습니다. 심지어, 모든 행이 다른 열의 개수를 가지고 있어도 오류가 뜨지 않는 코드입니다. # 팁 2 두 번째 팁은 글로벌 변수(전역 변수)를 사용하는 방법입니다. val = 1 def f(): val = 2 위 코드에서 첫 번째로 등장한 변수 val은 두 번..
완전탐색 - 모든 경우를 다 살펴본다! - 거의 같은 의미인 '브루트 포스(무차별 대입)'라는 용어로도 불립니다. - 완전탐색은 모든 경우를 살펴보기에 시간이 오래 걸립니다. 시간을 단축시키고 싶다면 백트래킹을 사용합니다. 백트래킹이란 탐색 과정에서 더 이상 답이 되지 않는 분기를 발견했을 때 되돌아가는 기법을 의미합니다. - 완전탐색은 크게 반복문 / 재귀 / 큐로 구현할 수 있습니다. 관련 알고리즘 반복문 순열 조합 DFS 재귀 큐 BFS 순열 permutation n개의 수 중 r개를 뽑아 줄을 세우는 방법의 수 1. 라이브러리 사용하기 from itertools import permutations arr = [0, 1, 2, 3] for i in permutations(arr, 4): print(..
# 접근법 우선순위 큐를 이용합니다. 최소 힙의 크기를 N으로 고정시켜가며 숫자들을 힙에 넣었다 뺐다 반복합니다. 최소 힙에서 요소를 제거할 때는 항상 최솟값이 제거되므로, 모든 수를 넣었다 빼기를 반복했을 때 최종적으로 힙에 남게 되는 수들은 N * N개의 숫자들 중 제일 큰 숫자 N개가 됩니다. * 이 방법은 '모든 수는 자신의 한 칸 위에 있는 수보다 크다'라는 규칙을 딱히 이용하지 않고 풀 수 있는 풀이법입니다. # 답 import heapq h = [] n = int(input()) for _ in range(n): s = map(int, input().split()) for i in s: if len(h) >= n: heapq.heappushpop(h, i) else: heapq.heappus..
# 문제상황 아래와 같이 후위표기식을 받을 때 피연산자를 알파벳 대문자로 받은 뒤, 그 후 각 알파벳 문자 자리에 치환 될 숫자를 입력받습니다. 저는 이 문제를 문자열의 'replace' 함수를 사용해서 알파벳과 숫자의 위치를 바꿔 풀려고 했었는데, 결론부터 말하면 그렇게 풀면 안 됩니다. 입력되는 숫자가 모두 1자리수 라는 보장만 있다면 문자열 replace 함수를 써도 풀리겠지만, 숫자가 2자릿수를 넘어가버리면 풀이가 꼬여버립니다. 나중에 후위표기식 문자열에서 실제 연산을 위해 값을 읽어올 때, 문자 1개만 가져와야할지 2개를 가져와야할지 알 수 없기 때문입니다. 그럼 어떻게 풀어야 할까요? # 해결 입력받는 숫자들이 차례대로 'A, B, C...'에 대응된다는 점이 핵심입니다. val = [] fo..
1. 배열 Array 기본 자료형인 리스트를 배열처럼 사용합니다. 시간 복잡도 임의 접근 O(1) 삽입 / 삭제 O(N) 2. 스택 Stack 기본 자료형인 리스트를 스택처럼 사용합니다. stk = [] stk.append(x) #리스트의 맨 뒤에 요소를 삽입합니다. stk.pop() #리스트의 맨 뒤 요소를 반환하고 삭제합니다. (괄호 안을 비워뒀을 경우) 스택은 한 쪽에서만 데이터를 넣고 뺄 수 있는 자료구조입니다. 이러한 스택의 특징을 FILO(First-In-Last-Out) 또는 LIFO(Last-In-First-Out)라고 부릅니다. 시간 복잡도 삽입 / 삭제 O(1) 3. 덱 Deque 덱을 import해서 사용합니다. from collections import deque dq = deque..
# 팁 1 이 문제는 자료구조 맵을 이용하는 문제입니다. 파이썬에서 맵은 딕셔너리라는 자료형으로 구현하면 됩니다. 그렇게까지 까다로운 문제는 아니지만, 딕셔너리를 활용하는 방법을 잘 모른다면 조금 까다로울 수 있습니다. 따라서 이 문제를 푸는데에 도움이 되는 딕셔너리를 사용하는 몇 가지 팁을 정리해 보겠습니다. 첫 번째 팁은 '빈 딕셔너리를 생성하는 방법'입니다. 방법은 2가지 정도 있습니다. 방법 1. d = dict() 방법 2. d = {} 두 방법 모두 변수 d에 비어있는 딕셔너리가 담기게 됩니다. # 팁 2 두 번째 팁은, 딕셔너리에 담겨 있는 요소들의 value 값들 중 최댓값을 찾는 방법입니다. max_val = max(d.values()) # 팁 3 세 번째 팁은 딕셔너리에 있는 요소들을 ..
