그리디 문제https://www.acmicpc.net/problem/13164초기 접근 방식1. 이진탐색이 문제를 처음에 그리디로 접근하고자 하였으나, 생각보다 잘 풀리지 않아 그 다음 방식으로 이진 탐색을 떠올렸다. 백준에 있는 공유기 설치 문제와 유사하다고 생각하여 이 문제 또한 이진탐색으로 접근하여 문제를 풀어보았다.https://www.acmicpc.net/problem/2110 2. 잘못된 이유이진 탐색에서 mid의 의미가 명확하지 않다. 공유기 설치 문제 : mid = 공유기 사이의 최대 간격 -> 이를 바로 답에 활용할 수 있었음.행복 유치원 문제 : mid = 조를 S개 만큼 나누면서, 각 조의 첫번째 원생 사이의 간격이 최소가 되도록 하는 수 -> 문제에서 요구하는 바와 일치하지 않음.이..

MST 문제https://www.acmicpc.net/problem/1647접근 방식문제 분석마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.-> N개의 노드와 M개의 간선을 가지는 양방향의 가중치 그래프일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다.-> MST (1. 불필요한 간선 제거 2. 최소 신장 ..

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을 활용하여 최소 신장이 되도록 노드를 방문하는 식..