거의 알고리즘 일기장

https://www.algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. 어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subseque www.algospot.com O(n^2) 풀이 반복문 풀이 #include #include using namespace std; ..

https://algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요. 입력 입력의 첫 줄에는 테 algospot.com 접근 시간 : 5초, 테스트케이스 : 최대 50개, n : 최대 100 딱봐도 이 ..

https://codeforces.com/problemset/problem/189/A Problem - 189A - Codeforces codeforces.com 풀이방법 시간은 1초, n,a,b,c는 최대 4000이다. 조건은 1. piece는 무조건 a or b or c 2. 최대로 자를수 있는 값을 구하라 완전탐색으로 할시 최악의 경우 ( a,b,c가 1, n이 4000일때 ) 4000! * 3일수 있다. 그러므로 완전탐색은 탈락이고 시간을 줄일수 있는 dp를 써보자. dp[value] : value일때 최대로 자를수 있는 개수 그리고 a, b, c를 하나씩 순서대로 밑의 조건대로 넣어보자. 1. value % piece (a or b or c) == 0 일때 dp[value] = max(dp[va..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 풀이방법 완전탐색으로 푼다면 16!로 말도안되는 시간이 걸린다. 그러므로 dp를 추가해서 적절히 중복되는 연산을 저장하고 그 값을 이용함으로써 연산을 줄이는 방법이 필요하다. 예를 들어 1 2 3 4 5 6 7 1 2 3 4 5 7 6 1 2 3 4 6 5 7 1 2 3 4 6 7 ..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이방법 https://kunkunwoo.tistory.com/60 프로그래머스_가장 긴 팰린드롬 https://programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업.. kunkunwoo.tistory.com 이 문제와 유사하다. 자세한 설명은 위에 해놨으니..

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활�� www.acmicpc.net 풀이방법 냅색 알고리즘의 일종이라고 한다. (알고싶다면 밑의 블로그 참조할것) https://namnamseo.tistory.com/entry/%EB%83%85%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 냅색 알고리즘 냅색 문제는 유명한 다이나믹 문제 중 하나이다. (사진 출처 wikipedia.org) 가장 유치하지만 또 가장 많이 쓰이는 설명으로는, 한 가게..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지 www.acmicpc.net 접근 주어진 조건들을 먼저보자. 시간은 2초, MxN 행렬 (M, N [백준][1520번][DP] 내리막길 내리막길 https://ww..

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다. www.acmicpc.net 주의사항 1. 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 2. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다. 풀이방법 https://kunkunwoo.tistory.com/101 백준 11066번 _ 파일 합치기 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 주의사항 소설이므로 장이 섞이면 안된다. -> 그러므로 바로 옆에 있는것하고만 파일을 합칠수있다! 접근 총 파일이 4개라고 하면 ..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이방법 예시인 1 ,2 5원으로 10원이 나올수있는 동전의 경우의 수를 잘 생각해보자. 일단 1원만 사용했을경우 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1, 2원 사용했을 경우 1 2 3 4 5 6 7 8 9 10 1 2 2 3 3 4 4 5 5 6 1, 2, 5원 사용했을 경우 1 2 3 4 5 6 7 8 9 10 1 2 2 3 4 5 6 7 8 10 잘 보면 ..