Dogfootruler Kim

문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 및 소스코드 여기서 한가지 자칫 실수할 것이 7 6 100 400 300 100 500 101 400 답: 500 이 반례이다. 나같은 경우에는 테케만 보고 맨끝이 제일 긴 비디오라 생각하여서 시작을 배열의 끝인 400부터 start로 잡고 갔는데, 이러한 반례가 존재한다. 따라서 리스트의 최대값을 찾고, 그것을 start로 해주고, end는 리스트의 총합을 넣어준다. 또한, 블루레이의 최솟값..

문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 및 소스코드 import sys input = sys.stdin.readline n, m = map(int, input().split()) arr = list(int(input()) for _ in range(n)) arr.sort() start = 1 end = arr[n-1]-arr[0] res = 0 while(start

문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 및 소스코드 벨만포드 알고리즘으로 푸는 문제이다. 어려워 ... 다익스트라와의 차이점은 매 반복마다 모든 간선을 확인한다는 것 다익스트라는 방문하지 않는 노드 중에서 최단 거리가 가장 가까운 노드만을 방문 import sys input = sys.stdin.readline INF = int(1e9) n, m = map(int,..

문제 https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1

문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 및 소스코드 1의 개수가 하나도 없을 때 고려해주지 않으면 valueerror가 뜬다 ㅠㅠ ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ ㅠㅠㅠ... import sys input = sys.stdin.readline sys.setrecursionlimit(10000) from collections import deque n,m = map(int, input().split()) arr = [list(map(int, ..

문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 및 소스코드 dfs로 풀어주었다. 여기서 중요한 점이 삭제할 노드의 부모노드가 가진 자식노드가 삭제할 노드 밖에 없을 때다. 노드를 삭제하면 부모노드가 리프가 되므로 +1을 해줘야 하기 때문. 아래 그림을 보면 쉽게 이해할 수 있다. 이러한 케이스에서 올바른 출력을 하기 위해서, dfs가 끝난 후 만약 삭제할 노드의 부모노드가 가진 자식노드의 개수가 하나 뿐이라면 ans에 +1을 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 및 소스코드 자바랑 파이썬 같이 쓰려하니 넘 헷갈린다 ,, ㅠ 그치만 아직까진 파이썬이 조아 ..... bfs로 구현했다. 함수는 따로 만들지 않았다. 귀찮았다 .. deque에 시작점(1)과 시작카운트(0) 을 담아서 while 문을 돌렸다. q = ([1,0]) 이렇게 시작 ! 1번 노드와 3번, 2번 노드가 연결되어있다고 했을 때, q = ([3, 1]) q = ([3, 1], [2, 1]) 위와 같이 q에 appe..

문제 https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 풀이 및 소스코드 연속된 부분은 더할 수 없기때문에 dp[i] = max(dp[i-1], dp[i-2]+money[i]) 라는 점화식이 나온다. def solution(money): answer = 0 dp1 = [0 for _ in range(len(money))] dp2 = [0 for _ in range(len(money))] dp1[0] = money..