PS/백준 (329) 썸네일형 리스트형 [BOJ] 백준 9963 N-Queen (Swift) 문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 이 문제는 백트래킹 알고리즘을 사용하여 풀이할 수 있습니다. 모든 경우의 수를 확인하면 시간 복잡도는 O(nn) 일 것이고, 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에 담아주었기 때문에 위치가 아닌 값을 가지고 비교하여도 무방합니다. 모든 수를 뽑아낼 때 까.. [BOJ] 백준 10866 덱 (Swift) 문제 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Deque 자료구조를 사용해서 풀 수 있습니다. Deque 자료구조를 구현한 후, 명령에 맞게 처리해주면 됩니다. Deque 자료구조에 대해 잘 모른다면, 이 포스팅을 참고하시면 도움이 될 것입니다. https://dev-mandos.tistory.com/195 [자료구조] Deque에 대해 알아보고 구현해보기 (Swift) Deque란? Deque 자료구조는 Queue.. [BOJ] 백준 1966 프린터 큐 (Swift) 문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 풀이 Queue 자료구조를 사용하여 풀 수 있습니다. 앞에 있는 문서를 삭제연산을 하고, Queue의 요소들 중 중요도가 가장 높은 문서라면 그대로 삭제해줍니다. 삭제를 해줄 때, 몇개가 삭제되었는지 수를 세주어서 몇 번째로 삭제되었는지 확인할 수 있습니다. Queue의 요소들 중 중요도가 더 높은 문서가 있다면, Queue에 다시 삽입시킨다면 자연스럽게 맨 뒤에 위치하게 됩니다. 중요도가 가장.. [BOJ] 백준 11866 요세푸스 문제 0 (Swift) 문제 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 풀이 이 문제는 Queue를 사용해서 풀 수도 있고, index를 순회하면서 풀 수도 있습니다. Queue를 사용해서 풀이하면, K-1번 만큼 Queue에서 삭제한 요소를 Queue에 삽입시켜주고 K번째가 될 때, Queue에서 삭제연산을 해주면 K번째 요소를 제거할 수 있습니다. 이 동작을 queue가 빌 때 까지 반복해주면 됩니다. index로 접근은 어떻게 할까요? 초기값은 0번째 인덱스를 가리키고 있고, index에 k - 1을 더해준 위치의 요소를 제거해주면 됩니다... 이전 1 ··· 17 18 19 20 21 22 23 ··· 42 다음 목록 더보기
