일지 & 개발

문제 요약알고리즘 분류: 수학난이도: Medium문제내용:pref이라는 리스트가 주어진다.pref[i] = arr[0] ^ arr[1] ^ arr[2] ...... ^ arr[i]  식처러  arr 0번째 인덱스 부터 i번째 xor연산된 값이다.xor 연산되기 전의 arr를 구하여라사이트 주소: https://leetcode.com/problems/find-the-original-array-of-prefix-xor/description/문제풀이  이번 문제는 xor의 법칙만 알면 쉽게 풀수 있는 문제이다.위 내용 보면 pref[i] = arr[0] ^ arr[1] ^ arr[2] ...... ^ arr[i]으로 되어 있으면 pref[0] = arr[0]으로 0번째 인덱스는 그대로 넣으면 된다. 그럼 첫번..

문제 요약알고리즘 분류: DP난이도: Medium문제내용:가로, 세로 안에 0 과 1로 채워져 있다. 0은 빈곳 1은 면적이 있는 공간이다.정사각형 최대 넓이를 구하여라사이트 주소: https://leetcode.com/problems/maximal-square/description/문제풀이  이번 문제는 간단한 DP(동적계획법) 문제이다. DP에 대한 자세한 설명은 아래글에서 확인 해보면 된다.https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP)이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘..

문제 요약 알고리즘 분류: 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 문제내용: n까지 숫자를 사전순으로 정렬 하여라. 사이트 주소: https://leetcode.com/problems/lexicographical-numbers/description/ 문제풀이 이번 문제는 숫자를 사전 순으로 정렬 하는것이다. 1, 2, 3 순이 아니라 1, 10, 100순으로 앞자리가 낮은 순으로 정렬 하는것이다. 이 문제는 깊이 우선 탐색, 백트레킹으로 해결하면된다. 깊이 우선 탐색, 백트레킹 자세한것은 아래 글에서 확인 해보면 된다. 백트레킹: https://jih3508.tistory.com/84 깊이 우선 탐색: https://jih3508.tistory.com/94 [알고리즘 이론] 깊이 우선 탐색(DFS) 이론..

문제 요약 알고리즘 분류: 동적계획법(DP) 난이도: Medium 문제내용: 숫자로된 문자열 S가 주어진다. 1~26을 A ~ Z로 디코딩 가능하다. 문자열에서 조합 가능한 가지수를 출력해라. 단 01 ~ 09은 안된다. 사이트 주소: https://leetcode.com/problems/decode-ways/description/ 문제풀이 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하기에는 시간이 많이 걸려서 시간이 최적화 되도록 풀어야한다. 그래서 이번문제는 DP로 해결할것이다. DP관련 자세한 설명은 아래 글로 확인 해보면된다. https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP) 이론 이번에..

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

문제 요약 알고리즘 분류: 그리디, 수학 난이도: Medium 문제내용: 각 자리수는 0과 1만 올수 있다. 숫자 N을 주어 줬을때 0, 1만 오는10진수 조합된 숫자로 최소 몇번 더하면 되는지 구하여라. 사이트 주소: https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/description/ 문제풀이 이번 문제에는 그리디 문제이다. 그리디 관련 자세한 내용은 아래 글에서 참고 하면된다. https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy) 이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알고리즘이다. 이 ..

문제 요약 알고리즘 분류: 시뮬레이션, 이분탐색, 그래프탐색(DFS, BFS) 난이도: Medium 문제내용: heights[row][col]는 셀 (row, col)의 높이를 나타낸다. (0, 0) → (row, col)까지 도착해야 한다. 상하좌우로 이동 할때 최대 이동할수있는 높이 차이만큼 이동할 수 있다. 최소한 최대 이동할 수 있는 높이 차이만큼 구하여라 사이트 주소: https://leetcode.com/problems/path-with-minimum-effort/description/ 문제풀이 이번 문제에는 그래프 탐색과 이분탐색을 활용한 문제이다. 관련 내용은 밑에 글에서 확인 해보면 된다. 이분 탐색: https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%..