https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 정리 파이어스톰 시전 (Q회) 2^L X 2^L 크기의 부분 격자로 나누기 모든 부분 격자를 시계방향으로 90도 회전 인접한(상하좌우) 칸 중 얼음 있는 칸이 3개 미만인 칸은 얼음양 - 1 모두 끝난 후 남은 얼음의 합 출력 (완전탐색) 남은 얼음 중 가장 큰 덩어리의 얼음 칸 개수 출력 (BFS) 구현 하기 1. 파이어스톰 → 배열 회전. 회전할 부분 배열 구하기 for i..

https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 이분 탐색으로도 풀 수 있지만 나는 문자열 함수를 사용해서 간단하게 풀었다. 우선 B를 정렬해 두고, A를 순회하면서 A의 생물보다 큰 생물의 첫 번째 인덱스를 구해서 그 값을 answer에 더해줬다. 여기서 주의할 것은 A는 자기보다 작은 애만 먹을 수 있다는 것. 크기가 같은 것은 못 먹는다. 조건들을 좀 더 추가했는데, 만약 B의 가장 큰 ..

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를 ..