철학하는 개발자

있는 것은 있고, 없는 것은 없다.

DFS 6

[Code Tree] 정수 사각형 최장 증가 수열 [Python]

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-lis-on-the-integer-grid/description 정수 사각형 최장 증가 수열 설명 | 코드트리정수 사각형 최장 증가 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약N * N 행렬의 임의의 위치에서 값이 커지도록 상하좌우로 이동할 때, 가능한 최대 이동 횟수를 구하자.아이디어임의의 시작점(i, j)에서 DFS를 통해 구한 최대 이동 횟수는, 다른 시작점에서의 탐색 과정에서도 재사용될 수 있다.즉 부분 경로의 결과가 전체 탐색에서 활용된다.점화식은 다음을 나타낸다.dp..

PS/Code Tree 2025.06.27

[Programmers 알고리즘 고득점 Kit] 여행 경로[Python]

문제https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  풀이항공권의 정보가 주어졌을 때, 모든 공항을 전부 방문할 수 있는 경우를 찾고 들른 공항의 순서를 출력하는 문제다.정답이 여러개 존재하는 경우 공항의 순서를 사전순으로 출력해야 한다.일단, 입력받은 항공권의 정보에 대해 다음과 같이 그래프를 생성하고, 역순으로 정렬해줬다.from collections import defaultdictdef solution(tickets): graph = defaultdict(list) for ..

PS 2025.02.28

[백준 01405] 미친 로봇 [Python]

문제https://www.acmicpc.net/problem/1405 풀이로봇이 확률에 따라 상하좌우로 움직인다고 한다.이동 가능한 모든 경로에 대해, 방문하지 않은 곳을 방문하는 비율을 구하는 문제로 재해석할 수 있다.주어진 상하좌우로 움직이는 확률을 방향 좌표와 함께 묶어주자.문제에서 주어진 N은 14이기 때문에 -14 ~ 14를 고려해 보드의 크기는 29면 충분하다.if __name__ == '__main__': visited = [[False] * 29 for _ in range(29)] # Input N, *D = map(int, input().split()) D = [(*point, d * 0.01) for point, d in zip([(0, 1), (0, -1)..

[백준 03584] 가장 가까운 공통 조상 [Java]

문제https://www.acmicpc.net/problem/3584풀이주어지는 트리에 대해 두 정점의 공통 조상을 찾는 문제다.이미 부모-자식에 대한 정보가 주어지므로, 입력과 동시에 parent를 바로 구성할 수 있다. 공통 조상을 구해야하는 두 정점 중 한 정점으로부터 루트노드까지 방문해주고,다른 정점도 동일하게 방문하지 않은 부모 노드를 따라 방문하면 된다.이미 방문한 적 있는 부모노드는 공통 조상 노드이므로 탐색을 중단하고 반환해주면 된다.소스코드보기

[백준 01520] 내리막 길 [Java]

문제https://www.acmicpc.net/problem/1520풀이최대 500 X 500 크기의 보드에 대해 상하좌우 움직이면서 이전 위치보다 숫자가 작은 방향으로만 움직여 왼쪽 위에서 오른쪽 아래로 도착하는 경우의 수를 구하는 문제다.단순히 그래프 탐색으로 모든 경우의 수를 탐색하면 시간초과가 발생한다.중복 방문을 하지 않으면서도, 모든 경우의 수를 계산해야 한다.DP[i][j] = (i, j)에서 도착지 (M - 1, N - 1)까지 이동하는 경우의 수우선 입력을 받자.모든 지점이 도착지에 도달한다는 보장이 없으므로, dp는 -1로 초기화하자.dfs를 하며 만약 도착지에 도달했다면 1을. 이미 방문한 곳이라면 dp[x][y]를 반환해주자.그게 아니라면 새로운 탐색을 시작해야 하므로 dp[x][y..

[백준 24479] 알고리즘 수업 - 깊이 우선 탐색 1 [Java]

문제오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  visited[R] 입력첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ ..