코딩 공부소

https://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 이 문제는 dp를 이용한 문제입니다. 풀이법 이 문제는 전단계의 값들과 자신의 값을 더한 것중 최댓값과 최솟값을 찾으며 비교하는 문제입니다. 푸는 방법은 다음과 같습니다. 1.1번쨰 자리에서 시작할 경우 전단계의 1번째자리와 2번째자리의 값중 최댓값과 최솟값을 찾는다 2.2번째 자리에서 시작할 경우 전단계의 1번째 자리와 2번째 자리, 그리고 3번째 자리중 최댓값 최솟값을 찾는다. 3. 3번째 자리에서 시작할 ..

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이 문제는 이진 탐색을 이용한 문제입니다 풀이법 이진 탐색을 이용하는 방법은 다음과 같습니다 1. 무조건 가능한 수 중에 최소값 start 변수로 지정 2. 가능 여부를 떠나 , 현재 최대값을 end 변수로 지정 3.중간 값mid 를 찾은 다음 그 중간값에 따라 값을 바꿨을 때, 조건에 맞는 지 확인 4.조건에 맞는다면 이 중간값을 start 변수에 대입, 아니면 end 변수에 대입합니다 5..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 그래프 탐색을 이용해서 푸는 문제입니다. 해결법 m*n 크기의 밭에 있는 배추들이 인접해있으면 인접해있는 배추들의 수와 관계없이 하나의 지렁이만 있으면 되는 내용입니다. 한마디로, 인접해있는 노드들의 집합 개수만 세면 되는 문제죠. 그러기 떄문에 해결법은 1. 이중 for문을 통해 값이 1인 밭을 찾는다. 2. 찾았다면, y방향으로 -1, 1, x방향으로 -1 1를 각각 이동하면서 값이 1인 밭을 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 그래프를 이용해서 푸는 문제입니다. 풀이법 문제를 보면 1번 컴퓨터와 연결되있는 컴퓨터들은 모두 바이러스에 걸리므로, 1번 컴퓨터와 연결되있는 2 5 그리고 그 두 컴퓨터와 이어져있는 3 6까지 총 4개의 컴퓨터들은 바이러스에 걸리고, 4 7 컴퓨터만 무사한것으로 볼 수 있습니다. 따라서 해결법은 1. 입력 간선을 모두 정점 노트의 다음 노드에 저장한다.( 예 1-2를 정점이 1인 노드의 다음 노드 값..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 백트래킹을 이용하는 문제로 실버 3문제입니다 해결책 문제는 간단합니다. 만약 n이 3이고 m이 2가 됬다면 2자리 수열로 모든 가능한 수를 만드는것입니다 .그러면 수열은 (1,1),(1,2)......(3,3)까지 나오게 되는거죠. 이를 이용하면 다음과 같습니다 1. 해당 노드의 자리에 노드를 놓으면, 다음엔 자리수를 줄여서 재귀함수를 호출한다. 예를 들어 n이 3이고 m이 2라고 했..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 백트래킹 알고리즘의 대표적인 문제 중 하나로, 골드 4 문제입니다. 해결책 이 문제를 해결하기 위해 백트래킹의 개념을 알아야합니다. 백트래킹은 기존 끝까지 탐사하는 DFS와 달리 만약 탐색하고 있는 값이, 옳지 않다 생각하면, 바로 전 노드 단계로 돌아가버려 그 다음 단계를 수행합니다. 그럼으로써 효율적이게 탐색을 할 수 있는것입니다. 위 그림을 보시면, 백트래킹에 대해 잘 나타내고 있습니다. 일단 해..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제는 실버 3으로 동적 계획을 사용하는 문제입니다. 풀이 이 문제는 LIS라는 유명한 문제입니다. 왜 동적 배열을 이용하는지, 살펴 봅시다 i 0 1 2 3 4 5 6 A 0 10 20 10 30 20 50 DP 0 이런 표가 있다고 해봅시다 보기 쉽게 i=0일때 경우를 추가해봤습니다. LIS 문제를 푸는 키워드는..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 실버 3이며, 동적할당을 이용해서 푸는 문제입니다 풀이 만약 n이 주어진다면 저 n을 1,2,3의 합으로 나타내는 경우를 모두 구해 주면 됩니다. 처음 생각해보면 꽤 시간이 많이 걸릴것 같지만 푸는 방법만 알면 어렵지 않습니다 동적 계획은 이전에 저장 되어있는 값을 이용해 누적해서 계산해주는 방법입니다. 때문에, 만약 n이 1..3.까지 라고 했을때, dp[1] =1, dp[2]=2, dp[3]= 4입니다. dp[0]은 0으로 둡시다. 0원을 만드는 경우의 수는 없으니까요 그러면 만약 n=4일때..