YANGORITHM

문제 www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 다음과 같은 점화식을 만든다. 1. dp[i][0] = 수열에서 i번까지 선택했을 때 연속합의 최대값, 중간에 삭제를 진행하지 않음 2. dp[i][1] = 수열에서 i번까지 선택했을 때 연속합의 최대값, 이전에 삭제를 진행했다 or 현재 값을 삭제한다. n개의 수열 중에서 dp[n][0]와 dp[n][1] 까지 모두 구했을 때, 그 중에서 최대값을 찾으면 된다. 1번을 구하기 위한 점화식은 다음과 같다..

문제 www.acmicpc.net/problem/8895 8895번: 막대 배치 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. www.acmicpc.net 풀이 다음과 같은 점화식을 만든다. dp[n][l][r] = n개의 막대가 있을 때, 왼쪽에서 l개 오른쪽에서 r개 막대가 보인다. 그리고 길이 1인 막대가 왼쪽에 있을 때, 오른쪽에 있을 때, 가운데 있을 때로 나누어서 생각해 본다. 1. 길이 1인 막대가 왼쪽에 있을 때 : 이 막대가 사라졌을 때 왼쪽에서 보이는 막대가 1개 사라지므로 점화식은 다음과 같다. dp[n-1][l-1][r] 2...

문제 https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net 풀이 집합 S에 저장된 숫자들에 대해서 6개를 선택해서 만들 수 있는 조합을 출력하는 문제이다. 순열을 이용해서 조합을 구할 때는, 몇 개를 선택해서 조합을 이룰건지 알아야 한다. 이 때, 선택한 수들은 같은 숫자로 바꾸고 그 외 숫자들도 같은 수로 바꿔서 순열을 구하면 조합을 구할 수 있다. 예를 들어, 1 2 3 4 에서 3개를 선택해서 조합을 이루는 수를 구한다고 하면..

문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 풀이 모든 도시를 방문하고, 도시의 방문 순서를 다르게 하는 문제이다. 도시의 수는 최대 10개이다. 그러므로 가능한 방문 순서의 수는 10! 이 되고, 이를 순열을 이용해 나타낸다. d 배열을 이용해 도시를 저장하고, next_permutation() 함수를 이용해 d..

문제 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 www.acmicpc.net 풀이 그래프 탐색과 이분 탐색을 이용해서 해결하는 문제이다. 이분 탐색을 통해 중량 값을 찾고, 그래프 탐색을 통해 해당 중량 값으로..

문제 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마 www.acmicpc.net 풀이 주사위의 6면을 상하좌우앞뒤로 구분을 해서 생각한다. dice[6]에서 0:상, 1:뒤, 2:우, 3:좌, 4:앞, ..

문제 https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 풀이 수열의 왼쪽에 있는 수가 오른쪽에 있는 수보다 몇 개가 더 큰지 알아내면 된다. 그 수 만큼 버블 정렬에서 swap이 일어나기 때문이다. 수열 1 3 5 2 4 의 경우 3은 2보다 크고, 5는 2와 4보다 크므로 버블 정렬에서 swap이 총 세번 일어난다. 병합 정렬을 이용해 왼쪽에 있는 수가 오른쪽에 있는 수보다 몇 개가 더 큰지 구할 수 있다. R 배열의 값을 새로운 정렬..

문제 https://www.acmicpc.net/problem/13335 13335번: 트럭 문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최 www.acmicpc.net 풀이 다리를 큐로 생각을 하고 트럭이 다리에 올라가는 것을 큐에 값을 넣는 것으로 생각을 한다. 큐에 넣을 수 있는 최대 수는 w가..

문제 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. www.acmicpc.net 풀이 2차원 배열을 이용해 '*' 과 ' ' 정보를 저장을 하고 출력을 했다. 3*3 에서 9개를 기준으로 다음과 같이 재귀문을 ..

문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 풀이 문제에 나와있는 조건을 순서대로 구현하면 되는 문제이다. 청소할 공간이 있으면 이동하고 이동한 장소에서 다시 청소할 공..