빠르고 꾸준하게

자료구조 & 알고리즘/백준(Baekjoon)

[백준]4811(파이썬) - 알약

https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 이 문제는 꽤나 까다로웠던 문제입니다. 이 문제를 빠른 시간 내에 풀 수 있다면 DP관련 문제들은 웬만한 건 해결할 수 있겠다는 생각이 들었죠.먼저 DP로 푸는 문제인 거 같다! 라는 생각을 했고 DP문제를 푸는 과정을 정리해봤습니다. DP는 이전 결과가 다음결과에 영향을 미쳐야 합니다. DP를 풀 때 변수를 어떻게 정할지가 중요합니다. 이전 결괏값을 가져다 쓰기 위해서는 초기화가 중요합니다. 위 세 가지 조건을..

자료구조 & 알고리즘/백준(Baekjoon)

[백준]5014(파이썬) - 스타트링크

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이 문제는 보자마자 BFS로 풀어야겠다는 생각이 들었습니다. 또 생각이 들었던 점은 뱀과 주사위 게임과 거의 유사한 유형이라는 점입니다. 이 문제의 핵심은 BFS 떠올렸어? 그리고 UP, DOWN을 어떻게 표현할래?라고 생각합니다. 이 부분만 인지를 했으면 문제 푸는 데는 어렵지 않았습니다. 한 가지, result를 -1로 초기화하지 않고 0으로 초기화한 뒤, result [s-1] = 0을 제외시키면 31 ..

자료구조 & 알고리즘/백준(Baekjoon)

[백준]5430(파이썬) - AC

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 이 문제는 간단하지만 어떻게 시간을 줄일 거냐? 를 묻는 문제입니다. 저 같은 경우에는 일단 구현을 해놓고 짜 놓은 코드에서 어떻게 시간을 줄일지 생각을 합니다. 사람마다 맞는 방식을 찾는 게 중요한 것 같습니다. 구현은 어렵지 않았습니다. 최대한 for문을 안 쓰고 while과 deque를 사용해서 구현했고, 이 문제에서는 리스트 형식의 문자열을 입력값으로 받기 때문에 파싱을 해서 숫자가 들어있는 문자열로 바꾸는 부분이 중요했다고 생각합니다. 주요 구..

자료구조 & 알고리즘/백준(Baekjoon)

[백준]9019(파이썬) - DSLR

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 이 문제는 보고 처음에 든 생각은 BFS 문제구나 싶었습니다. 항상 2중 리스트에서 상하좌우를 고려해서 풀어나가는 방식의 BFS 문제를 많이 접했는데요, 익숙하지 않아서 BFS 문제라는 확신이 들기까지는 꽤 오래 걸렸죠. 이 문제에서 D, S, L, R 조건을 구현하는 건 어렵지 않았고, 이거 BFS인 거 알겠어? 를 물어보는 문제였습니다. 먼제 D, S, L, R 일 때 각각 다른 ..