흔적을 기록하는 노트

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 정답률이 무척 낮은 문제였는데, python3 정답률은 평균보다도 낮았고, 내가 그 정답률을 더 낮추는데에 기여했다!... pypy3로 풀란 말이 있었지만 python3로 풀고 싶었다.. 이진탐색 알고리즘으로 간단히 구현했지만 시간초과로 빠르게 광탈했고, 여러 코드를 참고해봤지만 도통 시간초과는 풀리지 않았다. sort도 없앴고, min과 max도 없앴고. ..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 점점 문제가 복잡해진다...! 헷갈려서 이번 문제부터 설계를 메모하기 시작했는데, 마침 설명하기도 난해한 문제라 그냥 메모로 대신한다. 글씨가 좀 흩날라가서.. (차마 패드도 교정해주지 못한 악필..) 다음부턴 더 열심히 써야겠다..!! 그리고 이젠 설계하는 습관을 더 들여야겠다. 코드가 복잡한 것 같아 시간이 오버될 줄 알았는데 통과됐다. 조건 범위가 그리 넓지 않아서 그런 듯 하다.. 그래도 나름..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 빙 돌아온 문제였다. 최종적인 답안은 짧은 편인데, 원초적인 코드는 굉장히 길었다. 에라 모르겠다 싶어 제출한 코드가 의외로 정답처리 됐고, 아주 깔끔한 답안은 분명 아닐 거라 생각하고 수정보완 해줬다. 그냥 넘어갈 수도 있었는데 굳이 코드를 처음부터 다시 짰고, 그걸 더 수정했다. 지금 생각해보면 잘한 일이었다. ..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 예기치 않은 곳에서 오류를 만난 문제다. 여느때처럼 K와 N을 받고, 랜선 길이들을 리스트에 넣고. 그 리스트를 정렬해 가장 긴 랜선 길이를 뽑아 최댓값으로 정해줬다. 이제부턴 그냥 이진탐색 구현! 중간값(mid) 지정 후 랜선 리스트를 돌며 자를 수 있는 랜선 길이들을 모두 카운팅 해줬다. 만약 이 개수가 N보다 크거나 같으면 우선 result에 저장. 구할 수 있는..

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 연산으로 계산해 빠르게 풀어야 하는 문제인가 싶었는데, 2초라는 넉넉한(?) 시간을 보곤 한 명씩 처리해가며 풀어도 되겠다 싶었다. 학습한 덱을 적용해보는 간단한 기본 문제였다. 오히려 출력을 어떻게 해줄지 고민을 더 많이 했다. 그냥 리스트를 통채로 출력하면 대괄호에 둘러싸여 나오는데. 화살 괄호..? 꺾인 괄호로 출력하기 위해선 리스트를 for문에 넣고 요소만 빼와야 했다. 이걸 한 번에 구현할 수 있는 멋진 방법이 없을까 생각해봤는데, 내겐 새로운 함수인 join을 사용해보기..

https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 10828-스택, 10856-큐, 이번엔 10866-덱 스택 기본 문제의 마지막인 듯 하다. 애초에 덱으로 문제를 풀어왔기 때문에 이전과 크게 다르지 않다. 명령 가짓수가 많아져 더 추가한 것 말곤 달라진 게 없다. 아래 글을 참고하면 좋겠다. 2022.01.24 - [[Python]BaekJoon.AC] - [Python]백준 BaekJoon.AC 10828 : 스택(deque,..

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 이전에 했던 10828-스택 변형문제다. 까다롭게 변형된 것도 아니라 기존 틀에 몇 가지만 더해주면 된다. 문제 이름은 '큐'지만... 덱을 이용했다. 파이썬에선 queue와 deque이 뚜렷하게 차별화된 기본 사용법을 가지진 않는 것 같다. 큐보다 덱이 더 기능이 많은 것 같기도 하고... 양방향 추가·추출이 가능한 deque과 그렇지 않은 queue 중 굳이 queue를 사용할..

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 경우의 수가 많기 때문에 switch문을 사용하면 좋겠지만 파이썬에선 그런 구문이 없다. 하지만 if문의 능력범주가 넓고 이용하기 쉽기 때문에 크게 문제되지 않는 것 같다. 우선 한 줄씩 입력받아 그 라인을 split해 리스트에 저장해주고, if문을 이용해 명령어에 따라 나눠지게 만들었다. 먄악 추가적인 정보가 필요한 명령어라면 아까 저장한 리스트 옆칸엔 반드시 정보가 들어있을 ..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 다양한 방법을 시도했던 문제다... 이건 틀리고 이건 시간초과고, 떠오르는 방법을 다 적용해봤는데 이렇다 할 해결방법이 없었다. 분명 하라는대로, 이진탐색으로 풀었는데... 리스트로도 해보고 딕셔너리도 사용해보고. 처음엔 딕셔너리도 이진탐색엔 어울리지 않는 것 같아 리스트로만 해보다, 다들 딕셔너리를 당연하듯 쓰길래. 그리고 이진탐색 아닌 방법으로도 해봐도 안되길..

https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 가장 최근에 넣은 스택 옆에 저장하고, 가장 최근에 넣은 스택을 꺼내오는 덱을 이용했다. 구현은 그리 어렵지 않아 이만 설명을 마친다. 코드로 이해하는 편이 빠를 것 같다. from collections import deque import sys K = int(input()) deq = deque() result = 0 for i in range(K): num =..