본문 바로가기

프로그래밍/알고리즘

 (7)
동적 프로그래밍 - 예제 1번째 문제 https://leetcode.com/problems/unique-morse-code-words/ 알파벳에 해당되는 모스 부호가 있고, 특정 단어가 인풋으로 들어오면 해당 단어를 모스부호로 변경을 한 후 , 중복되지 않은 문자가 몇개인지 return 시키는 문제다. public int uniqueMorseRepresentations(String[] words) { List morse = List.of(".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."); Lis..
동적 프로그래밍 동적 프로그래밍 이란? DP는 문제에 대한 모든 경우의 수를 효율적으로 탐색하는 프로그래밍 패러다임. 1. 문제를 원래 문제의 더 작은 중첩 하위 문제로 나눈다. 2. 중첩 하위 구조에서 최적 솔루션이 형성될수있다. (작은 단위에서 문제를 해결할 솔루션 찾는걸 말하는듯?) 이 두가지 특성을 좀 더 자세히 봐보자. 피보나치 수열 - DP 를 설명하는 고전적인 예다. 앞의 두 수를 더하면 다음 수열이 나오는구조. 피보나치 수 f(n) 이 있다면 작은 하위 문제로 나눌수 있다. f(n-1) , f(n-2) 그럼 f(n-1) , f(n-2) 이 하위 문제에서 솔루션을 찾고 f(n-1) + f(n-2) 로 f(n) 을 구할수있다. 핵심은 작은 단위로 잘라서 거기서 해결책을 찾자 DP 알고리즘 구현 방법 1. bo..
[비트 연산] leetCode - 461. Hamming Distance 문제 설명: int 값 2개가 주어졌을때 두 값을 비트 단위로 변경 한 후 각 자리가 다른 자리의 갯수를 세는 문제 문제 풀이 : 먼저 비트 연산에 대해서 알아보자 & : 각 자리의 비트가 모두 1 인 경우 1 , 아닌 경우 0 | : 두 비트 중 1개라도 1이면 1 ^ : 두개가 서로 다르면 1, 아니면 0 a >> i : a 의 모든 비트를 오른쪽으로 i칸 밀고 맨 왼쪽을 0으로 채움 a > 로 i 만큼 이동시켜본 후 그 값을 & 1 로 해본다 & 1 을 했을때 그 자리값이 1일때나 1이 나오므로 각 자리가 다른 개수를 셀 수 있다. 풀이 코드 : https://github.com/kwonhyucknae/algorithm_study/blob/master/src/com/leetCode/problem/H..
[이진검색트리] leetCode - 530. Minimum Absolute Difference in BST 이진 검색트리 leetCode - 530. Minimum Absolute Difference in BST 문제 설명: 이진 검색 트리에서 각 노드의 데이터 중 절대값의 차이가 가장 작은 값을 구해라 문제 풀이 : 이진 검색트리 서치 종류 가 3가지가 있다. preOrder : preOrder 에서는 root left right 이런식으로 검색을 하고 inOrder : inOrder 에서는 left root right 이런식 postOrder : postOrder 에서는 left right root 이렇게 검색을 한다. 근데, 이때 이진 검색트리의 특징이 inOrder 를 하면 오름차순이 된다는것 이걸 이용해서 풀어준다. 코드를 보면 클래스 변수로 이전 노드의 데이터를 저장하고 이전 노드와의 차이 값을 M..
[백트래킹] leetCode - Generate Parentheses 백트래킹 재귀(recursion) 과 거의 동일하게 풀었다. 재귀와 거의 다를게 없다고 생각. 먼저 문제를 봐보자 문제 요약 - 먼저 int n 이 주어지고, () 괄호의 정합성이 항상 맞으면서 n 만큼의 () 이 나오는 모든 경우를 표현하는 문제 문제 풀이 - 괄호 '(' 부분과 ')' 부분을 재귀 호출을 하고 , 호출을 끝낼 수 있게 termination check 를 해준다. 코드에서 (open < n && close < n) 이 termination check 를 해준 부분이고, 먼저 괄호 ( 가 n 번 만큼 나오게 재귀 호출을 해준후 다시 ( 가 나온 만큼 ')' 가 호출 되도록 재귀 호출을 해준다. 이렇게 하면 open 이 n 번 만큼 close가 n 번만큼 나오는 모든 경우의 수를 볼 수 있..
leetCode - daily coding 오늘의 leetCode 알고리즘 풀어본 문제를 봐보자 5. Longest Palindromic Substring 먼저 가장 긴 펠린드롬 문제 문제 요약 - 주어진 스트링에서 뒤집어도 똑같은 문자 - 펠린드롬 문자 중 가장 긴 문자를 찾아서 return 시키는 문제다 문제 풀이 - 이 문제는 다이나믹 프로그래밍으로 풀었다. 생각을 어떻게 해야하냐면 , 일단 펠린드롬을 찾기위해서는 2중 for문을 돌아야하는데, 첫번째 기준 문자와 두번째 기준 문자가 같을때 , 안에 있는 문자가 1개 밖에 없거나 , 이 문자 전까지 즉 [i-1][j+1] 까지가 동일한 문자였으면 팰린드롬이라고 할 수 있다. 그 찾은 문자중에 가장 긴 문자를 return 하면 된다. 문제 정답 - https://github.com/kwonhy..
LeetCode - April 30-Day LeetCoding Challenge - Week 1 오랜만에 알고리즘을 공부 감을 찾기 위해 Leet Code 30 챌린지 문제들을 풀어보고 복기 해보자 - Maximum Subarray 문제 문제 요약 - 주어진 배열에서 값을 더해서 가장 큰 합이 되도록 만드는 문제다 다이나믹 프로그래밍 문제라 할 수 있겠다 문제 풀이 - 임시 저장할 배열을 생성, 0 부터 시작해서 다음 숫자로 갈때마다 각 숫자까지 왔을때 최대의 합이 나오는 숫자를 새로 생성한 배열에 저장을 한다 . 1. 이 전 자리까지 더해서 나올 수 있는 가장 큰 값과 + 현재 자리수 2. 현재 자리수 저 2개를 비교해서 가장 큰 수를 배열에 저장 문제 정답 https://github.com/kwonhyucknae/algorithm_study/commit/a57ebcc092f54e10d933afa..

티스토리툴바