👾

문제 링크: www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 시간 내에 문제를 풀기 위해선 동적 계획법(Dynamic Programming)을 이용해 문제를 해결해야 한다. 1로 만들기 위한 연산 횟수를 저장하는 dp테이블을 만들고 dp[1]부터 dp[n]까지를 계산한다. dp[1] = 0 dp[2] = dp[1] + 1 // 2로 나누거나 1을 빼기 dp[3] = dp[1] + 1 // 3으로 나누기 dp[4] = dp[2] + 1 = dp[3] + 1 // 2로 나누거나 1을 빼기 dp[5] = dp[4] + 1 // 1을 빼기 dp[6] = dp[2] + ..

문제 링크: www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제 설명 사이트의 개수는 항상 동쪽이 많으므로 (N

문제 링크: www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 설명 BFS를 이용하여 도시를 모두 방문하는 방법을 이용하였다. BFS를 하는 중 만약 현재 도시의 최단 거리 값이 k 보다 클 경우, 이 뒤에 방문하는 도시들의 최단 거리는 모두 k보다 크므로 BFS를 중지한다. solution 함수 설명 최단 거리가 k인 도시들을 담을 리스트 answer 초기화 출발 도시를 큐에 삽입..

문제 링크: www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 설명 적록색약인 사람과 아닌 사람의 matrix를 따로 만들어서 생각합니다. 저는 적록색약의 matrix는 G를 모두 R로 바꿔서 문제를 풀었습니다. 각각의 matrix를 BFS를 이용해 상, 하, 좌, 우로 연결된 같은 색을 모두 탐색합니다. 이때 상, 하, 좌, 우 인덱스를 편하게 계산하기 위해 dx, dy를 정의해서 사용했습니다. 방문한 matrix의 원소는 0을 대입해서 방문 처..

문제 링크: www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 설명 단순히 DFS와 BFS를 수행하면 됩니다. 저는 (N + 1) X (N + 1) 크기의 matrix를 이용해 정점 간의 간선을 표시했습니다. 또한 dfs를 할 땐 방문한 노드를 1로 표현하고 bfs를 할 땐 0으로 표현해서 visited를 따로 초기화할 필요 없이 바로 사용할 수 있도록 했습니다. 소스코드 def dfs(v): # 방문 노드 1로 표현..

문제 링크: www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 설명 면접자들을 서류 점수가 높은 순서대로 정렬한 뒤, 면접 점수에 대해 생각합니다. 서류 점수가 1등인 사람은 무조건 뽑히고, 2등인 사람은 1등보다 면접 순위가 높으면 뽑힙니다. 3등은 1, 2등보다 면접 순위가 높이면 뽑히고 나머지 사람들도 비슷하게 계산합니다. 따라서 서류 순위가 높은 순서대로 면접자를 정렬하고, 각 면접자들의 면접 순위가 면접 커트라인보다 더 높은..

문제 링크: www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제 설명 만약 n이 1이나 3이 주어진다면, 2원과 5원으로는 거슬러 줄 수 없으므로 -1을 반환합니다. 나머지는 최소 개수의 동전으로 거슬러줘야 하므로 5원을 먼저 거슬러주는 방법을 선택했습니다. n을 5로 나눴을 때 나머지는 다음과 같이 5가지입니다. (x: n을 5로 나눈 몫) 나머지가 0일 경우 5원으로만 거슬러 줄 수 있으므로 answer = x 나머지가 1일 경우 5원을 하나 빼고 2원 3개를 추가해야 합니다. => 5x + 1 = 5(x - 1) + (2 * 3) 따라서 anwer = (x - 1) + ..

문제링크: www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 풀이 분배 법칙을 사용해서 문제를 풀 수 있다. ( ( ) [ [ ] ] ) 의 경우에 2x(2+3x3)으로 계산되는데, 이는 결국 (2x2) + (2x3x3)과 같다. 왼쪽 괄호가 나오면 temp에 2나 3을 곱한 뒤 스택에 push 하고, 오른쪽 괄호가 나오면 temp를 2나 3으로 나눈 뒤 스택을 pop 한다. 이때 ( ( ) [ [ ] ] ) 표시된 괄호처럼 괄호 값이 '( )' 또는 '[ ..

문제링크: www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 식을 마이너스 연산자가 나오기 전과 후로 나눠서 생각할 수 있다. 한 번 마이너스 연산자가 나온 후에는 뒤에 나오는 숫자들은 모두 마이너스로 계산할 수 있다. 예를 들어 1+1+1-1+1-1+1과 같은 식이 있을 때 최솟값을 가지도록 괄호를 치면 1+1+1-(1+1)-(1+1)이 된다. 한 번 -가 나오면 뒤에 나오는 +는 앞의 연산과 괄호로 합쳐서 뺄셈을 해주는 것이다. 따라서 bool ..

문제링크: www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 풀이 키가 작은 사람부터 몇 번째 자리에 서면 되는지 정했다. 정답 배열을 0으로 초기화한 다음, 자기보다 큰 사람이 왼쪽에 2명 있다면 3번째 자리에 서는 방식으로 문제를 해결했다. 작은 키 순서대로 확인하기 때문에 이미 정답 배열에 들어간 사람(줄을 선 사람)은 모두 자신보다 키가 작다고 생각할 수 있다. 예제 입력처럼 [2, 1, 1, 0]이 입력으로 주어졌을 때 answer은 다음 순서..