BFS 문제https://www.acmicpc.net/problem/9019시간 초과1. 문자열 변환 및 조작 연산은 느리다.문자열 변환문자열 변환(정수 -> 문자열 -> 정수)이 빈번하게 발생하면 누적된 비용이 상당히 커질 수 있다.문자열 슬라이싱슬라이싱 연산은 새로운 문자열을 생성하는 작업이므로, 메모리 할당 및 복사가 발생하며 매우 느린 작업이다.문자열 슬라이싱의 시간 복잡도는 O(k)로 비용이 크다. 이 때, k는 슬라이스된 문자열의 길이이다. 문자열 코드 (시간 초과 + 오답)while queue: val, dslr = queue.popleft() if val not in visited: visited.add(val) queue.append(((2 * val)..

DP 문제https://www.acmicpc.net/problem/17404문제 요약1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.💡 풀이 코드 (실패 - 마지막 행을 0번째 행으로 옮겨 겹치지 않게 하는 코드)'''51 10 1001 10 1001 10 1001 10 1001 10 100출략 : 32정답 :122'''# 마지막 행을 0번째 행으로 옮겨 겹치지 않도록 하자.import sys n = int(sys.stdin.readline())graph = [[0] * 3 for _ in range(n + 1)]dp = [[0] * 3 for _ ..

DP 문제https://www.acmicpc.net/problem/1149 💡 풀이 코드 (성공)import sys n = int(sys.stdin.readline())graph = [[0] * 3 for _ in range(n + 1)]dp = [[0] * 3 for _ in range(n + 1)]for i in range(1, n + 1): graph[i][0], graph[i][1], graph[i][2] = map(int, sys.stdin.readline().split()) if i == 1: dp[i][0],dp[i][1],dp[i][2] = graph[i][0],graph[i][1],graph[i][2]def sol(n, graph): for i in ..

MST / BFS + 이진탐색 문제https://www.acmicpc.net/problem/1939최소 신장 트리(MST)란?개념connected, weighted, undirected(양방향 가중 그래프)에서 정의되며, 신장 트리 중에서 가중치의 합이 최소가 되는 신장 트리이다.즉, 그래프에서 모든 정점을 포함하면서, 간선들의 가중치 합이 최소가 되는 트리를 의미한다. 최소 신장 트리 (가중치 합 : 8) 구현 방식MST를 구현하기 위해선 두개의 그리디 알고리즘을 사용할 수 있다. 1) Prim's Algorithm다엑스트라와 비슷한 방식이다.Dijkstra는 최단 경로를 찾는 알고리즘Prim은 최소 신장 트리를 찾는 알고리즘 (MST)자료구조 heap을 활용하여 최소 신장이 되도록 노드를 방문하는 식..

누적합, 수학 문제https://www.acmicpc.net/problem/10986접근 방식이 문제는 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수(부분구간의 개수)를 구하는 것이다.부분구간의 개수를 구해야 하므로 투포인터 알고리즘을 잠깐 떠올렸으나 주어진 데이터의 앞뒤 연관성이 없기 때문에 다른 방법을 고안해냈다. 투포인터 알고리즘을 쓸 수 없는 이유1) 투포인터 알고리즘의 일반적인 사용 사례투포인터 알고리즘은 주로 다음과 같은 조건을 만족하는 경우에 사용된다.정렬된 배열: 배열이 정렬된 상태에서 특정 합을 찾는 문제.특정 조건을 만족하는 구간: 예를 들어, 구간의 길이 또는 합이 특정 조건을 만족하는 경우.단일 스캔: 한 번의 배열 스캔으로 문제를 해결할 수 있는 경우.2) 투포인터 ..

이분 탐색 문제https://www.acmicpc.net/problem/2512💡 풀이 코드 (성공)import sys n = int(sys.stdin.readline())arr = list(map(int, sys.stdin.readline().split()))amounts = int(sys.stdin.readline())def binary_search(n, arr, amounts): start = 1 end = max(arr) answer = 0 while start