https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 1. 입력받은 값으로 트리를 구성한다. python의 defaultdict을 사용했다. 어처피 간선 정보는 자식노드 - 부모노드로 N-1개 주어지므로 리스트가 아니라 default(int) 로 value 값을 저장한다. 2. 재귀함수 (dfs)로 루트까지 가는 경로를 구하는 함수 작성 3. 각각의 노드에서 루트까지 가는 경로를 구한다. 4. 경로..
Algorithm (PS)
https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net BFS + 브루트포스로 풀었다 비트마스킹으로도 풀 수 있는 것 같은데 연습해야겠다.. import sys from itertools import combinations from collections import deque input = sys.stdin.readline N, M = map(int, input().split()) array = [list(map(int, input().split())) for..
https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 규칙성을 찾으면 직관적으로 풀 수 있는 dp 문제였다 봤더니 티어가 실버 1 이다 . 딱 그정도 수준인것 같긴 하다 ㅎㅎ.. 말로 설명하기 어려워서 그림으로 그려보았다. 1) 현재 N== 1, 즉 자리가 한자릿수일 때는 자기 자신이 오르막 수에 해당하므로 오르막 수가 1개이다. 0, 1, 2, .. 9 이런 얘들이 한자릿수 오르막 수가 된다. dp[1][i] =..
https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 푸는 로직은 간단하다 1) 주어진 입력값으로 tree를 구성한다. 친절하게도 문제에서는 enroll과 referrel 이 같은 순서로 주어진다. enroll[i] 이 자식노드, referrel[i] 의 원소가 부모노드가 된다 ! 2) seller를 start로 하여 루트 노드 (center)까지 탐색한다 재귀함수를 만들어서 자기 자신을 기준으로 tree에서 부모노드를 꺼내 부모노드로 이동하는 식으..
https://www.acmicpc.net/problem/21922 21922번: 학부 연구생 민상 첫 번째 줄에는 연구실의 크기가 세로 $N(1 \le N \le 2,000)$, 가로 $M(1 \le M \le 2,000)$ 순으로 주어진다. 두 번째 줄부터 $N + 1$ 줄까지 연구실 내부 구조 정보를 알려주는 값 $M$개가 주어진다. $1,2,3,4$ www.acmicpc.net 그래프에서의 시뮬레이션 / 구현 문제이다 물건 종류 1 ~4 가 있고 해당 물건을 만날때마다 에어컨 바람에 대해서 조치를 취해주어야 한다 (방향을 바꾸거나, 에어컨 바람이 그냥 통과하거나, 더이상 앞으로 가지 않는 경우 3가지가 있다) 처음에 놓친부분은 : 1) 물건 3과 물건 4를 처음에 단순히 시계방향 반시계방향으로 생..
https://www.acmicpc.net/problem/10159 플로이드워셜 알고리즘을 이용하면 날먹할 수 있는 문제이다 왜 플로이드 워셜이냐?! 라고 한다면.. 모든 1 ~ N번 노드가 자기자신을 기준으로 했을때 자신을 제외한 모든 노드까지 도달할 수 있는지를 확인하기 때문이다 입력에서 주어지는 순위는 한방향 그래프라고 이해할 수 있다 따라서 graph[a][b] =1 (a>b인 경우) 저장해서 경로가 있음을 표시했다. n = int(input()) # node m = int(input()) graph = [[0] * (n+1) for _ in range(n+1)] for _ in range(m): a, b = map(int, input().split()) # a > b graph[a][b] = 1..
https://www.acmicpc.net/problem/2310 2310번: 어드벤처 게임 입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타 www.acmicpc.net 문제 유형으로는 dfs, bfs문제라고 나와있는데 나는 백트래킹 문제라고 생각한다. bfs로 먼저 접근을 했었는데, 방문처리가 중복이 되는 경우가 발생하는 문제점이 있었다. 또한 문제에서 제시한 조건으로 트롤을 만났을때 통행료를 확인한 후 이 방을 방문처리 할 지 말지가 정해진다. 통행료가 부족해서 통과할 수 없으면 재귀함수를 탈출시키고 통과할 수 있으면 연결된 다음 방 (next..
https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr import heapq INF = int(1e9) def dijkstra(n, start, graph): # end : a or b distance = [INF]*(n+1) distance[start] = 0 queue = [] heapq.heappush(queue, (0, start)) while queue: dist, now = heapq.heappop(queue) if dist < dista..
