본문 바로가기

Swift

(356)

[BOJ] 백준 9184 신나는 함수 실행 (Swift) 문제 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 풀이 DP를 사용하여 풀 수 있는 문제입니다. DP는 점화식만 세운다면 쉽게 풀 수 있습니다. 이 문제에서는 점화식을 아예 주고 시작해서, 점화식에 맞게 코드를 작성해줍시다. 먼저, 저는 20 * 20 * 20의 3차원 배열을 선언해주었고, 초기값을 1로 갖고 있도록 하였습니다. 이제 이 3차원 배열을 점화식에 맞게 채워주었습니다. 바텀업 방식으로 풀이할 때는 입력을 받을 때, 0 보다 작거나 ..

[BOJ] 백준 24416 알고리즘 수업 - 피보나치 수 1 (Swift) 문제 https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 풀이 단순히 문제만 보았을 때, 의사코드를 작성해서 직접 count를 해주는 것을 떠올릴 수 있습니다. 하지만, 재귀호출로 fib(40)을 호출한다면 어마어마하게 재귀호출을 하기 때문에 시간초과가 날 것입니다. 어떻게 코드1 횟수를 구할 수 있을까요? 단순히 생각해봅시다. fibo(3)을 구하려면 fibo(2), fibo(1)이 필요합니다. 그렇다면 코드 1을 2번 호출을 하겠..

[BOJ] 백준 1449 수리공 항승 (Swift) 문제 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 풀이 그리디 알고리즘으로 풀이할 수 있습니다. 파이프의 길이는 최대 1000이므로, 1부터 1000까지 확인하면서 물이 세는 곳이라면, 길이가 L인 테이프를 붙여주어야 합니다. 그렇다면 물이 세는곳 + L 까지는 모두 테이프로 막아져있기 때문에, 물이 세는곳 + L부터 1000까지 다시 물이 세는곳을 확인해주고, 테이프의 수를 하나 늘려줍시다. 최대 1000까지 확인하였다면,..

[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하고 고른 수들을 출력해줍시다. 소스코..

이전 1 ··· 17 18 19 20 21 22 23 ··· 45 다음

티스토리툴바