백준 - 센서(Swift) 문제 설명 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 나의 풀이 문제를 이해하기 어려웠던 문제다. 기지국을 어떠한 좌표에 설치하고 커버하는 방식인 줄 알았는데 다른 글들을 살펴보니 구간을 커버한다는 말이었다. 사실 집중국의 수신 가능영역은 고속도로 상에서 연결된 구간으로 이루어졌다는 말을 보고 짐작은 했으나 아이디어가 떠오르지 않아서 좌표로 생각한 것 같다. 그래서 이 문제는 그리디하게 ..

백준 - 공항(Swift) 문제 설명 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 나의 풀이 상당히 어려웠던 문제다. 처음 접근은 비행기가 도킹할 수 있는 게이트가 주어졌을때 가장 큰 부분을 배치하면 된다라는 아이디어였다. 하지만 방문처리하는 부분이 애매했다. 예를들어 1~6까지의 게이트가 있고 3개의 비행기가 갈수있는 게이트가 6 6 6으로 주어졌다면 처음 6에 대한 부분은 false로해서 만들 수 있지만..

백준 - 크게 만들기(Swift) 문제 설명 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 나의 풀이 처음에는 큰 숫자가 앞에 있어야한다는 것을 알았기에 투 포인터로 이용해서 문제를 풀었다. 하지만 500,000인 상태에서 투 포인터를 계속 앞으로 리셋하면서 돌리는 것은 말도안되는 시간복잡도를 결과로 내놓는다. 이 때문에 다른 풀이를 참고하다가 스택을 사용하는 것을 알게되었다. 스택이라는 추가적인 자료구조를 사용함으로써 새로 들어오는 값에 대해서는 마지막값과 비교하는 로직을 담을 수 있게 되었다. (기존의 투 포인터는 ..

백준 - 빵집(Swift) 문제 설명 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 나의 풀이 첫번째로 가장 최대로 파이프라인을 까는 것은 그리디한 접근으로 맨 위부터 채우는 것이다. 만약 오른쪽 위, 오른쪽, 오른쪽 아래의 길이 있을때 오른쪽 아래를 선택해서 파이프라인을 형성했다면 그 아래의 길들은 위쪽이 막혀서 설치할 경우의 수가 줄어들게 된다. 이 때문에 최대한으로 만들기 위해서는 오른쪽 위, 오른쪽, 오른쪽 아래로 순서대로 탐색해야 한다. 이 문제는 ..

게임을 만든 동준이 문제 설명 https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 나의 풀이 처음에는 앞에서부터 탐색할까 했었는데 그렇게 되면 5 5 5의 경우 첫번째는 3이 되어야하는데 4가 되기 때문에 바로 문제가 생겼다. 그래서 맨 끝에서부터 1씩 차이나는 것이 가장 균형있게 조금씩 줄이는 것이라고 판단해서 풀었다. import Foundation let n = Int(readLine()!)! var arr: [Int] = [] for _ ..

백준 - 병든 나이트(Swift) 문제 설명 https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 나의 풀이 문제에서 n과 m의 범위가 2억까지인 것을 보고, 이동방법이 4가지 이상인 경우는 한번 이상씩 사용해야한다는 것을 보고 조건별로 풀어야 한다는 것을 직감했다. 즉 4가지 이하의 경우와 4가지 이상의 경우를 따져봐야한다. 일단 N이 1일때(행이 1)는 위나 아래로 갈 수 없기 때문에 처음위치인 1칸이 최대값이다. N이 2일때는 위로한칸 오른쪽으로 두칸과 아래로한칸 오른쪽으로 두칸밖에 할 수없다. 그렇기에 4가..