그리디 문제https://www.acmicpc.net/problem/2212문제 설명고속도로 위에 최대 K개의 집중국을 세워 N개의 센서에 도달해야 한다.이때, N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 한다.각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.접근 방식그리디우리는 최대 K개의 집중국을 세워 모든 N개의 센서에 도달하는 것이 목표이다.즉, 최대 K개의 집중국을 세워 n(n1,n1,..)-k(k1,k2,..)의 최솟값의 합을 구하는 것이 목표이다.여기서 N개의 센서와 K개의 집중국이 의미하는 바가 무엇인지 알아보자.N개의 센서 : 우리가 도달해야 하는 센서의 개수로, 각 센서는 원점으로부터의 정수 거리의 위치에 놓여 있다.K개의 집중국 : 세울 수 있는 집중국의 개수로,..

그리디 문제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 ..