교대최소제곱법

모든 재귀함수 문제는 DP로 해결할 수 있다 -> X 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 재귀함수의 장점 변수를 여럿 만들지 않기 때문에 헷갈리지 않는다 반복문에 비해 코드가 간결하다 재귀함수의 한계 → 연산 복잡성, 같은 연산을 반복해야한다 -> 시간복잡도가 커진다 또한 메모리 문제도 있다. 재귀함수를 사용하면 함수를 호출할 때 메모리에 적재되는 일련의 과정을 거쳐야 하기 때문에 *오버헤드(ovehead)가 발생할 수 있다! → 문맥 교환에 비용이 발생한다! 함수를 종료하지 않..

서울과학고는 산책하기 참 힘든 곳이다. https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 첫 번째 제출 def dfs(start): global cnt for next in graph[start]: if not visited[next]: if spot_ls[next-1] == 0: visited[next] = True dfs(next) visited[next] = False else: cnt += 1 N = int(input(..

문제 핵심 1. 시작점에서 고려하지 말고, 끝 점에서 고려하자! 시작점에서 고려할 경우 새로운 노선이 들어왔을 때 두 가지를 확인해야한다 새로운 노선의 시작이 범위를 벗어나는가? 새로운 노선의 끝이 범위를 벗어나는가? 하지만 새로운 노선의 끝을 기준으로 범위를 설정하면 범위의 시작부분만 확인하면 된다. 2. 왜 정렬을 했는데 우선순위 큐를 써야하는 문제인 것일까? 정렬의 기준이 끝을 기준으로 했기 때문이다. 범위를 벗어나는 노선을 제거할 때는 종료지점 기준이 아닌 시작지점 기준으로 작은 수부터 제거해야한다. 그러니 값이 들어올 때만 정렬을 해주는 것은 엄청난 시간 복잡도가 필요하다. 따라서 이를 힙으로 해결한다. -> 힙을 사용하는 이유 : 값이 들어올 때마다 정렬이 필요한 경우 or 두 가지 기준의 정..

1. heapq의 힙 푸쉬는 가장 작은 숫자가 가장 앞에 존재한다. -> 리스트명[0]은 가장 작은 숫자 -> 그래서 pop을 안하고 [0]으로 가장 작은 숫자를 엿볼 수 있다. 2. heappop은 기본적으로 가장 작은 원소를 출력한다. -> 최소힙 from heapq import heappop, heappush N = int(input()) min_heap = [] max_heap = [] ans_ls = [] for _ in range(N): num = int(input()) if len(min_heap) == len(max_heap): heappush(min_heap, (-num, num)) else: heappush(max_heap, (num, num)) if max_heap and min_he..

삼성 코테는 1솔 패스가 거의 오피셜이기 때문에 1번 문제만 노리는 전략을 세웠다. 1솔 하더라도 1번이 2번보다 어렵게 나오기 때문에 1번 1솔만 의미가 있다는 말을 들었는데 잘 모르겠다. 1번 문제 : 시뮬레이션(로봇대전) 2시간 반 정도 걸려서 공개테케 8개를 통과했는데 나머지 2개를 못 찾았다. 어짜피 1솔 목표이기 때문에 2번 문제는 구경만 하고 다시 테케 통과를 위해 검토했는데 못 찾음... 체계적으로 설계하지 못해서 예외를 놓친 듯 하다. 기본적인 설계는 하고 코드작성을 하긴 했지만 좀 더 구체적으로 설계할 필요가 있는 것 같다. 입출력, 실행루프 부분은 알아보기 쉽게 짜졌는데 함수 부분은 나중에 테케 찾으면서 손대기가 힘들더라 삼성은 무조건 시뮬레이션 문제 하나 나오니까 시뮬 문제를 많이 ..

이진탐색 def bisect(n): left = 0 right = N - 1 while True: mid = int((right + left) / 2) if n == nums[mid]: return True if right

하노이탑 문제의 답은 2**N - 1 이다. 라고 외웠었는데 왜 그럴까? 하노이탑의 기본 원리는 N개를 2번 기둥으로 옮기고 가장 큰 원판을 3번 기둥으로 옮긴 뒤 다시 N개를 3번 기둥으로 옮기는 방식이다. 즉, hanoi(n-1) + 1 + hanoi(n-1) 그럼 이게 왜 2**N - 1 일까? 만약 3번의 재귀를 돌았을 때를 계산해보면 다음과 같다. 2(2(2(x + 1) + 1) + 1 = 8x + 4 + 2 + 1 결국 1 + 2 + 4 + 8 + ... = 2**N - 1 인 것이다. 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 ..

최초 코드 from collections import deque def findCheese(): ls = [] for row in range(N): for col in range(M): if graph[row][col] == 1: ls.append((row, col)) if graph[row][col] == -1: graph[row][col] = 0 return ls def bfs(): q = deque() q.append((0, 0)) while q: r, c = q.popleft() for i in range(4): nr = r + dr[i] nc = c + dc[i] if nr = N or nc >= M: continue if graph[nr][nc] == 0:..