본문 바로가기
[C/C++] BOJ 11055 :: 가장 큰 증가 부분 수열 BOJ 11055 :: 가장 큰 증가 부분 수열 문제 링크 : https://www.acmicpc.net/problem/11055 나의 풀이 1. 가장 큰 증가 부분 수열을 저장할 1차원 배열을 생성한다. 2. 기준 idx를 두고 그 앞 범위를 탐색하며 증가 부분 수열일 될 때, 그 합을 갱신한다. 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_11055/BOJ_11055.cpp 1234567891011121314151617181920212223242526272829303132333435// 백준알고리즘 11055번 :: 가장 큰 증가 부분 수열#includeusing namespace..
[C/C++] BOJ 11722 :: 가장 긴 감소하는 부분 수열 BOJ 11722 :: 가장 긴 감소하는 부분 수열 문제 링크 : https://www.acmicpc.net/problem/11722 나의 풀이 1. 가장 긴 감소하는 길이를 저장할 lds 배열을 만든다. 2. 기준 idx까지 앞 쪽의 원소들을 탐색하면서 감소하는 부분 수열이 될 경우, 기준 idx의 lds를 갱신한다. 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_11722/BOJ_11722.cpp 123456789101112131415161718192021222324252627282930313233// 백준알고리즘 11722번 :: 가장 긴 감소하는 부분 수열#includeusing..
[SW 문제해결 응용] LIS :: 최장 부분 증가 수열 LIS(Longest Increasing Subsequence) 최장 부분 증가 수열 구하는 문제 : 어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 문제 부분 수열에 포함되는 요소들이 순서상 연속적일 필요는 없음 문제 풀이를 위한 방법으로 3가지가 있다. 1. 완전 탐색2. 다이나믹 프로그래밍3. 이분 탐색 완전탐색, O(2^N) 완전 검색 적용 1. 수열의 모든 부분 집합을 구하여 각 부분 집합이 증가 수열이 되는지 판별 2. 증가 수열이 되는 수열 중 가장 길이가 긴 수열을 찾음 ex)S = {3, 2, 6, 4, 5, 1} 2^6 = 64개의 부분집합 길이가, 0일 때, {}1일 때, {3}, {2}, {6}, {4..
[C/C++] BOJ 11053 :: 가장 긴 증가하는 부분 수열 BOJ 11053 :: 가장 긴 증가하는 부분 수열 문제 링크 : https://www.acmicpc.net/problem/11053 나는 아직 for문 여러 개를 사용해서 다이나믹 프로그래밍 하는 것에 서툰 것 같다!! 옛날에 살짝 공부했던 적이 있는 LIS 기초 부분인데도 제대로 풀지 못했다 ㅠㅠ.. 알고리즘에 대한 공부를 명확히 하고 문제를 다시 풀어봐야 겠다!! 나의 풀이 1. 배열의 기준점을 두번째 index에서 가장 긴 곳까지 두면서 비교한다. 2. 배열의 0번에서 기준점까지 점진적으로 비교하면서 증가하는 수열이 될 때에 dp배열을 갱신시킨다. 3. 모든 dp배열을 채운 후, 그 중 가장 큰 값을 찾아 출력한다. 나의 코드 Github : https://github.com/j2wooooo/Da..
[C/C++] BOJ 1932 :: 정수 삼각형 BOJ 1932 :: 정수 삼각형 문제 링크 : https://www.acmicpc.net/problem/1932 나의 풀이 1. 정수삼각형의 값을 2차원 배열에 저장한다. 2. 각 층마다 최댓값을 저장한다.삼각형의 가장 왼쪽 값은 바로 윗층의 같은 열의 값 + 현재 값을 저장한다.삼각형의 가장 오른쪽 값은 바로 윗층의 현재 열 - 1 의 값 + 현재 값을 저장한다.나머지 값은 그 둘 중 최댓값 + 현재 값을 저장한다. if (j == 0) arr[i][j] += arr[i-1][j]; else if (j == i) arr[i][j] += arr[i - 1][j - 1]; else arr[i][j] += max(arr[i - 1][j], arr[i - 1][j - 1]); 3. 마지막 층 중에서 최댓값을..
[C/C++] BOJ 2163 :: 초콜릿 자르기 BOJ 2163 :: 초콜릿 자르기 문제 링크 : https://www.acmicpc.net/problem/2163 규칙이 매우 간단하여 O(N)이 아닌 O(1)로 풀 수 있는 문제! 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_2163/BOJ_2163.cpp 12345678910111213// 백준알고리즘 2163번 :: 초콜릿 자르기 #includeusing namespace std; int N, M, ans;int main(void){ cin >> N >> M; ans = N*M - 1; cout
[C/C++] BOJ 11052 :: 카드 구매하기 BOJ 11052 :: 카드 구매하기 문제 링크 : https://www.acmicpc.net/problem/11052 나의 풀이 학부 고급알고리즘 시간 때 배운 Knapsack 알고리즘을 생각하며 풀었다! 1. 카드 1개를 갖기 위해 지불해야 하는 금액의 최댓값은 카드 1개가 포함된 카드팩의 가격이므로 그 값을 그대로 저장한다. 2. 카드 2개부터는 지금까지 저장한 카드를 갖기위해 지불해야 하는 금액의 최댓값과 카드팩의 가격을 이용하여 비교한 후 갱신한다. Ex) 카드 2개를 갖기 위해 지불해야 하는 금액의 최댓값은 1) 카드 0개를 갖기 위해 지불해야 하는 금액의 최댓값 + 카드 2개가 포함된 카드팩의 가격 = 5현재 저장되는 최댓값은 52) 카드 1개를 갖기 위해 지불해야 하는 금액의 최댓값 + 카..
[C/C++] BOJ 2306 :: 유전자 BOJ 2306 :: 유전자 문제 링크 : https://www.acmicpc.net/problem/2306 처음에는 다이나믹 프로그래밍이니까 무조건 하나의 반복문 루프 안에서 끝내야 한다는 생각에 사로잡혀 한 번의 루프로 끝낼 수 있는 규칙을 찾지 못해 난관에 빠졌었다, 생각을 바로잡고 문제에 나와있는 규칙을 적용하여 재시도한 결과, 얼추 규칙에 맞는 프로그래밍을 할 수 있었다. 그러나 계속 틀렸습니다. 가 떠서 백준 슬랙을 통해 문의한 결과 ㅠㅠ 간과한 점을 알 수 있었다. 나는 2번 조건과 3번 조건을 각각의 반복문으로 진행시켜 주었는데 그러면 atat와 같은 KOI 유전자의 길이를 제대로 도출해낼 수 없었다. 따라서 같은 루프 안에서 2번 조건과 3번 조건을 함께 판단하는 것으로 코드를 변경함으로..

티스토리툴바