해당 문제는 수열 A가 주어졌을 때 원소들을 지우면서 "B[0] > B[1] B[3] "를 찾고, 다음 ""를 찾는 과정을 반복하면 문제를 해결할 수 있다. 이유는 다음과 같다. a > b e: 이 경우 >, 총 3번 반복했으므로 답은 4가 된다. b e , , d>e는 c>e만 남길 수 있다. 이때 be를 만족하고, ebe sequence[i+1]: flag = 1 result += 1 elif flag == 1 and sequence[i] < sequence[i+1]: flag = 0 result += 1 print(result+1)
Algorithm
해당 문제는 로마 숫자가 주어졌을 때 로마 문자들을 재배치하여 가장 작을 수를 찾아내는 문제다. 입력으로 주어지는 로마 숫자는 1~99까지의 양수이고, 우리가 만들 수 있는 수 역시 1~99까지의 수 밖에 되지 않으므로 Brute Force를 사용하기로 결정했다. 처음으로 떠올린 방법은 I, V, X, L, C의 개수에 따라 최소값을 모두 구하는 방식이다. 즉, I가 1개인 경우, I가 1개, X가 2개인 경우 등 모든 경우를 살펴보고, 해당 경우들의 최소값을 미리 배열에 저장하는 것이다. 따라서 입력으로 받아온 문자의 I, V, X, L, C의 개수를 보고 우리는 구했던 최소값을 찾아 출력하면 된다. 이를 위해 크기가 128인 배열 하나를 선언했다. 그리고 조합 가능한 모든 문자열을 살펴보며 (I의 개..
문제에서 주어진 바와 같이 우리는 준서가 버틸 수 있는 무게에 맞추어 최대 가치를 가지도록 배낭에 물건을 담아야 한다. 이를 위해 knapsack 알고리즘을 활용할 수 있다. 만약 다음과 같이 물건과 가치가 주어졌다고 할 때 버틸 수 있는 무게를 10으로 놓고 knapsack 알고리즘이 어떻게 진행되는지 살펴보자. 물건 1 2 3 4 무게 5 6 4 3 가치 20 10 30 40 knapsack 알고리즘을 위해서는 dp table을 생성해야 한다. 이를 위해 (물건의 개수+1) ×(버틸 수 있는 무게+1) 만큼의 크기를 가진 table을 생성한다. 이때 (물건의 개수+1) 만큼의 행을 가지도록 생성한 이유는 knapsack알고리즘을 적용하기 위해서다. 배낭 용량 0 1 2 3 4 5 6 7 8 9 10 ..
알파벳을 탐색할 때 고려해야할 조건은 다음과 같다. 다음에 탐색하는 인덱스가 배열 범위를 넘어가는가? 다음 알파벳을 이전에 만난적이 있는가? 위를 고려하여 DFS 방식으로 탐색하면 다음과 같이 구현할 수 있다. import sys input = sys.stdin.readline def dfs(x, y, tmp): # 현재까지 탐색한 결과가 최대 이동 횟수라면 result에 저장한다. global result result = max(result, tmp) # 현재 위치에 해당하는 알파벳에 방문처리를 한다. index = ord(board[x][y])-ord("A") visited[index] = True # 모든 방향으로 이동하여 dfs 탐색을 수행한다. for i in range(4): next_x, n..
해당 문제는 Floyd Warshall 알고리즘을 사용해 풀 수 있는 문제다. Floyd Warshall 알고리즘은 a에서 b도시로 이동하는 최단 거리를 임의의 도시 c를 경유하는 모든 경우를 고려하여 구하는 알고리즘이다. 즉, 총 도시의 개수가 5개인 경우 1에서 2로 이동하는 최단 거리를 찾을 때 아래 경우를 모두 고려한다. 도시 1에서 도시 1로 이동 후 도시 1에서 도시 2로 이동 도시 1에서 도시 2로 이동 후 도시 2에서 도시 2로 이동 도시 1에서 도시 3로 이동 후 도시 3에서 도시 2로 이동 도시 1에서 도시 4로 이동 후 도시 4에서 도시 2로 이동 도시 1에서 도시 5로 이동 후 도시 5에서 도시 2로 이동 해당 알고리즘은 DP을 활용하여 다음과 같이 구현할 수 있다. import s..
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지지만, 높이는 서로 다를 수 있다. 아래는 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이며 색칠된 부분은 가장 넓은 직사각형이다. 위와 같이 가장 넓은 직사각형을 구하기 위해서는 다음과 같은 알고리즘을 적용할 수 있다. 이때 히스토그램의 각 부분(2, 1, 4, 5, 1, 3, 3의 높이를 가지는 객체)를 ‘막대기’라고 부르자. 모든 막대기 중에 가장 낮은 높이의 막대기를 선택한다. (가장 낮은 높이) × (막대기의 개수)를 통해 현재 히스토그램에서 가장 낮은 높이의 직사각형의 넓이를 구한다. 가장 낮은 높이의 막대기를 기준으로 왼쪽과 오른쪽으로 나눈다. 각 부..
11049번: 행렬 곱셈 순서첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같www.acmicpc.net 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 이때 행렬 N개를 곱하는데 필요한 곱셈의 연산 수는 행렬을 곱하는 순서에 따라 따라지게 된다. 즉, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우 A, B를 먼저 곱하거나 B, C를 먼저 곱하는 경우 각각 90번, 126번으로 곱 횟수가 다르다. 이때 행렬 N개의 크기가 주어지고, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값..
