https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 정렬하고, 완전탐색으로 각 점들을 순회했다. 양쪽으로 화살표를 가리키게 할 수 있는데, 방향에 따라 범위를 넘어선 경우(-1, n)와 색상이 다른 경우를 제외하고 left와 right 화살표 길이를 구할 수 있다. import Foundation /* 각 점은 N개의 색깔 중 하나를 갖는다 각 점 p에 대해서, p에서 시작하는 직선 화살표를 이용해 다른 점 q를 연결하려고 한다. 여기서 ..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹으로 푼 문제 주어진 알파벳(정렬 필수)으로 중복 제외/비내림차순으로 순열을 만들고 자음이 2개 이상, 모음이 1개 이상인지 확인(checkAlpha(str:))한다. import Foundation /* L개의 다른 알파벳 소문자로 구성. 최소 한개의 모음, 최소 2개의 자음으로 구성 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열 (오름차순) */ let input = readLine(..

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 굉장히 많은 시행착오를 겪은 문제... 구현 방법(흐름) fireBalls 배열에는 현재 존재하는 파이어볼을 넣어놓는 배열 [FireBall] array에는 어떤 좌표값에 파이어볼을 넣어놓는 배열 → ex) (2, 3) 위치에 FireBall() 객체 넣어놓는다 k번 반복 파이어볼 이동이동한 좌표를 기준으로 array 배열에 파이어볼 넣기 현재 파이어볼을 넣..

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 문제 제목만 봐도 머리가 어질 하다 분명 굉장히 킨 코드를 짜야할 거 같은 느낌이 드는... 구현 문제였는데 이 문제는 처음에 풀었을 때 2시간 동안 풀었는데 결국 해결하지 못했다. 이 마법사 상어 문제를 풀면서 느낀 건 구현 문제는 문제가 원하는 것이 무엇인지 제대로 알고, 조건을 꼼꼼하게 체크해야 하는 거 같다. 기능 메소드들도 구분하고, 기능들이 나누어지는데 ..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 처음에는 이분탐색으로 했는데 시간초과 나서 딕셔너리를 사용해서 해당 카드의 개수를 세고 출력해 주는 방식으로 했다. [시간 초과 코드] import Foundation let n = Int(readLine()!)! var sg = readLine()!.split(separator: " ").map{ Int(String($0))! }.sorted() let m = ..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 이분탐색으로 간단하게 해결할 수 있는 문제. N이 작으면 이분탐색보다는 선형탐색이 더 낫지만 500,000까지 가므로 이분탐색으로 해줬다. 듣지도 못한 사람의 명단을 String 배열로 만들어줬고, 보지도 못한 사람들을 하나씩 받아서 이분탐색으로 듣지도 못한 사람 명단에 이름이 있는지 확인해 줬다. import Foundation let input = readLine()!.split(separa..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이번 문제는 브루트포스/백트래킹으로 풀었다. N/2 명의 경우의 수만 구하면 start 팀과 link 팀의 능력치를 구할 수 있다. 0~(n-1) 중 n/2개를 선택하면 되므로 이에 따른 백트래킹을 구현해 주었다. 일단, 따로 선수를 배열에 넣지 않고 선택한 선수를 visited 부울 배열에 true로 넣고 만약 n/2명을 선택했다면 true인 애들은 start 팀에 능력치를 넣어준다. 여기서 for-in loop를 ..

https://www.acmicpc.net/problem/16508 16508번: 전공책 곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 www.acmicpc.net 브루트포스 문제. 백트랙킹으로 풀었는데 정말 많이 틀렸다..^^ 지금 생각해 보면 사실 그렇게 틀릴 일이 없는데,, 백트래킹 문제를 꽤 오랫동안 안 풀었더니 더 헤맸던 것 같다 다시 공부하자! 처음에는 만들고자 하는 단어와 전공책 제목과 직접적으로 비교하고, removeLast(), remove() 메소드를 사용해서 삭제해 주는 쪽으로 했다. 그런데 이렇게 하니 시간초과 발생(91%에서..😭). c+..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net N일동안 최대한 많은 상담을 하고, 최대 수익을 얻어라. 이 문제는 N이 15보다 작기 때문에, 완전탐색으로 해도 충분할 거라고 생각했다. 게다가 시간제한이 2초! DFS를 사용해서 시작날짜로부터 깊게 들어가도록 했다. 튜플을 사용해서 (기간, 금액) 배열을 만들고, 1일~N일을 시작날짜로 잡고 DFS를 돌렸다. 여기서 N일도 가능한 것은 1일 상담이라면 N일도 가능하기 때문. 모든 날짜가 가능한것은 아닌데, 만약 해당 날짜에 시작한 상담이 퇴사날을 넘어서게 된다면 이 상담은 하지 않아야 한다. 그러므로 이 경우는 continue로 ..