이숭간 공부기록

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제유형: BFS 문제풀이 answer배열 = 해당노드를 몇초에 처음 방문하게 되는지 저장하기 위한 배열 + 방문여부또한 체크할수있다. 큐에서 노드하나 빼서 해당노드를 기준으로 -1, +1, 2배를 해준다. 결과로 나온 3개의 노드를 순회하며 아직 방문전이고 ((이미 방문한 노드일경우 중복해서 큐에 넣을필요가 없기때문)) n이아니면 (만약 어떤 이동을 수행한 결과가n이면 결국 자기자신..

www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net 문제유형 : 스택, 리스트, 구현 문제풀이 : 커서의 위치를 0으로 두고 앞뒤로 움직일때마다 커서도 움직이는 형태로 진행하면 구현은 되나 시간복잡도가 높아져서 시간초과가난다. 처음에나도 이런 방식으로 코딩하고 구현은 됬는데 시간초과가 나서 실패함 사실 조금만 생각해봐도 테스트의 길이가 최대 1,000,000이므로 커서위치를 구해서 커서위치에서 지우거나 삽입할때 시간이 오래걸리게된다 . (pop(커서위치)..

www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 문제유형 : 정렬 문제풀이 : sort/sorted함수에서 lamda를 이용해서 정렬조건key로 넘겨주기!!! > list = [[0,1], [[3, 4], [1, 1], [1, -1], [2, 2], [3, 3]] 처럼 2차원배열이거나, list안의 원소가 튜플같은 경우의 정렬조건 key = lamda x : x[0] // 내부원소중 첫번째 값을 기준으로 ..

www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제유형 : 큐 문제풀이 : 자료구조 '큐'를 활용한 문제로 난이도는 쉬웠다. 처음에 포문으로 하다가 또 조건문써서 (한장남을때까지) break하는것보다 while문이 더깔끔한것 같아서 한번 수정함! 정답코드 : import sys input = sys.stdin.readline from collections import deque n = int(input()) card_list = deque([i for i ..

다이나믹프로그래밍 : 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과의 재사용 --> 한번 계산해서 해결한 문제는 다시 계산하지 않도록 한다. 일반적으로 두가지 방식 ( 탑다운, 보텀업)으로 구성된다. 언제 DP로 문제를 풀 수 있는가?? 1. 최적 부분 구조 : 특정 번째까지의 최적의해는 앞의 최적의해를 이용해서 계산되는경우 ex) i번째까지의 최적의해는 i-1, i-2번째까지의 최적의해를 이용하는 경우 2. 중복되는 부분문제 점화식으로 표현되는 식은 재귀함수를 통해 구현할 수 있다. but 시간복잡도가 큼 메모이제이션을 사용하는 탑다운 방법은 구현시 재귀함수를 이용한다. 즉, 큰 문제를 해결하기위해서 작은문제들을 재귀적으로 호출하여 작은문제가 모두 해결되었을때 ..

www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제유형 : 수학, DP 문제풀이 : 정답코드 : 1. 내가푼코드 (DP 로품, 근데 걍 빨리 풀고싶어서 좀 안좋게품 호호 _ 메모리낭뷔, 그래도 편법은 아니지않나? ) import sys input = sys.stdin.readline n = int(input()) dp = [-1] * (n+8) dp[2]=1 dp[4]=2 dp[5]=1 dp[6]=3 dp[7]=2 dp[8]=4 for i in range(9, n+1): dp[i] = min(dp[i-2], dp[i-5])+1 print(dp[n]) 2. 다른분 코드 ( DP..