일지 & 개발

문제 요약 알고리즘 분류: DFS, 백트래킹, Tree, Hash 난이도: Medium 문제내용: 이진 트리에서 가장 깊은 노드 합을 구하여라 사이트 주소: https://leetcode.com/problems/deepest-leaves-sum/description/ 문제풀이 이번 문제는 아래 트리 자료구조 통해서 가장 깊은 노드의 합을 구하는 것이다. 트리, 깊이 우선 탐색, 백트레킹에 관한 개념은 아래 글에서 확인 해보면된다. 트리: https://jih3508.tistory.com/87 백트레킹: https://jih3508.tistory.com/84 깊이 우선 탐색(DFS): https://jih3508.tistory.com/94 Python class TreeNode: def __init__(s..

문제 요약 알고리즘 분류: 백트레킹, DFS, 위상정렬 난이도: Medium 문제내용: 강의 수 numCourse와 prerequisites 배열을 준다. prerequisites[i]는 [a, b]가 들어 있다. b 수강 하기 위해서는 a수강을 먼저 들어아한다. 수강 들을수 있는지 참/거짓으로 반환 하여라. 사이트 주소: https://leetcode.com/problems/course-schedule/ 문제풀이 이번 문제는 깊이우선탐색, 백트레킹, 위상정렬을 활용한 문제이다. 두개에 관련 설명은 아래 글에서 확인하면 된다. 깊이우선탐색(DFS): https://jih3508.tistory.com/94 백트레킹: https://jih3508.tistory.com/84 위상 정렬: https://namu..

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

문제 요약 알고리즘 분류: 백트래킹 난이도: Silver1 문제내용: 부등호 ''와 부등호 개수가 주어진다. 각 자리 사이에 부등호를 넣어서 조건에 맞는 숫자중 최대 값과 최소 값을 구해라. 사이트 주소: https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 문제풀이 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 여기에 참조하면된다. 문제 접근 방법 이번 문제는 숫자0 ~ 9방문여부와 각 자리에 0 ~ 9 까지 뒤에 숫자랑 부등호와 비교해서 맞으면..

문제 요약 알고리즘 분류: 백트래킹 난이도: Gold5 문제내용: 서로 다른 알파벳 L과 C개의 문자를 주어진다. 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다. 정렬 되어있다. 조건에 맞는 암호들을 모두 출력해라 사이트 주소: https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제풀이 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다. https://jih3508.tist..

알고리즘 분류:백트레킹, DFS, 시물레이션 난이도: Gol4 문제내용: 세로 R, 가로 C의 알파벳 보드가 있다. (1, 1)부터 시작해서 상하좌우 이동할때 같은 알파벳 2번 지날 갈수 가 없다. 최대 이동할수 있는 횟수를 구해라. 사이트: https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제풀이 이번에는 문제는 백트레킹 또는 DFS 두가지 방법으로 풀수가 있다. 백트레킹 이나 DFS(깊이 우선 탐색)에 대한 설명은 아래 사이트에서 확..