흔적을 기록하는 노트

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문자 하나 잘못 입력해서 삽 좀 펐다... 입력 리스트 크기를 num[N][N]으로 설정해서, 메모리를 아무리 줄여도 메모리 초과가 발생했다ㅋㅋㅋㅋ;; 분명 num[N][3]으로 작성했던거 같은데...^^ max와 min을 따로 분리해 값을 구했다. 각 리스트(maxS, minS)에 그 칸에 해당하는 가장 큰 값 또는 가장 작은 값을 저장하는 방식이다. 입력 리스트를 한 칸씩 방문하며 그 칸이 왼쪽에 있다면 오..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net set을 제대로 몰라 한참 헤맸다. 지금까진 중복 제거하는 목적으로만 사용해서... set이 집합의 의미를 가지고 있는지 모르고 있었다. 고로 set은 합집합, 교집합, 차집합을 능숙히 해낼 수 있는 아이였던 것이다..! 이런 기능도 모르고 리스트나 딕셔너리로 삽을 펐으니.. a = set([1, 2, 3]) b = set([3, 4, 5]) print(a|b) 출력:{1, 2, 3, 4, 5}..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 자체는 단순한데 고민을 많이 했다. 함수나 더 복잡한 연산을 요하는 줄 알았는데, 통과한 코드를 보면 썩 그렇지도 않았다. 2와 5가 핵심이란 사실은 쉽게 눈치챌 수 있었다. 0이란 숫자는 2와 5를 곱해서만 만들어지니까. 문제는 이걸 어떻게 구워 삶느냐인데, 1부터 N까지 루프를 돌며 각 숫자에 2와 5가 몇 번 곱해져있는지 구하고 싶었다. 그러기 위해선 그 숫자를 2와 5로 나눠줘야 했고, while문과 if문을 통해 해당 수(2 or 5)로 나누어 떨어지는지 확인한 후 c..

. . . 이하생략 이번 문제는 직접 들어가 확인하도록 하자... https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 포켓몬 도감에 대한 문제이니 딕셔너리를 사용하기로 했다!(?) 도감, 사전, 비슷한거 아니겠어? 지금 확인해보니 해시를 사용한 집합과 맵...을 참고하라고 적혀있다..ㅎ 시간과 메모리 모두 무난하게 통과됐으니 그냥 넘어가기로 했다. 다솜이의 결정이다. 딕셔너리에 저장을 해주는데, 두 딕셔너리에 저장을 해..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net add 조건을 보고 set으로 풀어야겠단 생각이 들었다. 일일이 확인해주는 것보다 애초에 중복을 허용하지 않은 set을 선택했고, 문제 자체에서도 set을 요구하고 있음을 느꼈다. 해야 할 연산의 수가 정말 많았고 시간이 넉넉하지 않단 생각이 들어 시간단축을 신경썼다. 첫번째 if문으로 리스트 길이를 확인해준 것도 같은 이유다. 조금이라도 줄여보고자 if문을 넣었는데, 이게 이득이었는진 확인하지 않았다.. 여느 스택 문제처럼 set..

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을 사용해보기..