본문 바로가기
반응형

Problem Solving/BOJ228

백준 14888번 연산자 끼워넣기 - 스위프트(Swift) 풀이 1. 앞에서부터 차례로 연산자를 정한다. 2. 다음 연산자를 고를 때는 남은 연산자 중에 하나를 고른다. 3. N-1개의 연산자를 다 골라서 완성했으면 결과값을 가지고 최대, 최솟값을 갱신한다. 1. 앞에서부터 차례로 연산자를 정한다. N이 최대 11로 매우 작다. 연산자 개수는 최대 N-1 = 10개이므로, 10가지 종류의 연산자가 있다고 하더라도 모든 경우의 수가 10! 밖에 되지 않는다. 따라서 브루트 포스로 N-1개 연산자를 줄 세우는 모든 경우를 고려해주어도 시간 안에 통과가 가능하다. 앞에서부터 차례로 연산자를 정해주자. 2. 다음 연산자를 고를 때는 남은 연산자 중에 하나를 고른다. operators[i]를 남아있는 연산자 i의 개수, bruteForce(index, currentValue).. 2022. 2. 10.
백준 2581번 소수 - 스위프트(Swift) 풀이 1. 에라토스테네스의 체를 이용하여 1 이상 10,000 이하의 자연수에 대해 소수 여부를 구한다. 2. M부터 N까지 순회하면서 최소 소수와 소수들의 합을 구한다. 1. 에라토스테네스의 체를 이용하여 1 이상 10,000 이하의 자연수에 대해 소수 여부를 구한다. 에라토스테네스의 체를 이용하면 O(NloglongN)에 1 이상 N이하인 모든 자연수에 대해 소수 여부를 구할 수 있다. N이 최대 10,000이기 때문에 굳이 에라토스테네스의 체를 사용하지 않아도 1~(i-1)까지로 전부 나눠봐서 소수인지 판별하는 O(N^2)을 알고리즘을 사용해도 시간 내에 통과가 가능하다. 2. M부터 N까지 순회하면서 최소 소수와 소수들의 합을 구한다. M부터 N까지 단순 순회하면서 소수들만 골라 더하고, 처음으로 나오.. 2022. 2. 10.
백준 2133번 타일 채우기 - 스위프트(Swift) 풀이 + 그림 설명 1. dp[index][first][second][third] = index번째 열의 각 행 상태가 first, second, third일 때, index열부터 남은 열을 모두 채우는 경우의 수 2. 현재 열의 상태에 따라 가능한 모든 경우의 수를 더한다. 1. dp[index][first][second][third] = index번째 열의 각 행 상태가 first, second, third일 때, index열부터 남은 열을 모두 채우는 경우의 수 다이나믹 프로그래밍을 이용한다. dp[index][first][second][third]를 위와 같이 정의한다. first, second, third는 0일 때는 비어있음, 1일 때는 채워져 있음을 나타낸다. 최종적으로 구해야하는 것은 dp[0][0][0][0.. 2022. 2. 9.
백준 1022번 소용돌이 예쁘게 출력하기 - 스위프트(Swift) 풀이 1. (r1, c1)부터 (r2, c2)까지 직접 채운다. 2. 가장 길이가 긴 숫자의 길이를 구한다. 3. 포맷에 맞춰 출력한다. 1. (r1, c1)부터 (r2, c2)까지 직접 채운다. 단순 구현 문제이다. r, c 범위가 절댓값 5000까지인데, (-5000, -5000)부터 (5000, 5000)까지 전부 구해도 총 연산 횟수 10^8로 시간 초과가 나지 않는다. 하지만 10^8개의 Int를 선언하면 메모리 초과가 난다. 문제에서는 다음과 같은 조건을 두고 있다. 0 ≤ r2 - r1 ≤ 49 0 ≤ c2 - c1 ≤ 4 따라서 실제 2차원 배열은 정답이 될 50*5 사이즈로만 선언해둔다. 그리고 소용돌이를 채울 때, 50*5 범위에 들어가는 것들만 정답 배열에 기록하고 범위 밖인 것은 그냥 스.. 2022. 2. 9.
백준 2568번 전깃줄 - 2 - 스위프트(Swift) 풀이 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 2. 1번 결과에서 B만 모아 만든 배열에서 가장 긴 증가하는 부분 수열을 구한다. 3. (N - LIS길이)가 없애야 하는 전깃줄의 최소 개수이며, LIS에 속하지 않는 전깃줄이 제거해야하는 전깃줄이다. 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 2565번 문제에서 제거해야 하는 전깃줄 목록까지 추가로 구하는 문제이다. 기본 원리는 아래와 같다. 백준 2565번 전깃줄 - 스위프트(Swift) 풀이 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 2. 1번 결과에서 B만 모아 만든 배열에서 가장 긴 증가하는 부분 수열의 길이를 구한다. 3. N - LIS가 없애야하는 전깃줄의 최소 개수이다. 1. 전깃줄 please-amend.tistory.c.. 2022. 2. 7.
반응형

티스토리툴바