본문 바로가기

알고리즘/백준

[12847] 꿀 아르바이트(python) 1. 문제 https://www.acmicpc.net/problem/12847 12847번: 꿀 아르바이트 월세를 내기 바로 전 날 까지 인 n (0 < n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다. 그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000) www.acmicpc.net 2. 구현 과정 - 시간 제약이 1초이므로, O(N^2)만 되어도 안된다. N의 범위가 10만이므로, 최대 NlogN으로 풀어야 한다. - 누적합 함수인 accumulate를 사용해서 dp형식으로 푸는 방법과 투 포인터를 사용하는 방식 두 가지 방식으로 풀 수 있다. 개인적으로 투 포인터 문제는 익숙치 않아서, 후자 푸는 연습을 .. 더보기
[4485] 녹색 옷 입은 애가 젤다지?(python) 1. 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 2. 풀이 과정 - (0,0) 에서 (N-1,N-1)까지 갈 때 최소 루피(비용)을 출력하는 문제 - 처음엔 다익스트라로 풀려 했는데, BFS로 풀게 되었다. - 다익스트라는 "간선의 길이"가 중요한 문제, 즉 A번 -> C번 노드로 가는데 걸리는 "간선"의 비용이 어느정도인지가 주어지면 푸는 문제인데 해당 문제는 간선의 비용이 아니라 "특정 노드"에 도착했을 때 무조.. 더보기
[2110] 공유기 설치(python) 1. 문제 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 2. 구현 과정 - 읽을 수록 헷갈려서 문제를 이해하는데 오래걸렸다. 인접한 공유기의 최대거리? 가 어떤 의미인지를 빨리 이해하는 게 중요한 것 같다. - 맨 처음 완전 탐색으로 전체 N개 중 C개를 조합으로 구한 후, 가장 먼 거리를 구하려 했는데, 시간 초과가 난다. -> 파이썬 기준 2초 : 약 4000만 연산. nC2만 해도 2.. 더보기
[18111] 마인크래프트(python) 1. 문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 2. 구현 과정 - 완전 탐색으로 처음 풀었더니, 시간 초과가 났다. 500*500*256이 파이썬에선 1초가 넘어가는 걸 처음 알았다.. C++만 풀어왔던 나에겐 다소 충격(저 크기가 초과가 난다고?)이었고, 앞으로는 주의해서 풀어야 겠다. - 완전 탐색에 실패해서 그 다음 이분 탐색으로도 고민을 해 보았지만, 답을 구하려는게 최소-최대 높이가 아닌 최소 소요시간 이라는 점에서 정확.. 더보기
[1654] 랜선 자르기(python) 1. 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 2. 접근 방법 * 문제 이해 - 길이가 다른 k개의 랜선을 잘라서, N개 이상의 같은 길이 랜선들로 만들 때 (자르고 남는 대상은 버림) 만들 수 있는 최대 길이 * 접근 순서 1) 최대 길이 찾기(최적의 길이 찾기) : 최적 해를 구하는 것이므로 탐색(?)의 느낌이 남... 탐색에서 가장 대표적인 예시는 이분 탐색! 2) 탐색 시작 방향 구하기 : 가장 .. 더보기
[9012]괄호 1. 문제 www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 2. 접근 방법 1)스택을 이용해서 '('이면 스택에 넣고 ')'이면 스택에서 뺀다. 만약 '('이 나와서 빼려했는데 이미 스택이 비어있거나, 모든 괄호를 다 봤는데 아직 스택이 비어있지 않으면(닫히지 않은 괄호들이 있음) 올바르지 않은 문자열이다. 3. 실수했던 부분 & 처음 알았던 부분 1)stack에서 pop할때만 생각하지 말고, for문을 나왔을 때 스택에 값이 .. 더보기
[2805]나무자르기(C++) 1. 문제 www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 www.acmicpc.net 2. 접근 방법 1) 톱의 높이로 가능한 범위는 '~ 나무의 가장 높은 높이' 이다. 2) 톱의 높이를 정했을 때, 높이를 구하기 위해서는 log(N)만큼이 필요하다.(모든 나무들들을 다 베어서 합을 구해야 하므로), 따라서 모든 나무들의 높이에 맞게 나무를 잘라본다면 log(N^2)만큼 걸리므로 시간초과가 걸린다. 3) 이처럼 나무의 개수도 많고, 값도 크면 .. 더보기
[11048] 이동하기(C++/DP) 1. 문제 www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 2. 접근 방법 1) 이동방향이 (r+1, c), (r, c+1), (r+1, c+1) 이므로 사이클은 생기지 않는다. (1,1)->(N,M)까지 갈 수 있는 경우의 수를 구하려고 했다. 2) candy[i][j]가 (i,j)번째 도착했을 때 얻을 수 있는 최대 사탕 개수라고 할 때, candy[i][j]는 미로의 (i,j)번째 방에 놓인 사탕의 수 + (i,j)에 오기 직전까지 가장 .. 더보기

티스토리툴바