본문 바로가기

PS

(326)

[BOJ] 백준 14889 스타트와 링크 (Swift) 문제 풀이 먼저, 스타트팀와 링크팀을 나누어 주어야 합니다. 스타트팀의 팀원들을 n / 2명을 뽑는다면, 자동으로 링크팀도 팀이 꾸려지게 됩니다. 저는 백트래킹을 사용해서 조합할 수 있는 팀을 구했습니다. 이제 팀이 나누어졌다면, 팀별로 능력치를 구해줬습니다. 1, 2, 3번이 팀이라면, $S_{12}, S_{21}, S_{13}, S_{31}, S_{23}, S_{32}$의 능력치가 팀의 능력치 일 것입니다. 반복문을 사용해서 구해주었고, 팀간의 능력치의 차이의 최소값을 구해주면 끝 입니다. 소스코드 후기 백트래킹을 사용해서 팀을 나눌 수 있었습니다. 팀을 나누었다면, 팀간의 능력치의 차이의 최소값만 구해주면 되는 문제였습니다.

[BOJ] 백준 14888 연산자 끼워넣기 (Swift) 문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 백트래킹 알고리즘을 사용해서 풀 수 있는 문제입니다. 수 사이에 연산자를 하나씩 다 넣어보고, 최대값과 최소값을 구할 수 있습니다. 연산자의 갯수를 Int 자료형의 Array로 입력을 주기 때문에, 이 Array의 Index를 사용해 어떤 연산자인지 판별하였습니다. 코드를 직접 보시면 쉽게 이해가 될 것입니다. 소스코드 후기 생각보..

[BOJ] 백준 2580 스도쿠 (Swift) 문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 스도쿠 판을 모두 채우는 문제입니다. 백트래킹 알고리즘을 사용해서 풀이할 수 있습니다. 먼저, 스도쿠 판에 0이 쓰여있는 좌표를 저장해줍시다. 이제 0이 쓰여있는 좌표에 1부터 9까지 수를 하나씩 대입해보고, 대입한 수가 가로줄, 세로줄에 쓰여있으면 안되고, 또한 3x3 정사각형에도 쓰여있으면 안됩니다. 이것을 확인해줄 함수를 작성해주었습니다. 가로줄은 y좌표에서 1부터 9까지의 x좌표..

[BOJ] 백준 9963 N-Queen (Swift) 문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 이 문제는 백트래킹 알고리즘을 사용하여 풀이할 수 있습니다. 모든 경우의 수를 확인하면 시간 복잡도는 $O(n^n)$ 일 것이고, n이 최대 15이므로 437,893,890,380,859,375 번 연산을 하겠네요.. ㄷㄷ 그래서 백트래킹을 사용하여 안되는 경우를 가지치기 해주어야합니다. n * n 체스판을 떠올리면 2차원 배열을 떠올리기 마련인데, 1차원 배열만 사용해도 무방합니다. 1차원 배열의 i..

[BOJ] 백준 15652 N과 M (4) (Swift) 문제 https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 1부터 n까지 자연수 중에서 중복없이, 비내림차순 형태의 길이가 m인 수열을 모두 출력하는 문제입니다. 또한, 이미 뽑은 수를 또 고를 수 있습니다. N과 M (2) 문제와 (3) 문제가 합쳐진 문제같네요. 선택한 숫자부터 n까지 for문을 돌면서, 수를 선택해주면 비내림차순 형태로 수열을 구할 수 있습니다. m개를 고른 경우에 함수를 return하고 고른 수들을 출력해줍시다. 소스코..

[BOJ] 백준 15651 N과 M (3) (Swift) 문제 https://dev-mandos.tistory.com/169 [BOJ] 백준 15649 N과 M (1) (Swift) 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 dev-mandos.tistory.com 풀이 1부터 n까지 자연수 중에서 중복없이 m개를 고른 수열을 모두 출력하는 문제입니다. 이미 골랐던 수를 또 골라도 되는 조건이 있습니다. 1부터 n까지 for문을 돌면서, 배열에 넣어주고 재귀함수 형태로 다시 1부터 n까지 돌도록 구현했습니다. m개 만큼 골랐다면 return 해주고 골랐던 수를 출력..

[BOJ] 백준 5430 AC (Swift) 문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 먼저, 입력에 괄호가 들어있어서 이를 제거해주어야 합니다. dropFirst, dropLast 메서드를 사용해서 괄호를 제거할 수 있습니다. 그 이후 "," 문자열을 기준으로 나누어 줍니다. 입력을 파싱해서 Array로 만들어 주었습니다. 함수는 "R"(뒤집기)과 "D"(버리기)로 두가지로 이루어져있습니다. 뒤집는 것은 revsersed 메서드, 버리는 것은 removeFirst를 사용할 수 있을 것 같은데 이 둘은 시간 복잡도가 $O(n)$..

[BOJ] 백준 1021 회전하는 큐 (Swift) 문제 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 Deque 자료구조를 사용해서 풀 수 있는 문제입니다. n이 최대 50이기 때문에, $O(n)$인 removeFirst, insert 메서드를 사용해서 구현할 수 있습니다. 편의성을 위해 1부터 n까지의 array를 담아주고, 뽑아내려고 하는 수의 위치를 입력받는데, 1부터 n까지 array에 담아주었기 때문에 위치가 아닌 값을 가지고 비교하여도 무방합니다. 모든 수를 뽑아낼 때 까..

이전 1 ··· 16 17 18 19 20 21 22 ··· 41 다음

티스토리툴바