본문 바로가기

Algorithm💻35

[Algorithm] DFS, BFS DFS (Depth-First-Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘을 말한다. 스택 자료 구조(혹은 재귀 함수)를 이용한다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없다면 최상단 노드를 꺼낸다. 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. DFS 동작 예시 [Step 0] 그래프 준비 (방문 기준 : 번호가 낮은 인접 노드부터) 시작 노드 : 1 [Step 1] 시작 노드인 '1'을 스택에 삽입하고 방문 처리한다. [Step 2] 스택의 최상단 노드인 '1'에 방문하지 않.. 2022. 11. 15.

[백준,Python] 1260번 - DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 깊이 우선 탐색(dfs)와 너비 우선 탐색(bfs)으로 실행 시킨 값을 출력하는 문제이다. 두가지의 차이점을 확실히 아는 것이 중요할 것 같다. 코드 import sys input = sys.stdin.readline n,m,v = map(int,input().split()) visited = [False]*(n+1) graph = [[] for _ in.. 2022. 11. 15.

[백준,Python] 9465번 - 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 해당 문제는 도저히 점화식이 떠오르지 않아 구글링을 했다. 위의 표를 예시로 들어보자. 좌측에서부터 해당 스티커의 위치에 최대값이 될 수 있는 경우를 생각하면 된다. 우선 해당 위치에서 좌,우,위,아래 숫자는 선택할 수 없다. 1번 인덱스에서는 왼쪽 대각선의 0번 인덱스의 숫자를 더할 수 있다. 2번 인덱스부터는 이 전까지 최댓값을 더한 숫자를 저장하고 있는 왼쪽 대각선의 숫자와 .. 2022. 11. 13.

[백준,Python] 9095번 - 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 d[4]를 구한다고 하자. 3을 만들 수 있는 경우의 수에서 +1을 한 것, 2를 만들 수 있는 경우의 수에서 +2를 한 것, 1을 만들 수 있는 경우의 수에서 +3을 한 것을 합치면된다. 즉, d[4] = d[3] + d[2] + d[1] 이라고 볼 수 있다. d[n] = d[n-3] + d[n-2] + d[n-1] 이라는 식이 나온다. 해당 그림은 정리를 깔끔하게 하셔서 참고를 했다. [Python] 백준 #9095 - 1, 2, 3 더하기 (tistory.com) 코드 d=[0]*11.. 2022. 11. 12.

[Algorithm] 다이나믹 프로그래밍 현재 코딩테스트 준비를 하는 과정에서 다이나믹 프로그래밍에 관련된 문제를 풀다가 한번 정리를 해보는 것이 좋다고 생각이 들었다. 이에, 다이나믹 프로그래밍(Dynamic Programming)기법이라고 하는 동적 계획법에 대해 정리해보고자 한다. Dynamic Programming, 동적 계획법 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 해결하고자 하는 문제들의 중복 여부를 확인해볼 것 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장함 탑다운(Top-Down) 방식 다이나믹 프로그래밍으로 해결할 수 .. 2022. 11. 11.

이전 1 2 3 4 ··· 7 다음

티스토리툴바