https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 난이도: 실버2 소요시간: 30분 다익스트라를 쓰면 풀리는 문제이다. 거리가 1로 고정인 점을 생각하여 다익스트라 알고리즘을 조금 수정 하면된다. import sys import heapq N,M,K,X = map(int,sys.stdin.readline().split()) INF=1e9 dist = [INF]*(N+1) g..
Problem Solving
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 난이도: 실버2 소요시간: 60분, 엣지케이스 관련 힌트 참고함 최대로 나올수 있는 값을 end로 정했다. 1~end를 이분탐색하여서 정답을 찾았다. import sys K,N = map(int,sys.stdin.readline().split()) end=0 cableList=[] for _ in range(K): temp=int(sys.stdin.readline())..
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 난이도: 실버2 소요시간: 답을 보았기에 재풀이 필요 입력값으로 (회의시작,끝나는시간) 들을 받는다. 이때 회의시작시간기준으로 정렬을 했더니 풀이가 쉽지 않았다. 끝나는시간을 기준으로 정렬을 하면 쉽게 풀이가 가능하다. 이때 끝나는시간이 같을경우에는 시작이 빠른 회의를 앞쪽으로 보내야 한다. 그래야지 시작시간=끝나는 시간 인 회의도 카운트가 가능하다. 먼저 시작시작 오름차순정렬 -> 끝나는시간 오름차순으로 두번 정렬하여도 되지만 나는 한번에 하는방법을 선택했다. 아래 처럼 하면 x[1]기준으로 오름차순 정렬하고 ..
https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 난이도: 실버4 풀이 시간: 40분.... 15분만에 풀었으나 엣지케이스를 발견을 하여.. 알고리즘을 새로 짬.. 아래는 나의 코드이다. 3으로 빼주면서 5의 배수가 될때마다 리스트에 추가하여 최솟값을 마지막에 출력한다. 문제를 보자마자 DP가 떠올랐다. DP[i-3]과 DP[i-5]를 비교하면 되겠다는 생각이 바로 떠올라 점화식이 쉽게 생각났지만 오늘은 그리디를 공부하기로 한 날이기에 그리디로 풀었다. i..
https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 풀이시간: 1시간이상 걸려서 힌트를 참고하여 품 난이도: 골드5 아래는 나의 코드이다. 처음 접근 법은 자두까 떨어지는 나무가 바뀔때를 기준으로 입력값을 끊어서 생각했다. 예를 들면 2 1 1 2 2 1 1 순으로 자두가 떨어지면 1 2 2 2 로 변환하여서 생각하였다. 이 방법대로 풀어보니 뒤로갈수록 허점들이 발견이 되었고 수정을 하여도 몇몇 케이스에서 제대로 작동을 하지 안았다. 이 접근법 때문에 시간..
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 난이도: 실버2 소요시간: 45분 아래는 나의 코드이다. nq 변수에 값을 잘못 저장하여 에러잡느라 시간을 예상치 못하게 많이 잡아 먹었다... import sys from collections import deque T = int(sys.stdin.readline()) move=[[1,0],[-1,0],[0,1],[0,-1]] def BFS(start): que= deque([start]) if visite..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 아래는 나의 코드이다. DFS,BFS를 복습하기에 좋은 문제이다. 상하좌우를 검색하는 유형이 아닌 그래프 유형이다. import sys from collections import deque N,M,V = map(int, sys.stdin.readline().split()) myMap = [] for i in range(M): temp= list(map(int,..
이 문제는 이것이 코딩테스트다 262페이지 문제이다. 최단 거리문제는 전부 똑같은 유형이다. 정답이 거의 동일하고 출력부분만 다른 경우가 많다. 이 문제는 입력의 값이 크기에 우선순위큐다익스트라 알고리즘을 이용하여야 한다. 다익스트라 구현 방식을 이해를 하여야 한다. 그리고 거리비용이 현재보다 커질 때는 가지치기(branch and bound)를 미리 해주어야 한다.는 것을 알아야 한다. https://yunzae.tistory.com/94 최단경로(다익스트라,플로이드워셜) 최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립 yunzae.tistory.com 아래는 나의..
