종만북 [Algorithm] 📈가장 긴 증가하는 부분 수열 0. 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는... 백준종만북algospot동적계획법algospot [Algorithm] 🦘외발 뛰기 0. 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗... 종만북algospot동적계획법algospot [알고리즘] Intro 문제의 본질을 어떻게 생각하냐에 따라 문제를 쉽게 만들 수 있음 형태 혹은 목표가 비슷하거나 관련된 문제를 풀어봤었다면 이전과 비슷하게 접근 방법일 거라 기대할 수 있다. 하지만 해당 알고리즘을 동작 과정과 원리를 완전히 이해해야지 비슷한 문제에대해서 응용할 수 있다. 이후에 소개될 방법 중 하나인 무식하게 풀기의 방식처럼 시간과 공간 제약을 생각지 않고 문제를 해결할 가장 단순한 알고리즘을... 종만북종만북 [Algorithm] 🏠울타리 잘라내기 0. 문제 너비가 같고 높이가 다른 판자들이 붙어서 울타리를 구성하고 있을 때, 울타리에서 잘라 가장 큰 직사각형을 만들어라 입력 테스트 케이스(C) 나무 판자의 숫자 나무 판자의 각 높이 출력 가장 큰 직사각형의 넓이 1. 문제 간단 해석 붙어있는 판자에서 자를 수 있는 가장 큰 직사각형의 넓이를 구해라 2. 아이디어 💡 총 3가지 경우가 가능함 1) 반절을 잘랐을 때 왼쪽 부분에서의 직사... 종만북algospot분할정복algospot <종만북> 08. 동적계획법_비대칭 타일링 (Asymmetric Tiling) c++ 먼저 비대칭 타일링 문제를 풀기 위해서는 앞에서 공부했던 타일링 방법의 수 세는 알고리즘을 복습할 필요가 있다. 2xn 사각형을 채우는 방법들은 맨 오른 쪽이 어떻게 채워져 있느냐로 나눌 수 있다. a는 마지막 타일의 가로길이가 1인 경우, b와 c는 마지막 타일의 가로 길이가 2인 경우이다. a와 c는 본질적으로 동일 하기 때문에 tiling(n)=1xtiling(n-1) + 1xtilin... Tiling종만북algorithmalgospotdynamicprogrammingTiling [Algorithm] ♟️게임판 덮기 1. 문제 해석 흰색 판을 3칸짜리 L모양 블럭으로 덮는 경우의 수 회전 가능, 겹치기 불가능 입력 C(테스트 케이스) H(세로) W(가로) #(검은칸).(흰칸) 출력 게임판 덮는 경우의 수 2. 아이디어 💡 L모양 블럭을 회전시 4가지 모양 가능 💡 흰색과 검은색을 분리 후에, L모양 블럭으로 덮을 수 없는 곳과 있는 곳을 구분 💡 조합을 이용하여 풀이 : 재귀함수 3. 풀이 1) L모양 ... 종만북완전탐색algospotalgospot <종만북> 08. 동적계획법_합친 LIS (JLIS, Joined Longest Increasing Subsequence 문제는 정수 수열 A, B가 주어질 때 JLIS의 길이를 계산하는 프로그램이다. list()는 S(start)에서 시작하는 증가 부분 수열 중 최대 길이를 반환하는 함수이다. ret 의 값을 바꾸면 cache[a][b]의 값도 변하기 때문에 매번 귀찮게 cache[a][b]라고 쓰지 않고, 실수를 줄여주기 위해 사용한다. ret=1 로 설정하는 이유는 항상 S[start]는 있기 때문에 길이... 종만북dynamicprogrammingLISalgospotLIS <종만북> 08. 동적계획법_삼각형 위의 최대 경로 개수 세기 (Tripath Count) c++ 먼저 삼각형 위의 최대 경로 개수를 세기 위해서는 최대 경로를 푸는 알고리즘을 먼저 짜야한다. (y,x) 의 위치에서 바로 아래 숫자 혹은 오른쪽 아래 숫자로 내려갈 수 있기 때문에 (y+1, x)와 (y+1, x+1) 중에 큰 숫자를 찾아 더해서 내려가면 된다. 연산을 수행하고 나면 (b)와 같은 결과를 얻을 수 있다. 여기서 최대 경로의 개수는 9-7-3-5, 9-7-3-5, 9-7-2-... 종만북algorithmalgospotdynamicprogrammingalgorithm [Algorithm] 🕛시계 맞추기 1. 문제 해석 16개의 시계가 존재하고 모두 12시로 맞춰야함 각 시계들은 하나의 버튼에 연결되어 있어서 버튼을 한 번 누르면 3시간 후로 이동함 10번 이내에 시계 맞추기 입력 C(테스트 케이스), 16개 시계의 시간 출력 12시로 맞추기 위해 버튼을 누르는 최소 횟수 (10회 이하) 2. 아이디어 💡 한 개의 스위치는 4번 이상 누르지 않음 (다시 원상태로 복구) 💡 스위치와 연결되어 ... 종만북완전탐색algospotalgospot
[Algorithm] 📈가장 긴 증가하는 부분 수열 0. 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는... 백준종만북algospot동적계획법algospot [Algorithm] 🦘외발 뛰기 0. 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗... 종만북algospot동적계획법algospot [알고리즘] Intro 문제의 본질을 어떻게 생각하냐에 따라 문제를 쉽게 만들 수 있음 형태 혹은 목표가 비슷하거나 관련된 문제를 풀어봤었다면 이전과 비슷하게 접근 방법일 거라 기대할 수 있다. 하지만 해당 알고리즘을 동작 과정과 원리를 완전히 이해해야지 비슷한 문제에대해서 응용할 수 있다. 이후에 소개될 방법 중 하나인 무식하게 풀기의 방식처럼 시간과 공간 제약을 생각지 않고 문제를 해결할 가장 단순한 알고리즘을... 종만북종만북 [Algorithm] 🏠울타리 잘라내기 0. 문제 너비가 같고 높이가 다른 판자들이 붙어서 울타리를 구성하고 있을 때, 울타리에서 잘라 가장 큰 직사각형을 만들어라 입력 테스트 케이스(C) 나무 판자의 숫자 나무 판자의 각 높이 출력 가장 큰 직사각형의 넓이 1. 문제 간단 해석 붙어있는 판자에서 자를 수 있는 가장 큰 직사각형의 넓이를 구해라 2. 아이디어 💡 총 3가지 경우가 가능함 1) 반절을 잘랐을 때 왼쪽 부분에서의 직사... 종만북algospot분할정복algospot <종만북> 08. 동적계획법_비대칭 타일링 (Asymmetric Tiling) c++ 먼저 비대칭 타일링 문제를 풀기 위해서는 앞에서 공부했던 타일링 방법의 수 세는 알고리즘을 복습할 필요가 있다. 2xn 사각형을 채우는 방법들은 맨 오른 쪽이 어떻게 채워져 있느냐로 나눌 수 있다. a는 마지막 타일의 가로길이가 1인 경우, b와 c는 마지막 타일의 가로 길이가 2인 경우이다. a와 c는 본질적으로 동일 하기 때문에 tiling(n)=1xtiling(n-1) + 1xtilin... Tiling종만북algorithmalgospotdynamicprogrammingTiling [Algorithm] ♟️게임판 덮기 1. 문제 해석 흰색 판을 3칸짜리 L모양 블럭으로 덮는 경우의 수 회전 가능, 겹치기 불가능 입력 C(테스트 케이스) H(세로) W(가로) #(검은칸).(흰칸) 출력 게임판 덮는 경우의 수 2. 아이디어 💡 L모양 블럭을 회전시 4가지 모양 가능 💡 흰색과 검은색을 분리 후에, L모양 블럭으로 덮을 수 없는 곳과 있는 곳을 구분 💡 조합을 이용하여 풀이 : 재귀함수 3. 풀이 1) L모양 ... 종만북완전탐색algospotalgospot <종만북> 08. 동적계획법_합친 LIS (JLIS, Joined Longest Increasing Subsequence 문제는 정수 수열 A, B가 주어질 때 JLIS의 길이를 계산하는 프로그램이다. list()는 S(start)에서 시작하는 증가 부분 수열 중 최대 길이를 반환하는 함수이다. ret 의 값을 바꾸면 cache[a][b]의 값도 변하기 때문에 매번 귀찮게 cache[a][b]라고 쓰지 않고, 실수를 줄여주기 위해 사용한다. ret=1 로 설정하는 이유는 항상 S[start]는 있기 때문에 길이... 종만북dynamicprogrammingLISalgospotLIS <종만북> 08. 동적계획법_삼각형 위의 최대 경로 개수 세기 (Tripath Count) c++ 먼저 삼각형 위의 최대 경로 개수를 세기 위해서는 최대 경로를 푸는 알고리즘을 먼저 짜야한다. (y,x) 의 위치에서 바로 아래 숫자 혹은 오른쪽 아래 숫자로 내려갈 수 있기 때문에 (y+1, x)와 (y+1, x+1) 중에 큰 숫자를 찾아 더해서 내려가면 된다. 연산을 수행하고 나면 (b)와 같은 결과를 얻을 수 있다. 여기서 최대 경로의 개수는 9-7-3-5, 9-7-3-5, 9-7-2-... 종만북algorithmalgospotdynamicprogrammingalgorithm [Algorithm] 🕛시계 맞추기 1. 문제 해석 16개의 시계가 존재하고 모두 12시로 맞춰야함 각 시계들은 하나의 버튼에 연결되어 있어서 버튼을 한 번 누르면 3시간 후로 이동함 10번 이내에 시계 맞추기 입력 C(테스트 케이스), 16개 시계의 시간 출력 12시로 맞추기 위해 버튼을 누르는 최소 횟수 (10회 이하) 2. 아이디어 💡 한 개의 스위치는 4번 이상 누르지 않음 (다시 원상태로 복구) 💡 스위치와 연결되어 ... 종만북완전탐색algospotalgospot