위상정렬 문제https://www.acmicpc.net/problem/2252💡 풀이코드 (성공)import sys from collections import deque V, E = map(int, sys.stdin.readline().split())graph = [[] for _ in range(V + 1)]degree = [0] * (V + 1)for i in range(E): v1, v2 = map(int, sys.stdin.readline().split()) graph[v1].append(v2) degree[v2] += 1def topological_sort(V, E, graph, degree): queue = deque() result = [] for i in ..

BFS, 시뮬레이션 문제https://www.acmicpc.net/problem/13460 이 문제를 풀며 모호했던 부분이 많았기 때문에 구현이 어려웠던 것 같다.내가 이 문제를 풀며 모호함을 느꼈던 부분에 대해 먼저 소개하고자 한다. 헷갈렸던 부분1. RB에 모두 왼쪽으로 기울이기를 수행했을 때 이동 후의 끝점이 .과 O일때의 차이 1) 예제입력2의 예시 - 이동 후의 끝점이 .(빈 칸)일때 " 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.  "따라서, RB에 모두 왼쪽으로 기울이기를 수행했을 때 RB는 동시에 같은 칸에 있을 수 없으므로 다음과 같은 형태로 이동한다.  7 7########...RB##.######.....######.##O....########출력5 7 7########..

투포인터, 누적합 문제https://www.acmicpc.net/problem/1806투포인터 알고리즘 1. 개념투 포인터 알고리즘(Two Pointer Algorithm)은 배열이나 리스트와 같은 선형 자료 구조에서 두 개의 포인터를 사용하여 문제를 해결하는 기법이다. 이 알고리즘은 주로 다음과 같은 문제를 해결하는 데 사용된다.부분 배열 또는 부분 수열에서 특정 조건을 만족하는 경우 찾기두 배열에서의 교집합 구하기정렬된 배열에서 특정 합을 가지는 쌍 찾기 투 포인터 알고리즘의 기본 아이디어는 다음과 같다.두 개의 포인터를 사용하여 배열의 시작 부분과 끝 부분, 또는 특정 지점에서 시작하여 원하는 조건을 만족할 때까지 이동한다.포인터를 이동시키면서 조건을 체크하고, 조건에 맞는 경우를 찾으면 결과를 갱..

DP, 누적합 문제https://www.acmicpc.net/problem/2560 접근 방식 문제를 단순화해서 생각해보자.우리가 구해야하는 값은 N일째 되는 날 살아있는 짚신벌레 수(를 1000으로 나눈 나머지)이다.그러면 dp에 무슨 값을 기록해야할까 ? -> for문을 N번 돌며 dp[i]에 i일에 살아있는 짚신벌레 수를 기록하자.참조해야 하는 배열 없이, 이전 dp 배열에 기록했던 짚신벌레 수를 활용하여 현재 dp 배열의 값(현재 i일째에 살아있는 짚신벌레 수)를 구할 수 있다.dp[i]는 i일째 되는 날에 살아있는 짚신벌레의 수💡 풀이코드 (성공)import sys a, b, d, N = map(int, sys.stdin.readline().split())def sol(a, b, d, N): ..

DP, 누적합 문제https://www.acmicpc.net/problem/2616 이 문제는 냅색 알고리즘의 변형으로도 볼 수 있을 것 같다.누적합을 저장해준 (1차원) 배열을 만들고, 해당 배열을 활용하여 소형 기관차 3대로 최대 운송할 수 있는 손님수를 구하는 문제이다. 초기 접근 방식객차의 수, 소형 기관차가 최대로 끌 수 있는 객차의 수, 소형 기관차의 갯수(3)에 대한 정보가 주어졌다.처음에 이 문제를 보고 DP로 풀어야겠다고 생각했다. 그러나 초기에는 r = 소형 기관차가 최대로 끌 수 있는 객차의 수, c = 객차의 수에 대한 DP 배열의 형태를 구상하였기에 문제가 생각보다 쉽게 풀리지 않았다.3대의 소형 기관차가 최대로 끌 수 있는 객차의 수는 서로 같다. 여기서 "최대"라는 말에 포커스..

그래프, BFS/DFS 문제https://www.acmicpc.net/problem/21736 💡 풀이코드 (성공 - DFS 1)import sys sys.setrecursionlimit(10 ** 9) r, c = map(int, sys.stdin.readline().split())graph = []start = []visited = [[False] * c for _ in range(r)]dy = [0, -1, 0, 1]dx = [1, 0, -1, 0]cnt = 0for i in range(r): l = list(sys.stdin.readline().strip()) for j in range(c): if l[j] == "I": start.append((i,..