Coding Kitsune

문제링크 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이과정: dp를 처음접해서 사실 처음에는 그냥 큰 수(3->2->1)부터 나누고 빼고 하면 되는거 아닌가? 3으로 나누어 떨어지면 나누고 안되면 2로 나눠보고 안되면 1빼고 반복하면 되겠네 라고 생각했다가 혼났다... 동적 프로그래밍을 이용하는 문제이고, 처음 풀이를 보았을때, 한번에 이해가 되지 않았다. 핵심은 이 dp는 정확한 계산방법이 없으며 약간 브루트포스와 비슷한 방식으로 모든 경우에 대해 생각을 해보고 이것들의 최대값 또는 최솟값을 구한다. dp[i] = dp[i-1] + 1 2와 3으..

문제링크: https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이과정 : 덱이란 앞과 뒤 모두 삽입 삭제가 가능한 양방향 큐이다. 큐와 마찬가지로 핵심은 모든 연산이 시간복잡도 O(1)에서 끝나야한다.(O(n)은 시간초과..) 처음에는 데큐 없이 push_front를 짜려고 하니 고생하다가... 데큐를 쓰기로 결정..! 나머지는 풀이랄것 없이 저번에 했던 큐 구현과 거의 동일하다. #덱을 사용하고, 시간복잡도가 O(1)이어야함 i..

문제링크 : https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이과정: 몇일전 자료구조 수업을 다시들으면서 큐와 요세푸스 개념을 들었기 때문에, 쉽게 해결될 것이라 생각하였는데, 시간초과 때문에 생각보다 꽤나 고전했다. 처음에 풀었던 풀이다. #처음 시도(시간초과) def josephus(N, K): answer = [] current = 0 lst = [i for i in range(1, N+1)] while len(lst[current:]) != 1: if (current+1)%K == 0: answer.append(str(lst[..

문제링크 : https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이과정 : 이전문제였던 스택과 거의 동일한 방식으로, 결국 큐를 구현할 수 있느냐 묻는문제다. 자료구조 수업때 배웠던 대로 큐 클래스를 구현해서 풀까도 생각했지만, 그냥 남들처럼 포문안에 다 때려넣었다... ;ㅅ;... 다행히 원큐에 통과! 삽입하는건 스택과 동일한 방식이기 때문에 다른게 없을것이고, 디큐하는 부분이 포인트, 결국 큐 입장의 가장 앞을 가르키는 fro..

문제링크 : https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이과정 : 처음에 하나의 스택안에 입력문자들을 받고, 커서를 가르키는 인덱스를 추적하면서, 상황에 따라 포문을 돌려가며 문제를 풀어서 비교적 간단하게 문제를 풀었는데.. 역시 시간초과가 떴다...! #시간초과 import sys lst = list(sys.stdin.readline().split()) cur_idx = len(lst) testcase = int(input()) for ..

문제링크 : 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 풀이과정: 문제를 이해하는것이 정말 어려웠다... 스택에 1,2,3......순서로 계속해서 쌓아두고 차례로 뽑아쓰는 개념이다. 문제 처럼 4, 3, 6, 8 순서로 이 스택에서 뽑아쓰고 싶다면 스택을 먼저 만든다. 스타트가 4이기 때문에 [1, 2, 3, 4] 의 수열을 만들고, 내가 원하는 숫자 4를..

문제링크 : https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이과정: 처음에 스택 클래스를 구현해야하나 해서, 어떻게들 푸셨는지 블로그들을 방문해서 확인해보았다. 파이썬은 다행히 따로 클래스를 구현하지않고 리스트로들 푸셔서 같은 방식으로 풀었는데 시간초과..! 역시 백준은 input함수만 쓰면 높은확률로 시간초과가 뜬다. 궁금해서 input vs sys.stdin.readline을 알아보았다. 결론적으로 말하자면 input ..

문제링크 : https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 풀이과정: 문제읽고 20분동안은 한참 생각해야했다. 거리가 8정도 일때 까지 가정해보고 써내려가보았는데, 규칙을 찾지 못했고 답을 보고서야 끼워맞추기 식으로 규칙을 찾을 수 있었다...! 어떻게 생각하면 코테 준비한지 한달정도가 된 나에게는 조금 어려운 문제가 아니었나 생각한다. 이 규칙을 어떻게들 찾으셨는지 놀라운데,, 결론부터 말하자면 ..

문제링크 : https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이과정 : 하노이탑은 엄청 어릴때, 수학경시대회나 어려운문제집 같은 곳 보면 풀었던 기억이 있는데, 다시보니까 또 어려웠다... 재귀함수에 대해서 어느정도 알고있다 생각했는데도 알고리즘을 정확히 이해하는데 시간이 걸렸다. 우선 1번 2번 3번 기둥을 각각 start(시작점) by(경유) end(도착점)으로 정의하였으며 이는 각각의 상황에 따라 시작점이 경유점이 되기도, ..