본문 바로가기

반응형

분류 전체보기

(395)
[BOJ] 백준 2740 행렬 곱셈 (Swift) 문제 https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 풀이 행렬의 곱을 구하는 문제입니다. n * m 행렬과 m * k 행렬을 곱한다면 n * k 행렬이 만들어집니다. 행렬을 곱할 때, 요소들이 어떻게 곱해지는지 직접 그려서 확인해서, for문을 어떻게 사용해야할 지 감을 잡을 수 있을겁니다. 소스코드 후기 행렬의 곱을 for문으로 구현했는데, 머릿속으로만 구현하려다 애먹었던 문제였습니다. 노트에 직접 그려서 확인하면서 구현했..
[BOJ] 백준 1629 곱셈 (Swift) 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 단순히 21억번 제곱하게 된다면 ($O(n)$) 시간내에 해결할 수 없습니다. 문제 예제와 같이 $10^{11}$ 을 구한다고 가정해보겠습니다. 단순히 11 제곱을 구하면 11번의 연산이 필요하겠죠? 분할 정복 알고리즘을 사용해 $O(log_n)$ 의 시간복잡도를 갖도록 동작할 수 있습니다. $10^{11} = 10 * 10^{10}$ 이고, $10^{10} = 10^5 * 10^5$ 가 되겠죠? $10^5 = 10 * 10^4$ 이고, $10^4 =..
[BOJ] 백준 1780 종이의 개수 (Swift) 문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 풀이 분할 정복을 사용하여 풀이할 수 있는 문제입니다. 2630 색종이 만들기 와 유사한 문제입니다. 단순히 4개 대신 9개로 나누는 문제입니다. 기존에 2630 문제를 풀었다면 로직이 거의 유사해서 쉽게 풀 수 있는 문제라고 생각합니다. 소스코드 후기 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄어가는 방식인 분할 정복 기법을 사용하여 풀이할 수 있는 문제입니다.
[BOJ] 백준 1992 쿼드트리 (Swift) 문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 분할 정복 알고리즘을 사용하여 풀이할 수 있는 문제입니다. 압축된 문자열을 보면, 분할될 때, 괄호를 열고 분할된 문자열이 압축이 끝나면 닫아줍니다. 주어진 영상이 모두 0이나 1인지 확인하고, 0이라면 문자열에 0, 1이라면 1을 써주고 모두 0이나 1이 아니라면, 한 변을 2/n 으로 4등분하여 재귀함수로 다시 검사해줍시다. 4등분을 하게될 때가 분할될 때이므로 이때 괄..
[BOJ] 백준 2630 색종이 만들기 (Swift) 문제 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 그림으로 설명이 잘 되어있는 문제입니다. 처음에는 n * n 종이를 검사해서, 전체 종이가 같은색으로 칠해져 있는지 확인해주고, 0으로 같은색이라면 흰색, 1로 같은색이라면 파랑색 종이를 세어 줍시다. 전부 같은색인지 확인을 해주기 위해서는 0의 개수와 1의 개수를 세어서 그 갯수가 n * n 의 갯수라면 전부 같은 색입니다. 같은 색이 아니라면, 한 변을 n..
[BOJ] 백준 13305 주유소 (Swift) 문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 이 문제는 그리디 알고리즘의 말 그대로, 현재 상황의 최적의 해를 고르는 방식으로 풀이할 수 있습니다. 이와같이 도시가 있다면, 첫번째 도시에서는 무조건 2리터는 주유를 해야합니다. 2리터를 주유를 하고 난 뒤, 두번째 도시로 가게됩니다. 첫번째 도시보다 기름 값이 더 싸기 때문에 두번째 도시에서 3리터 만큼 주유를 하고 세번째 도시로 이동합니다. 세번째 도시에서는 두번째..
[BOJ] 백준 1541 잃어버린 괄호 (Swift) 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 괄호를 적절히 쳐서 식을 최소로 만들기 위해 어떤 방법을 사용해야 할까요? 모든 수식이 "+"라면 양수를 전부 더해주는 방법 밖에 없습니다. 하지만 "-"가 하나라도 있다면 어떨까요? 10 + 20 - 30 + 40 이란 식이 있다면 괄호를 어떻게 쳐줘야할까요? 10 + 20 - (30 + 40) 처럼 괄호를 쳐주어야 최소 값이 나오겠죠? 10 + 20 - 30 - 40 + 50 ..
[BOJ] 백준 11399 ATM (Swift) 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 오름차순으로 정렬을 해주어야, 뒷사람이 기다리는 시간이 줄기 때문에 시간의 합을 최소로 만들 수 있습니다. 문제 설명을 보면 힌트를 얻을 수 있습니다. 오름차순으로 정렬을 하고, 시간의 합을 누적하고, 누적된 시간의 합을 계속해서 더해주어 출력해주면 끝입니다. 소스코드 후기 오름차순으로 정렬만 해주면 쉽게 풀 수 있는 문제였습니다.

반응형