일지 & 개발

문제 요약알고리즘 분류: Greedy난이도: Medium문제내용:tops, bottoms 같은 길이 주사위 배열을 준다.tops[i], bottoms[i]  같은 index위치끼리 바꿀수 있다.top과 bottom을 바꾸면서 top이나 bottom중에서 같은 주사위 숫자가 같게 만들수 있을때 최소 몇번 바꾸면되는지 반환 하여라 만약 안될 경우 -1로 반환 하여라사이트 주소: https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/description/문제풀이모든 경우의 수로 답은 나오지 브루드포스로 풀경우에는 시간 초과가 나올것이다. 그래서 이번문제는 그리디로 풀어야 한다. 그리디 관련 설명은 아래글을 확인 해보면된다.https://ji..

문제 요약알고리즘 분류: Hash, Ascill Code, 문자열난이도: Medium문제내용:a-z 를 0-25까지 표현한다.(ex. a = 0, b = 1, c = 3 ...... ,z = 25)문제에서 문자열 s, k정수를 준다.문자열 s에서 k만큼 자르고 자른 문자열에서 각 알파벳을 숫자로 변환하고 합친다.합친것을 숫자에서 알파벳으로 변한다. 넘어가면 26나머지 값을 알파벳을 변환한다.자른 문자열에서 처리한 것들을 합친것을 반한하여라사이트 주소: https://leetcode.com/problems/hash-divided-string/description/문제풀이 이번 문제는 문자열을 각 문자형으로 변환후 Ascill Code로 처리하는 문제이다. 문자형 Ascill Code로 변환해서 처리하는 문..

문제 요약알고리즘 분류: LinkedList, 구현난이도: Medium문제내용:0 사이에 값을 합쳐서 하나의 노드로 표현해라.사이트 주소:https://leetcode.com/problems/merge-nodes-in-between-zeros/description/문제풀이 이번 문제는 링크드리스트 노드 클래스나 구조체를 활용하는 문제이다. 노드클래스에 대한 이해도만 있으면 문제 푸는데는 어렵지 않다. 일단 아래그림처럼 처음에 나온 링크드 리스트에서 0사이 값을 합쳐서 다시 링크드리스트를 만들기만 된다. 그림을 보면 어떻게 구현 해야 할지 보일것이다. 그럼 구현은 아래처럼 하면된다.노드 새로 인스턴스 한다.다음노드가 끝있을때까지 반복문을 돌린다.현재 노드가 0이 아니면 인스턴스한 노드에 값을 더하고 다음 ..

문제 요약알고리즘 분류: 동적계획법(DP)난이도: Medium문제내용:1 ~ 365여행가는 날들 days 변수와 1, 7, 30일 기준 이용료 costs를 준다.days 날짜대로 여행 간다고 했을때 최소 비용 구하여라사이트 주소: https://leetcode.com/problems/minimum-cost-for-tickets/description/문제풀이 이번 문제는 동적계획법(DP)으로 풀어야 통과되는 문제이다.  DP에 관한 성명은 아래 글에서 확인 해보면된다.https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP)이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이..

문제 요약알고리즘 분류: Tree, BFS, BST난이도: Medium문제내용:원래 BST의 모든 키가 자신보다 큰 키들의 합과 원래 키를 더한 값으로 변경되도록 하세요.사이트 주소: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/description/ 문제풀이문제의 트리 구조는 아래와 같다. 노드의 왼쪽 서브트리는 노드의 키보다 작은 키를 가진 노드들로만 이루어져 있어야 합니다.노드의 오른쪽 서브트리는 노드의 키보다 큰 키를 가진 노드들로만 이루어져 있어야 합니다.왼쪽 및 오른쪽 서브트리 또한 이진 탐색 트리여야 합니다.이번 문제에서는 트리의 탐색하면서 더하는 식으로 진행 하면된다.트리와 DFS 관한 내용은 아래 글에서 확인 ..

문제 요약알고리즘 분류:동적계획법(DP)난이도: Medium문제내용:나이트는 체스의 이동처럼 같다나이트는 체스판이 아닌 계산기에서 이동한다.(단 *, # 이동 불가능이다.)0~9에서 아무대나 시작한다고 했을때 이동횟수가 n을 주어 졌을때 나올수 있는 경우의 수를 반환 하여라.사이트 주소: https://leetcode.com/problems/knight-dialer/description/문제풀이 이번 문제는 나이트 이동때문에 백트레킹이라고 볼수 있지만 n이 5000인점을 보면 백트레킹으로 풀면 시간 초과로인하여 완전 탐색같은 알고리즘으로는 하기는 그렇다. 그래서 최적화 할 수  있는 동적 계획법을 해야 한다. 동적계획법에 대한 설명은 아래글에서 확인해보면 된다.https://jih3508.tistory...

문제 요약알고리즘 분류: 재귀호출난이도: Medium문제내용:문자열 길이 n이 있다.문자열에는 0과 1만 올수 있다.0뒤에는 1만 올 수 있다.사이트 주소: https://leetcode.com/problems/generate-binary-strings-without-adjacent-zeros/description/문제풀이 이번 문제는 간단한 재귀호춣 구현이다. 구현은 아래와 같이 하면된다.끝에 숫자가 1일때만 0추가하고 재귀호출한다.뒤에 1을 추가하고 재귀호출한다.문자열길이가 n일때 리스트에 추가한다. 재귀호출 기본적인 문제라서 문제 푸는데는 어렵지 않다. 위에 처럼 구현 하면 시간 복잡도는 O(2^n)만큼 나온다.CodePythonclass Solution: def validStrings(sel..

문제 요약알고리즘 분류: LinkedList난이도: Medium문제내용:짝수개 n개의 LinkedList개 있다.i 번째 인덱스와 그 맞은편 n - i - 1인덱스가 쌍둥이 노드 이다.twin sum 쌍둥이 노드의 합이다.쌍둥이 노드의 합중 가장 큰것을 구하여라사이트 주소: https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/문제풀이  이번 문제는 링크드 리스트활용 하는 간단한 문제이다. 구현은 아래와 같이 하면 된다.LinkedList 순회 하면서 List저장 한다.(문제에서는 몇개 노드인지 주어지 않아서 삽입삭제 가능한 자료구조를 사용해야 한다.) 저장한 리스트에서 0 번 부터 N / 2 인덱스까지 탐색하면서 twin sum(i + n -..