![]()
문제 https://www.acmicpc.net/problem/16435 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net Algorithm 스네이크버드의 길이보다 작거나 낮은 곳에 있는 과일이 있다면 그 과일을 fruits에 추가하고 스네이크버드의 길이를 1만큼 늘린다. 이 과정을 모든 과일의 높이가 스네이크버드의 길이보다 높은 곳에 위치할 때까지 반복한다. Code import sys input = sys.stdin.readline N, L = map(int..
https://www.acmicpc.net/problem/10865 10865번: 친구 친구 첫째 줄에 도현이네 반 학생의 수 N(1 ≤ N ≤ 100,000), M(0 ≤ M ≤ 1,000,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 나타내는 A B가 한 줄에 하나씩 주어진다. A B가 입력으로 주어진 경우 www.acmicpc.net 문제분석 친구 관계가 주어진다. 예를 들어 1번과 2번이 친구면 1 2가 주어진다. 입력으로 자기자신과 친구인 경우(ex 1 1)와 전에 나온 친구관계는 나오지 않는다(ex 1 2이 나온경우 2 1은 입력으로 주어지지 않음). 1번 사람부터 N번 사람까지 친구가 몇명 있는지 출력한다. 문제풀이 처음에는 친구관계를 나타내는 표를 생각해서 2차원 배열을 생각..
문제 분석 해당 문제를 가장 쉽게 풀려면 모든 경우를 다 확인해 보는 방법이다. 해당 알고리즘의 시간복잡도는 O(N^3)이므로(L 움직임 O(N), R 움직임 O(N), 중복 체크 O(N)) 시간을 초과하게 되어 최적화가 필요하다. 최적화 방법으로는 투포인터와 Count 기록 방법을 활용하겠다. 투포인터를 통해 Left와 Right를 움직이는 시간복잡도를 O(N)으로 줄이고 방문을 기록하여, 중복의 유무를 일일히 체크하는 것이 아닌 배열을 통해 한번에 알 수 있으므로 O(1) 만큼 걸린다. 따라서 이 방법대로 풀이하면 시간복잡도는 O(N)안에 문제를 해결할 수 있어 해당 방법으로 문제를 풀었다. 주의할 점은 Scanner를 사용하면 메모리가 초과된다는 점이다. BufferReader에 비해 시간이 오래걸..
![]()
2525번: 오븐 시계 첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.) www.acmicpc.net 문제코드
https://www.acmicpc.net/problem/23354 23354번: 군탈체포조 군탈 체포조(Deserter Pursuit)란 탈영병을 추적/체포하는 군인들을 말하며, 줄여서 DP 라고도 한다. 어느 날 군탈 체포조인 호열이에게 활동비와 지도를 주고 탈영병들을 모두 잡아 부대에 복귀하라 www.acmicpc.net 문제 분석 난이도 골드3 분류 다익스트라, 브루트포스 들어가기 전에 제 1회 KAUPC 출제 문제 문제 군탈 체포조(Deserter Pursuit)란 탈영병을 추적/체포하는 군인들을 말하며, 줄여서 DP 라고도 한다. 어느 날 군탈 체포조인 호열이에게 활동비와 지도를 주고 탈영병들을 모두 잡아 부대에 복귀하라는 명령이 주어졌는데, 돈을 아껴 봉지라면을 사 먹고 싶은 호열이는 활동비..
![]()
https://www.acmicpc.net/problem/3029 3029번: 경고 첫째 줄에 현재 시간이 hh:mm:ss 형식으로 주어진다. (시, 분, 초) hh는 0보다 크거나 같고, 23보다 작거나 같으며, 분과 초는 0보다 크거나 같고, 59보다 작거나 같다. 둘째 줄에는 나트륨을 던질 시간 www.acmicpc.net 문제 문제풀이
문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net Algorithm 다익스트라 문제이다. g와 h의 교차로(gh)를 지난 경로는 최단경로여야 하므로, (출발점에서 목적지에 가는 최단경로의 길이) = (출발점에서 gh를 지나 목적지에 가는 최단경로의 길이) 이어야한다. gh를 지나는 경로의 경우는 다음과같다. (출발점) → g → h → (목적지) (출발점) → h → g → (목적지) 즉, 출발점에서 목적지에 가는 최단경로의 길이..
문제 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 요약 N개의 정수로 된 수열에서 부분 수열을 뽑아낸 뒤, 부분 수열의 원소를 모두 더한 값이 입력값과 같은 경우의 수를 구하는 문제 문제 풀이 algorithm 헤더에 있는 prev_permutation() 함수를 사용했다. 이 함수를 사용한 이유는 다음과 같다. 중복 없이 N개의 정수로 된 수열을 조합하기 위해서 부분 수열의 원소 개수를 (1 ~ N)개까지 두고 조합하기 위해 먼저 N개의 정수로 된 수열을 벡터에 ..
![]()
15657번: N과 M (8) (acmicpc.net) 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 소스코드 문제풀이 자연수의 수 n과 n개의 자연수 중 고르게 될 자연수의 수 m을 입력 받음 n개의 자연수를 리스트로 입력 받음 고른 수열은 비내림차순이어야 하므로 리스트를 오름차순으로 정렬 자연수를 하나씩 append 또는 pop 할 것이므로 정답이 될 수열을 가지고 있을 빈 배열 생성 조건을 만족하는 수열을 생성해줄 fun() 함수 입력 받은 자연수 리스트 내에서 반복 정답인 수열을 가지고 있을 ..
다익스트라를 사용해 푸는 문제 평범한 골드 5 문제라고 생각했다가 시간 초과 2번 맞고 다익스트라를 잘못 이해하고 있었단 걸 알았다. 시간 초과의 원인 https://www.acmicpc.net/board/view/34516 7번 항목을 고려하지 않고 코드를 작성했기 때문에 시간 초과를 받았다. 평소에는 저 부분을 고려하지 않고 풀어도 잘 통과했다. 하지만, 정점이 10만개가 되니, 불필요하게 탐색되는 정점의 수가 누적돼 시간 초과로 이어졌다. 어떻게 해결했나? 매우 간단하다. 기존 코드에 2줄만 추가하면 됐다. 문제의 코드 while q: hereC, here = heapq.heappop(q) for there, thereC in graph[here]: cost = thereC + hereC if di..
![]()
https://www.acmicpc.net/problem/16955 16955번: 오목, 이길 수 있을까? 구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 www.acmicpc.net 문제 코드 문제 풀이 함수를 사용하여 1) 좌측 위 + 우측 아래, 2) 가운데 위 + 가운데 아래, 3) 우측 위 + 좌측 아래, 4) 좌 + 우 의 좌표를 비교함. 반복문을 실행, x,y = 0,0 부터 x,y = 10,10 까지 '.' 인 좌표를 찾아서 그 좌표를 'X' 로 바꿔주고, 그 좌표를 포함하여 연속된 'X' 5개가 완성되는지 확인함. 한 좌표에서 모든 함수를 돌았..
문제 씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다. 애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다. 입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다. 또한 출력할 때에 알파벳 순서로 출력해야 한다. 입력 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으..
