→

문제link: https://www.acmicpc.net/problem/9095주어진 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다. 접근방법을 구할 때, 수의 순서를 고려하는 것을 유념해야 한다. (1+2, 2+1을 별개로 본다.)가짓수를 세다 보면 규칙을 발견할 수 있다.f(n)이 n을 만들기 위한 방법의 수라고 할 때,f(n) = f(n-3) + f(n-2) + f(n-1)이 된다.이 문제에서는 n의 합을 구하기 위해 숫자 1, 2, 3만 사용한다.n의 합은 ((n-3)의 합 +3) + ((n-2)의 합 +2) + ((n-1)의 합 +1)과 같다.따라서 f(n-3) + f(n-2) + f(n-1) = f(n)이 된다. 코드import sysinput = sys.stdin.rea..

문제link: https://www.acmicpc.net/problem/2606연결된 컴퓨터의 번호 쌍을 입력받아, 바이러스에 감염된 컴퓨터의 수를 구하는 문제이다. 접근컴퓨터 번호 쌍을 입력받아 저장한다. 1번 컴퓨터에서부터 바이러스가 퍼져나가므로 1번 컴퓨터와 연결된 컴퓨터를 확인해 개수를 세어 출력하도록 했다.DFS를 활용했고, 한번 방문한 노드는 재방문하지 않도록 했다. 코드import sysinput = sys.stdin.readlinedef check(n): visited[n] = 1 for c in computers[n]: if not visited[c]: check(c)N = int(input())computers = [[] for _ in..

문제link: https://www.acmicpc.net/problem/2579계단을 오르면서 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 접근DP를 이용해 문제를 풀었다.계단마다 점수가 있고, 계단을 오르며 점수를 획득할 수 있다. 계단은 한번에 한 칸 또는 두 칸을 오를 수 있으며, 연속으로 세 칸을 밟을 수는 없다. 마지막 계단은 꼭 밟아야 한다.마지막 계단에 꼭 도달해야 하므로, '이 계단에 도달하기 전에 어떤 계단을 밟았을까?' 시점에서 문제를 풀면 금방 점화식을 찾을 수 있다. 처음에 시작점이 첫 번째 계단인 것으로 잘못 이해해 틀린 답을 한 번 제출했다 ㅎㅎ; 시작점->첫 번째 계단->두 번째 계단->... 이다! 코드import sysinput = sys.stdin.readlineN =..

문제link: https://www.acmicpc.net/problem/1003주어진 함수의 특정 행이 몇 번 호출되는지를 구하는 문제이다. 접근문제에서 주어지는 함수는 피보나치 수열을 구하는 재귀 함수로, fibnacci(0)이면 "0", fibonacci(1)이면 "1"을 출력하게 되어 있다.0과 1이 출력되는 수를 각각 구해야 하는데, 이 0과 1이 출력되는 횟수 또한 규칙적으로 증가한다.함수 fibonaccci(n)의 n이 0, 1, 2, 3, ...일 때,"0"은 1, 0, 1, 1, 2, 3, 5, 8, 13, 21...,"1"은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... 순으로 증가한다.따라서 피보나치 수열을 미리 구해 리스트에 저장한 후, 입력값에 따라 알맞은 출력 횟수..

문제link: https://www.acmicpc.net/problem/17219사이트 주소에 맞는 비밀번호를 출력하는 문제이다. 접근사이트 주소와 비밀번호를 딕셔너리에 저장하여 문제를 해결했다. 코드import sysinput = sys.stdin.readlineN, M = map(int, input().split())d = dict()for _ in range(N): url, pw = input().strip().split() d[url] = pwfor _ in range(M): print(d[input().strip()])

문제link: https://www.acmicpc.net/problem/11399N명의 사람이 한 줄로 서서 ATM을 이용한다고 할 때, 돈을 인출하는 데 걸리는 시간 합의 최솟값을 계산하는 문제이다. 접근한 사람이 ATM을 이용하고 있으면 그 시간동안 다음 사람들은 당연히 대기하게 된다. 시간이 적게 걸리는 순으로 돈을 인출하는 경우에 시간 합이 최솟값이 되므로 시간 순으로 정렬하여 계산했다.첫 번째 사람이 돈을 인출하는 시간은 모든 사람이 함께 소모한다. 하지만 마지막 사람이 돈을 인출하는 시간은 마지막 사람 혼자만 소모한다. 따라서 첫 번째 사람의 시간 P1에는 *N, ..., 마지막 사람의 시간 Pn에는 *1한 후 모두 더해 주었다. 코드N = int(input())P = sorted(map(in..

문제link: https://www.acmicpc.net/problem/18741부터 n까지의 숫자를 스택에 push, pop할 때 주어진 수열이 만들어질 수 있는지를 확인하는 문제이다. 접근오름차순으로 숫자를 스택에 push하면서, 입력받은 수열의 j번째 인덱스와 값이 같으면 pop하고, j를 증가시킨다. 코드import sysinput = sys.stdin.readlinen = int(input())a = [int(input()) for _ in range(n)]b = []ans = []i, j = 0, 0while i

문제link: https://www.acmicpc.net/problem/1966 접근collections의 deque를 사용해 deque를 만든 후, rotate를 이용해 큐를 회전해가며 중요도가 높은 순으로 출력하도록 했다. M번째 인덱스의 값이 언제 출력되는지를 확인해야 하므로, 초기 인덱스를 함께 저장했다.rotate()에 음수를 넣을 경우 왼쪽으로, 양수를 넣을 경우 오른쪽으로 회전한다. 값을 꺼낼 때는 popleft()로 0번째 인덱스 값을 꺼내고, rotate(-1)로 왼쪽 방향으로 회전시키며 중요도를 비교했다. 코드import sysinput = sys.stdin.readlinefrom collections import dequefor _ in range(int(input())): N,..

문제link: https://www.acmicpc.net/problem/11723집합을 구현하는 문제이다. 접근명령에 맞게 집합의 add, remove와 같은 동작을 수행한다.remove()의 경우 삭제하려는 key가 집합 내에 존재하지 않으면 KeyError가 발생한다. discard()는 그렇지 않다. if문으로 확인 후 존재하는 경우에만 remove()하는 대신, discard()를 사용해 remove 동작을 처리했다. 코드import sysinput = sys.stdin.readlineS = set()allS = set(range(1, 21))for _ in range(int(input())): tmp = input().split() if tmp[0] == 'add': S...

문제link: https://www.acmicpc.net/problem/10845큐를 구현하는 문제이다. 접근입력받은 명령에 맞추어 큐로서 동작하도록 코드를 구현했다. FIFO에 따라 동작한다.push되는 원소는 리스트 q의 끝에 저장한다. front 인덱스 값과 rear 인덱스 값을 변수에 저장해 pop 시 별다른 원소 제거 없이 변수 값을 조정하여 처리하도록 했다. 코드import sysinput = sys.stdin.readlineq = []f = -1r = -1for _ in range(int(input())): tmp = input().split() if tmp[0] == 'push': q.append(tmp[1]); r += 1 elif tmp[0] == 'pop': ..