정신차려 하프물범 정신차려 하프물범

문제 링크https://www.acmicpc.net/problem/11729할때마다 까먹는 하노이탑.. 제대로 이해를 못한거같아 밑에 블로그를 보면서 정리해봤다. [참고] https://mgyo.tistory.com/185문제점N -1개의 원반으로 두번째 막대로 옮겨야한다는 것은 알았음재귀로 이 문제를 어떻게 풀어낼지에 대해 막힘 풀이재귀란? 같은 형태의 보다 작은 입력을 지닌 자기 자신을 호출하는 것, 재귀적인 호출을 사용하는 함수를 “재귀함수”라고 한다.그렇다면 이 문제는 재귀의 여지가 있는가?hanoi(N): N개의 원판을 ~~~해서 다른 곳으로 옮기기hanoi(N-1): N-1개의 원반을 ~~~해서 다른 곳으로 옮기기이런 식으로 활용 가능하지 않을까?그럼 hanoi(N) 함수를 반복적으로 사용할 ..

문제 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 풀이 (2번~ n번) 모든 전구는 i번째를 눌렀을때 i-1번째의 전구 상태를 마지막으로 결정한다. i번째가 누를지 말지에 따라 i-1번째의 전구 상태가 정해지고 뒤로 가면 i-1번째 전구는 바뀌지 않는다. 그러므로 i번째의 전구를 누를지말지는 i-1번째의 상태와 목표 전구의 상태를 비교하며 결정한다. (1번 전구 설정하기) 그럼 초기값인 0번째의 전구를 누를지 말..

문제 링크 https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 풀이 처음엔 단순히 N(상자 개수)개의 누적합 테이블(dp)을 만들어, start, end, mid를 통해서 dp[mid]의 도토리 개수에 따라 mid를 파악하려 했다. [시간 초과 난 코드] import sys input = sys.stdin.readline N, K, D = map(int, inpu..

문제링크 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 풀이 - combinations로만 풀기엔 시간초과가 나는게 뻔해서 고민했다. 완전 탐색 문제인데 어떻게 다 돌지? - 질문게시판에 플로이드 워셜로 하면 금방 다그래서 봤더니 진짜 금방이다:) - 모든 지점 -> 모든 지점은 플로이드워셜, 최단 경로 알고리즘으로만 생각했는데 완전 탐색도 포함이니까 잊지말자! from itertools import combin..

문제https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치www.acmicpc.net 풀이시뮬레이션, 구현방향성 조건때문에 헷갈려서 시간이 너무 오래걸렸다 ㅜㅜㅜㅜ 시뮬레이션은 ㄹㅇ 독해가 중요한듯,,모여진 파이어볼의 방향이 모두 짝이거나 홀이면 -> [0, 2, 4, 6], 그렇지 않고 섞여있는 방향이면 -> [1, 3, 5, 7] 이다.import mathfrom copy import deepcopy# move# 일단 방향대로 속력만큼 움..

문제링크 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 분류: 트리순회 + 이진탐색 느낌? 몰라서 풀이를 참고했다 ㅜㅜ 노드 클래스를 만들어서 풀려 하니까 insert, find 등의 함수를 다 구현해야하나 싶었다. 참고 풀이를 설명하자면, 전위 순회로 받았기 때문에 처음 입력값인 50이 루트 노드 이다. 이진 트리이기 때문에 루트보다 큰 값은 오른쪽에 위치하게끔 인덱스를 설정해준다. 그 인덱스를 기준으로 왼쪽 서브트리를 돌..

문제 링크 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 풀이 풀이 설명 분류: 문자열 replace 를 썼더니 시간초과 replace 의 빅오: O(문자열의 길이 * (교체할 문자열의 길이 + 교체되는 문자열의 길이/교체할 문자열의 길이)) 그러므로 replace > slice > del 순서로 시간이 적게 걸린다는 것을 생각하자. 안될 경우 slice/del 로 바꿔보기 slice - O(L[a:b]) => O(b-a) de..

문제 링크 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 풀이 풀이 재귀함수를 이용해서, 지우려는 노드를 실제로 dict 형태를 가진 Tree에서 삭제시키는 것. 삭제 진행 자식 길이가 0이면 해당 노드 삭제 돌아와서 본인 삭제 삭제 과정 후에 자식이 0인 것을 센다. import sys input = sys.stdin.readline sys.setrecursionlimit(100000) N = int(input()) Tree = ..