목록알고리즘/백준 (56)
이숭간 공부기록
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 ..
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..
www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제유형 : DP 문제풀이 : 최적부분구조와 중복되는 부분문제를 만족하므로 DP(다이나믹 프로그래밍)으로 풀어야하는 문제이다. 현재의 최적의 해 = 2로 나누었을때 최적의해, 3으로 나누었을때 최적의해 중 작은값 + 1 ( 물론 나누어 떨어질때만 나눌수있음) 정답코드: import sys input = sys.stdin.readline n = int(input()) dp = [1] * (n+1) # 숫자랑 인덱스 일치시키기 위해서 0은 안쓰는걸로 if n==1: # 1이면 0이므로 출력하고 종료 print(0) exit() ..