일지 & 개발

문제 요약 알고리즘 분류: 브루트포스, 비둘기 집 원리 난이도: Silver1 문제내용: mbti N개에서 세 사람의 심리적인 거리를 구한다. 심리적거리는 각 두 사람 차이의 개수이고 A, B, C의 각 각 거리를 합한것이다. 가장 가까운 심리적 거리를 구하여 사이트 주소: https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제풀이 이번 문제는 브루트포스와 비둘기 집원리 문제이다. 비둘기 집 원리 개념은 아래 글로 확인해보면된다. https://namu.wiki/w/%EB%B9%84%EB%91%98%EA%B8%B0%20%EC%A7%91%EC..

문제 요약 알고리즘 분류: 백트래킹 난이도: Gold4 문제내용: 9 × 9 행렬 스도쿠 문제가 주어진다. 0이 빈값이다. 정답을 채워라 사이트 주소: https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 문제풀이 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다. https://jih3508.tistory.com/84 [알고리즘 이론] 백트래킹(Backtracking) 이론 이번에 볼 알고리즘은 백트래킹..

문제 요약 알고리즘 분류: 백트래킹, 조 난이도: 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..

문제 요약 알고리즘 분류: 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 탐색 알고리즘..