세흐세흐의 빠샤로그

1. 문제 링크https://www.acmicpc.net/problem/2666소요 시간 : 1시간시도 횟수 : 1 2. 문제 설명난이도 : G5사용 알고리즘 : DP벽장을 최소로 움직이는 횟수를 구하는 문제 3. 풀이 방식DP문제를 풀어보고 싶어서 문제를 골랐는데 처음엔 greedy 느낌도 나서 당황했다.공책에 끄적여보며 n=7, 문(2,6) 호출 순서 (4,3,1,6) 이렇게 해보니(왼쪽 오른쪽 거리가 같게) greedy가 아니라는걸 알 수 있었다.근데 이 문제, 내가 알던 기존의 DP와는 뭔가 달랐다.BFS에서 큐에 다음 데이터를 넣거나 DFS에서 재귀적으로 호출하듯이 이 문제 또한 다음 단계마다 2가지 경우의 수를 따져야 하는 느낌말하고 보니 이진 트리 느낌도 난다.이게 왜 DP일까, 이런 것도 ..

삼성전자 하계 알고리즘 특강을 신청했고, 6/28 ~ 7/2까지 사전 문제 풀이가 있다.그간 알고리즘을 열심히 하지 않았기에, 코테 단골 알고리즘들을 한 번씩 풀어보면서 나름의 준비를(?) 하려고 한다.오늘 풀어본 문제는 DP 관련 문제 ! 1. 문제 링크https://www.acmicpc.net/problem/2302소요 시간 : 34분시도 횟수 : 3 2. 문제 설명난이도 : G5사용 알고리즘 : DP(피보나치 수열)극장에는 한 줄의 좌석이 있고 사람들은 자기 입장권 번호와 양 옆 좌석 중 한 곳에 앉을 수 있다.VIP 회원에게는 고정 좌석이 있다고 할 때 사람들이 앉을 수 있는 방법의 가짓수를 구하는 문제 3. 풀이 방식처음엔 피보나치 수열인 줄 몰랐다.우선 중간중간 고정된 자리가 있다고 하니, ..