Algorithm (PS)

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 내가 바로 백트레킹이다 !!!! 하는 문제 dfs에서 경로에 현재 확인중인 array[nx][ny] 의 알파벳이 들어갈때 확인하고 다시 제거해서 원상복구한다 그러나 시간 초과가 났다... 또륵 괜히 level.5 문제가 아니다 ㅎ # 1987 알파벳 r, c = map(int, input().split()) array = [] for _ in range(r): array.append(inp..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net # 1197 최소 스패닝 트리 v, e = map(int, input().split()) edges = [] parent = [0]*(v+1) for i in range(1, v+1): parent[i] = i def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, ..

try except 문은 이럴때 사용한다 !! 라는 것을 알게되었다. 보통 입력값 갯수가 주어지는데 이문제에서는 안주어져서 어떻게 하나 싶었는데 파이썬에서는 EOF 에러를 잡을 수 있는 구문이 바로 except! except를 이용해서 예외적으로 오류를 처리할 수 있게 해준다. 그리고 풀이는 전위순회의 특성을 이용해서 풀었다 전위순회는 root -> left subtree -> right subtree 순서대로 순회한다. 즉, 1) root는 array[0] # 맨 앞의 원소가 루트노드 2) array를 쭉 확인하다가 처음으로 root보다 큰 값이 나오면 이것이 바로 right subtree의 첫번째 원소가 되므로, left와 right 서브트리의 경계값이 된다 이 두가지를 이용하여 postorder 함..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이진탐색의 시간 복잡도는 O(logN)으로 선형탐색 O(n) 을 사용할 때보다 시간을 단축할 수 있다 # 10815 숫자카드 n = int(input()) card = list(map(int, input().split())) m = int(input()) find = list(map(int, input().split())) card.sort() def bisect(l..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net bfs로 풀기 위해서, 100001개의 공간이 필요하다 이 개수는 문제에서 주어진 노드의 범위(0

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 맨처음 떠올랐던건 직관적인 DFS 이다 dfs로 갈수 있는 방향으로 한칸씩 이동하면서 마지막에 array[n-1][n-1]에 도달하면, (0,0) ~ (n-1,n-1)까지 가는 방법 으로 하나씩 카운트 했다. 주의할점은 dfs로 갈수있는 칸 체크할 때 가로방향이면 x가 범위안에 있는지, x < n-1 세로 방향이면 y가 범위안에 있는지 확인해주어야 한다. y < n-1 대..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 트리의 순회 중 preorder를 구해야 한다 우선 preorder, inorder, postorder에 대해서 알아야 한다 preorder : root -> left child -> right child inorder : left child -> root -> right child postorder : left child -> right child -> root 여기서 주목할 점은 postorder 에서 root가 배열에..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 중위 표기식을 후위표기식으로 바꾸는 문제이다 1. 피연산자 인 경우 : 알파벳인지 아닌지는 isalpha() 함수로 간단히 확인할 수 있다. 파이썬은 짱이다 2. 연산자의 경우 : 우선순위에 따라 stack에서 빼낼지, 여부가 결정된다 우선순위는 ( 왼쪽 괄호 *, / 곱셈 나눗셈 -,+ 뺄셈 덧셈 순으로 높다 ( 가 나오면 우선순위가 가장 높으므로 일단 스택에 쌓는다 / 혹은 * 가 나오면 ..