CEO

문제 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 풀이 특정 단어가 주어질 때, 다른 단어와 비교하여 하나만 다른 경우에 그 단어로 변환할 수 있다. DSF를 통해 처음 시작하는 문자부터, 변활 할 수 있는 문자와 비교하여 두 문자가 하나만 다른 경우 해당 문자를 기준으로 탐색할 수 있는 과정을 반복한다. 이를 위해 `stack`을 이용하고, 중복을 막기 위해 `defualtdict`를 활용하여 방문 여부를 체크하였다. 코드 from collections i..

문제 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 문제 풀이 처음에 생각할 때는 딕셔너리를 사용하지 않고, 각 경로를 방문해보고 알파벳 순에 따라 가장 앞의 값을 반환하려고 하였다. 하지만 주어진 티켓의 방문 경로에 따라, 딕셔너리를 활용하여 출발지에서 방문가능한 경로를 추가하는 방식을 사용하면 백트랙킹을 하지 않고 문제를 풀 수 있다. { 'ICN': ['ATL', 'SFO'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO'] } 예제 #2의 경우, 딕셔너리를 통해 도착지의 알파벳 순으로 정렬하면 위와 같이..

문제 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 풀이 수열이 주어지고, 수열 중 일부를 선택할 때 선택한 부분이 회문(Palindrome)인지 여부를 반환하는 문제이다. 이 문제를 풀기 전까지는 시간이 충분히 주어지는 회문 문제들을 풀어서, 단순히 list를 조작하는 방식으로 회문을 찾았다. 하지만 이 문제는 그런 식으로 풀면 시간 초과가 발생한다. 다른 DP 문제들과 마찬가지로, 메모이제이션을 통해 길이가 1부터 N까지의 늘려가며 회문인지 여부를 리스트에 기록해두는 방식을 사용한다. 다음과 같이 지정된 범위에 따라 회문의 여부를 결정할 ..

문제 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 기존에 풀었던 퇴사 문제에서 N의 범위가 커진 문제이다. N의 범위가 커짐에 따라 DFS로 풀지 않고 DP로 풀어야 문제를 해결할 수 있다. 즉 최대 수익을 완전 탐색을 통해 찾지 않고, 메모이제이션을 통해 값을 누적시켜가며 N일 까지 진행시켜야 한다. 점화식은 현재 날짜 + 일하는데 필요한 날짜

문제 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀�� www.acmicpc.net 문제 풀이 숫자가 주어 질 때, +, - 를 통해 숫자를 계산 할 수 있으며 계산된 숫자의 범위는 0 보다 크고, 20 보다 작아야 한다. 또한 주어진 숫자를 계산할 때, 마지막으로 주어진 숫자와 일치해야 한다. 예제 입력1의 경우 문제의 주어진 힌트와 같이 다음과 같은 경우의 수가 있다. 8+3-2-4+8-7-2-4-0+8=8 8+3-2-4+8-7-2-4+0+8=8 8+3+2+4-8-7+2-4-0+8=8 8+3+2+4-8-7+2-4+0+8=8 ..

문제 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 풀이 리스트를 만들 때, list[선택하고자 하는 아이템의 수][최대 가치]로 2차원 배열을 만든다. list[0]은 아무것도 연주하지 않은 상태, 최초에 볼륨을 적용한 상태이므로 list[0]의 값들은 0이다. 2중 반복문을 순회하면서 list[1], list[2] ... 로 접근하며 가방에 넣을 수 있는 아이템의 상태를 기록한다. n * m 만큼의 반복문을 순회하면, 최대 값어치을 체..

짧다면 짧고, 길다면 긴 대학원 생활이 오늘 부로 끝난다. 사회로 나가 일을 하다 보면, 지금 느낀 생각들 또는 감회들이 잊히고 무뎌지기 마련이다. 잊어버리기 전에 추억들을 기억해보고자 한다. 왜 대학원을 가고자 했는가? 내가 대학원을 가고자 했던 이유는 많은 대학원생들이 입학을 결심하는 이유와 비슷할 거라고 생각한다. 막상 학부생으로 졸업을 하니, 한 분야에 대해 명확히 아는 것도 아니고 전문성이 없다고 느껴졌다. 학부 과정 중에 분산처리, 스토리지에 대한 관심이 증가하면서 대학원 입학을 결정하였다. 어제는 대졸, 오늘부터 대학원생 대학원을 가야하는가에 대해, 한 학기 정도 고민을 한 후에 2018년도 2학기부터 석사로써 연구실 생활을 시작하였다. 학기가 시작하기 전 리눅스 커널 캠프를 참가하고, 리눅..

문제 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제 풀이 연주할 곡과 현재 볼륨, 최대 볼륨과 함께 각 곡을 연주할 수 볼륨 리스트가 주어진다. 조절할 수 있는 볼륨은 현재 연주곡이 1번이라면 볼륨 리스트 1번의 볼륨 크기만큼 추가하거나, 더하여 0보다 크거나 최대 볼륨보다는 작을 경우에만 연주가 가능하다. 만약 연주가 불가능하다 보면 -1을 출력하여야 한다. 처음 문제를 접하였을 때는 연주할 수 있는 볼륨을 -하거나 +하여야 하므로, DFS로 풀어야 한다고 생각하..