본문 바로가기
반응형

분류 전체보기

 (395)
[BOJ] 백준 1018 체스판 다시 칠하기 (Swift) 문제 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 먼저, 보드를 8x8 사이즈로 잘라서 체스판을 만들 수 있는 경우를 다 따져봐야합니다. 예를 들어 9x9 사이즈라면, 총 4개의 체스판이 나올 수 있습니다. 자른 후에는 8x8 사이즈의 체스판을 맨 왼쪽 윗칸이 흰색인 체스판, 검은색인 체스판과 다르게 칠해져있는 경우의 수를 찾으면 됩니다. 맨 왼쪽 윗칸이 흰색인 체스판을 보면, 행과 열의 합이 짝수인 경우는 흰색으로, 홀수인 경..
[BOJ] 백준 7568 덩치 (Swift) 문제 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 풀이 이 문제에서는 덩치는 키와 몸무게가 둘 다 크다면 덩치가 더 큰 것으로 판단합니다. 자기 자신보다 덩치가 큰 사람의 수 + 1이 자신의 덩치 등수가 되므로, 자기 자신과 모든 사람과의 덩치를 비교를 해서 풀이할 수 있습니다. 즉, 완전탐색으로 풀이할 수 있습니다. $O(n^2)$의 시간복잡도가 소요될 것이고 n이 최대 50이므로 완전탐색으로 풀이시, 충분한 시간내에 가능합니..
[BOJ] 백준 2231 분해합 (Swift) 문제 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 풀이 이 문제는 1 ~ n 까지 하나씩 확인해보면서 n의 생성자가 될 수 있는 수를 출력해주면 됩니다. 즉, 완전탐색으로 풀이할 수 있습니다. 각 자리수의 합은 수를 Int 배열로 만들어준 후, reduce를 사용해 합을 구할 수 있습니다. n이 최대 1,000,000이고 자리수는 최대 7이므로 최악의 경우 약 7,000,000의 연산을 하게 될 것입니다. 시간 ..
[BOJ] 백준 2798 블랙잭 (Swift) 문제 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 풀이 이 문제는 완전탐색으로 풀이할 수 있습니다. 3장의 카드를 뽑는 모든 경우의 수를 확인하고, M에 최대한 가까운 카드의 합을 확인하기 위해서는 3중 중첩 for문을 사용해서 풀이할 수 있습니다. 시간복잡도는 $O(n^3)$이 될 것이고, n이 최대 100이므로 $100^3 = 1,000,000$의 연산이 소요될 것 입니다. 1초에 약 1억번 연산이 가능하..
[BOJ] 백준 18870 좌표 압축 (Swift) 문제 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이 좌표를 압축한 결과는 0 ~ 중복을 제거한 Array의 개수 - 1 까지 나타날 것입니다. 중복을 제거하는 것은 Set 메서드를 사용할 수 있습니다. Set 자료형을 사용해 중복을 제거한 후, 이것을 오름차순으로 정렬해줍니다. 이제 오름차순으로 정렬이 되어있고, 중복이 없는 Array에 요소를 Key로 갖고, index를 Value로 갖..
[BOJ] 백준 10814 나이순 정렬 (Swift) 문제 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이 Swift의 sort, sorted 메서드는 기본적으로 안정정렬 입니다. 안정정렬이란, 중복된 값이 있을 때 순서가 바뀌지 않고 동일하게 정렬이 되는 것을 의미합니다. 따라서, 나이를 기준으로 정렬을 해주면 끝입니다. 안정정렬을 직접 구현하는 방법으로는, 입력을 받을 때 순서도 같이 넣어주고 나이를 기준으로 정렬하되, 나이가 같다면 순서가 빠른 순으로 정렬을 해주는 방법으로 구현할 수 있습니..
[BOJ] 백준 1181 단어 정렬 (Swift) 문제 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 문제에 나타난 조건에 따라 정렬해주면 됩니다. 단, 중복된 단어를 제거해야 하므로 Set 자료형에 넣어준 후, 다시 Array로 만들어주는 작업이 필요합니다. 그 이후, sort 메서드의 클로저로 해당 조건을 작성해줍시다. 해당 조건은 길이가 같으면 사전순, 다르다면 짧은 것으로 정렬해주면 됩니다. sort의 클로저 구문을 { $0.count == $1.count (길이가 같..
[BOJ] 백준 11651 좌표 정렬하기 2 (Swift) 문제 https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 풀이 https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 ..
반응형

티스토리툴바