반응형 브루트포스25 백준 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. 백준 1007번 백터 매칭 - 스위프트(Swift) 풀이 1. 각 점을 위치 벡터로 생각한다. 2. 점 A에서 B로 가는 벡터는 (B 위치 벡터) - (A 위치 벡터)이다. 3. 절반을 역벡터로 만든 뒤 모든 벡터를 합치면 벡터 매칭에 있는 벡터의 합을 구할 수 있다. 1. 각 점을 위치 벡터로 생각한다. 먼저 각 점을 위치 벡터로 생각해줄 것이다. 2. 점 A에서 B로 가는 벡터는 (B 위치 벡터) - (A 위치 벡터)이다. 다음과 같은 성질을 이용할 것이다. 두 점 A, B를 골라 A→B 또는 B→A로 가도록 벡터로 잇는 작업은, 두 점 A, B를 고른 뒤 두 점으로 가는 위치 벡터 중 하나를 역벡터로 만드는 작업이라고 할 수 있다. 3. 절반을 역벡터로 만든 뒤 모든 벡터를 합치면 벡터 매칭에 있는 벡터의 합을 구할 수 있다. 결국 구해야 하는 것은 벡터.. 2022. 2. 4. 백준 2143번 두 배열의 합 - 스위프트(Swift) 풀이 1. A의 모든 부 배열에 대해 합을 구해 각 합을 만들 수 있는 경우의 수를 카운트해둔다. 2. B의 모든 부 배열에 대해 합을 구해 각 합을 만들 수 있는 경우의 수를 카운트해둔다. 3. A의 모든 부 배열합 sum에 대해 (A의 부 배열 합이 sum이 되는 경우의 수) X (B의 부 배열 합이 T-sum이 되는 경우의 수)를 더한다. 1. A의 모든 부 배열에 대해 합을 구해 각 합을 만들 수 있는 경우의 수를 카운트해둔다. N=1000이므로 O(N^2)으로 모든 부 배열을 다 고려해볼 수 있다. 모든 부 배열에 대해 합을 구하면서 그 합을 만들 수 있는 경우의 수를 카운트해준다. 부 배열 합이 sum이 되는 경우의 수(count)를 딕셔너리에 dict[sum] = count 형태로 저장해준다. 원.. 2022. 2. 3. 백준 12100번 2048 (Easy) - 스위프트(Swift) 풀이 + 그림 설명 1. 미는 방향으로 블록을 몬다. 2. 인접한 두 블록을 미는 방향으로 합칠 수 있으면 합친다. 3. 합치면서 생긴 빈자리를 없앤다. 4. 4^5가지 경우에 대해 전부 다 시뮬레이션(1-3과정)하여 최댓값을 구한다. 1. 미는 방향으로 블록을 몬다. 아래와 같은 보드 상태에서 위로 밀어야 하는 상황이다. 열 별로 차례로 밀어줄 것이다. 1열부터 밀어보자. 먼저 빈 공간이 없도록 윗방향으로 블록들을 몰아준다. 2. 인접한 두 블록을 미는 방향으로 합칠 수 있으면 합친다. 이제 합칠 차례이다. 만약 인접한 두 블록을 합칠 수 있는 경우 합친다. 미는 방향이 윗방향이기 때문에 윗블록이 남고 아랫 블록은 사라진다. 3. 합치면서 생긴 빈자리를 없앤다. 합치면서 생긴 빈자리를 또 메꿔주면 미는 작업이 끝난다. 나.. 2022. 1. 29. 백준 1436번 영화감독 숌 - 스위프트(Swift) 풀이 먼저 브루트포스로 가능한 지부터 고려해야 한다. 1, 2, 3... 이렇게 1부터 차례로 666이라는 수를 포함하는지 체크해서 N번째로 666을 포함하는 수를 만나면 출력하고 break 해주면 간단하게 구할 수 있을 것이다. 이 방법이 제한 시간 안에 통과되는지 계산해보자. 일단 N의 최대값이 10,000이다. N = 10,000일 때 답이 몇 일지 예상해야 한다. (예상 못하겠으면 그냥 N=10,000으로 두고 위에 반복문 돌려서 기다려보면 알 수 있긴 하다.) 대충 666이 맨 끝에 오는 경우만 생각해줘 봤는데, 10,000가지가 되려면 채우려면 666 앞에 4자리가 더 붙어야 한다. _ _ _ _ 666 이렇게 되면 각 자리마다 0-9가 들어갈 수 있으니까 10,000가지가 될 것이다. 따라서 N .. 2022. 1. 13. 이전 1 2 3 4 5 다음 반응형
