백준문제풀이
[백준 2302] 극장 좌석 C++
www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 극장 좌석의 문제는 다이나믹 프로그래밍 문제로, 수열의 규칙을 찾아보면, 피보나치 수열임을 알 수 있습니다. 그 원리를 이용해서 해당 구간의 경우의 수를 곱해주는 문제입니다. 문제에서 VIP좌석이 있지만, 일단 우리는 VIP좌석을 빼고 규칙성을 찾아봅시다. VIP좌석을 빼고 규칙을 찾으면 1부터 N까지의 가능한 경우의 수는 1번째 = 1 2번째 = 2 3번째 = 3 4번째 = 5 5번째 = 8 6번째 = 13 7번째 = 2..
[백준 2096] 내려가기 C++
www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 이번 문제는 다이나믹 프로그래밍 문제로, 기존의 다이나믹 문제 유형과 비슷하지만, 메모리를 효율적으로 구성해야하는 문제입니다. 메모리를 효율적으로 사용하기 전에, 기존의 간단한 방법으로 문제를 풀면 배열을 arr[n][3] 배열에서 이전의 위치에서 arr[n][0~3]에 더 해질 수 있는 칸들(arr[n-1][0~3] 중에서 최댓값을 구해서 arr[n][0~3]에 더해주면 됩니다. 문제에서는 별 가능 가능 불가능 이렇게 나와..
[백준 1707] 이분 그래프 C++
www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 이 문제는 두 개의 정점이 주어졌을 때, 두개의 정점은 인접하지 못하도록 표시 후, 이분 그래프가 맞는지 판별하는 문제입니다. BFS, DFS 둘 중 아무거나 사용하면 됩니다. 이분 그래프 알고리즘의 핵심은, 두 개의 정점이 인접하지 못하도록, 2 가지 색깔로 칠해주는 것입니다. 처음 노드를 선택했을 때 1, 1로 칠해진 노드안에 있는 다음 노드를 선택 했을 때 2, 그리고 2노드안에 있는 다음..
[백준 11660] 구간 합 구하기 5 C++
www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 다이나믹 프로그래밍 알고리즘을 사용해서 푸는 문제입니다. map의 전체 사이즈는 최대 1024x1024이고, 연산을 최대 100,000번 해야하기 때문에, 브루트포스로 풀게되면 당연히 시간초과가 나올 수 밖에 없습니다. 시간초과가 나오지 않으려면, DP를 사용해서 각 인덱스별로 누적합을 저장하면 되겠습니다. dp[i][j]는 i, j까지 누적합을 말합니다. 입력을 받을..
[백준 2178] 미로 탐색 Swift
www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번 문제는 단순한 BFS, DFS탐색 문제입니다. 기본 문제이지만, Swift 언어 활용을 위해 풀어보려고 합니다. 최소 거리는 BFS탐색을 이용해서 자주 풀기 때문에 BFS코드로 풀었습니다. map함수는 갈 수 있는 곳 1과 갈 수 없는 곳 0으로 입력으로 받았고요. check함수는 방문했는지 여부, distance는 최소거리를 구하기 위해 사용했습니다. 주의 해야할 점은 입력값의 map이 숫자가 붙어서 나오는데, Swift는 readLi..
[백준 11724] 연결 요소의 개수 C++
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 이번 시간은 그래프의 기본인 연결 요소의 개수를 구하는 문제의 풀이법을 설명하겠습니다. 문제에서 조건은 방향이 없는 그래프라고 말하고 있습니다. 입력으로 정점의 개수 N과 간선의 개수 M을 입력받고요, 연결된 요소가 총 몇개 있는지 구하는 문제입니다. 이 문제는 DFS, BFS로 어느것으로 풀어도 되지만, 저는 DFS를 이용해서 깊..