일지 & 개발

문제 요약 알고리즘 분류: 백트래킹, 조 난이도: Silver2 문제내용: 부분수열중 합해서 합이 S인 개수를 구하여라 사이트 주소: https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제풀이 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다. https://jih3508.tistory.com/84 [알고리즘 이론] 백트래킹(Backtracking) 이론 이번에 볼 알고리..

문제 요약 알고리즘 분류: 백트래킹, 순열 난이도: Silver2 문제내용: 정수의 순서를 바꿔서 아래 같은 식의 최댓값을 구하여라 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 사이트 주소: https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제풀이 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다. https://jih3508.tistory.com/84 [알고리즘 ..

문제 요약 알고리즘 분류: dp 난이도: Gold5 문제내용: 두 문자열에서 가장 긴 수열 길이를 구하여라 사이트: https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제풀이 이번 문제에는 동적계획법 알고리즘 대표적인 문제인 LCS이다. LCS에 대한 개념은 아래 사이트에서 확인해보면 된다. https://jih3508.tistory.com/191 [알고리즘 이론] LCS(Longest Increasi..

이론 1. LCS이란? LCS 개념을 이해하기 전에 기본적으로 DP(동적 계획법)또는 이분탐색을 알아야 된다. DP 에 관련 내용은 아래 사이트에 참조하면된다. https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP) 이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘이다. 동적계획법 알 jih3508.tistory.com LCS는 2개의 문자열에서 비교해서 공통으로 길이가 가장 큰 열을 말한다. 예시로 ABCDEFG와 BDFGEH에서 가장 길이가 긴 수열은 BDFG가 될 수가 있다. 두 개의 문자열..

문제 요약 알고리즘 분류: dp 난이도: Silver5 문제내용: 피자 높이가 A일 때 B, C로 분리하면 B*C 만큼 즐거움이 있다. B, C에서 분리해서 추가로 즐거움을 더 할 수 있다. 피자 높이 N으로 주어 질때 최대 총합 즐거움을 구하여라\ 사이트: https://www.acmicpc.net/problem/14606 14606번: 피자 (Small) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net 문제풀이 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그..

문제 요약 알고리즘 분류: dp 난이도: Silver3 문제내용: 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 사이트: https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제풀이 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 10^N개 탐색 하면 시간 초과로 나올 것이다. 그래서 이번 문제는 DP로 풀어야 통과 되는 문제이다. DP랑 관련된것은 ..

문제 요약 알고리즘 분류: bfs, 구현, 시물레이션 난이도: Silver2 문제내용: 가로, 세로 크기가 n, m인 캠퍼스 공간이 있다. 그림영역과 빈 영역이 있는데 그림 영역 개수와 가장 큰 그림을 출력해라. 사이트: https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 문제풀이 이번 문제는 DFS,BFS 탐색 문제이다. DFS로 풀수있지만 BFS가 DFS보다 속도가 더 빨라서 이번 문제는 BFS로 푸는게 좋다. BFS 탐색 알고리즘..

문제 요약 알고리즘 분류: bfs, 구현, 시물레이션 난이도:Silver1 문제내용: 가로, 세로 크기가 n, m인 지도가 있다 2는 시작점 1은 갈수 있는 길, 0은 갈수 없는 곳 시작점 부터 각 지점 목적지를 출력해라 그리고 목적지 도달 하지 못하는 곳은 -1로 출력해라 사이트: https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제풀이 이번 문제는 BFS 탐색 문제이다. BFS 탐색 알고리즘에 관..