일지 & 개발

문제 요약알고리즘 분류:동적계획법(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 -..

문제 요약알고리즘 분류: 배열, 그리디난이도: Medium문제내용:가로, 세로 같은 크기 2차원 배열을 준다.각 배열 건물 높이 크기 값을 준다.동, 서, 남, 북으로 봤을때 스카이라인기준으로 건물 높이 올리라고한다.도시의 스카이라인을 변경하지 않고 건물 높이의 합계를 최대로 증가 시킬 수 있는 값을 반환 하여라사이트 주소: https://leetcode.com/problems/minimum-number-of-operations-to-make-word-k-periodic/description/문제풀이  이번 문제는 그리디 활용 하는 문제다 그리디 관련 내용은 아래 글을 확인 하면 된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알고리즘은 탐욕..

문제 요약알고리즘 분류: 문자열, 해쉬난이도: Medium문제내용:문자열 word와 k 정수가 준다.word k길이로 나눈것을 a,b,c, a ... 라고 하면 나눈것을 a, ,a , a...로 같은 반복된 문자열로 할라면 최소 몇개만 바꾸면 될지 반환 하여라사이트 주소: https://leetcode.com/problems/minimum-number-of-operations-to-make-word-k-periodic/description/문제풀이  이번 문제는 k길이 등분해서 abc패턴을 aaa로 만드는데 최소 몇번 해야 하는지만 알면 되는 문제이다. 각 k길이 만큼 나눠서 모든 경우의 수를 구하도 되지만 간단 하게 생각하면 각 문자열 자른 것을 몇번  반복된것을 구해서 전체개수에서 가장 많은것을 빼면..

문제 요약알고리즘 분류: 구현난이도: Medium문제내용:문자형으로 스토쿠 배열을 준다. '.'은 비어 있는 공간이다.스도쿠를 보고 유효한 스도쿠인지 반환하여라.사이트 주소: https://leetcode.com/problems/valid-sudoku/description/문제풀이  이번 문제는 스도쿠 빈칸을 채우는 문제가 아니라 스도쿠판을 주고 이 판이 유효한지만 체크 하면된다. 그럼 구현 할것은 크게 2개라고 보면된다.가로, 세로 중복된 숫자 여부3 × 3 Box 안에 중복된 숫자 여부 숫자 일때 아래 2개를 확인 하면 된다.1. 가로, 세로 중복된 숫자 여부  자기 위치 빼고 가로 세로 중복된 숫자 있는지 확인하면 된다. Pythondef isCross(x, y, num): for i in r..

문제 요약알고리즘 분류: 배열, 정렬난이도: Medium문제내용:배열 nums가 주어진다. num1과 num2를 나눠서 num1 최대값과 num2 최소값의 절대값을 구한다.위 사항에서 num1과 num2 분할하고 난뒤 결과값중 최소값을 구하여라사이트 주소: https://leetcode.com/problems/find-the-value-of-the-partition/description/문제풀이  이번 문제는 num1, num2 나눈다고 생각 하면 나눈것에서 모든 경우의 수를 구해야 하기 때문에 구현하는데 더 복잡할수가 있다. 그냥 두 수에서 차이중에서 최소값을 구하는데만 신경쓰면 문제 풀수 있다. 예를 들어 1번 예제에서 1, 3, 2 ,4 를 보면 예시에서는 [1, 3] , [2, 4] 에서 | 1-..

문제 요약알고리즘 분류: 그리디난이도: Medium문제내용:2차원 배열 points, points[i] = [xi, yi] 와 정수 w가 주어진다. w는 사각형 가로 길이이다.사각형의 범위가 (x`, 0) , (x` + w, 0), (x`, y`), (x` + 2, y`)로 이루어 진게 몇개가 있습니다.각 points 사각형안에 포함이 되어 있습니다. 모든 점이 사각형 안에 포함 될때 최소 몇 개 사형이 필요한지 반환 하세요.사이트 주소: https://leetcode.com/problems/minimum-rectangles-to-cover-points/description/문제풀이  이번 문제는 모든 경우의 수로 구하면 시간초과가 날것이다. 그래서 최적의 시간내로 풀수 있는 그리디로 풀어야 통과가 되는..