농담곰담곰이의곰담농
공지사항
-
크래프톤 정글 6기 교육생이 되었슴다.
Today I Learn
-
크래프톤 정글 6기 TIL - Review | 트라이( Trie ) 크래프톤 정글 6기 TIL - Review | 트라이( Trie )
유튭 강의를 하나 슥 볼랬는데 바킹독님 마지막 강의가 트라이였다.내 최애 남잔데, 그의 최애 알고리즘이 트라이라 그래서 호감도 급 상승..렛츠 기릿.. 진심으로 바킹독님..넘 멋지다..트라이( Trie )문자를 효율적으로 처리하기 위한 트리 자료구조 ✅ 장점 : 단어의 저장 개수와 무관하게 삽입,탐색, 삭제가 O(|S|)의 시간 복잡도를 가진다.✅ 단점 : 메모리를 많이 차지한다. 트리의 정점의 index를 기록해야해서 int의 4바이트* |S| 만큼 메모리를 더 사용한다.다른 자료구조와 비교!이진 검색 트리 : 삽입, 탐색, 삭제가 O(logN) 이지만, 문자열을 검색할 경우 단어의 길이 S 만큼 대조를 해야하기 때문에,최악의 경우 O( S * logN ) 이 걸린다.해시 : 삽입, 탐색, 삭제가 O.. -
크래프톤 정글 6기 TIL - Review | 보이어-무어 알고리즘 크래프톤 정글 6기 TIL - Review | 보이어-무어 알고리즘
정글 중반기에 들어가면서,, 할게 너무 많고 블로그에 "정리"를 하는거 자체도 힘들어서.. 공부하면서 노션에다 기록했더니 TIL을 안쓰는 사람처럼 보여버렸다..수료를 하고나서~ 좀 쉬다가!!정글 콤파스 보면서 놓쳤던 부분들 복습하는 중인데, 여기다가 정리를 해보려구 한다.나름 복습할 때 도움이 많이 되었다! 키키✅ 보이어 - 무어를 공부하기 전에....1. 부르투 포스 알고리즘2. KMP 알고리즘 에 대해 먼저 공부하는 것을 추천 ! Boyer - Moore algorithm( 보이어 무어 알고리즘 )문자열 검색에 사용되는 알고리즘이다.불필요한 것을 건너뛰고. 검색을 빠르게 하는 것이 주 목표.워드 검색 기능에서 사용된다. 보이어-무어 알고리즘은 보통 상황에서 문자열은 앞부분보다는뒷부분에서 불일치가 일어..
Coding Test
-
10844 쉬운 계단 수 10844 쉬운 계단 수
https://www.acmicpc.net/status?user_id=yuu_ta&problem_id=10844&from_mine=1 ✔ 유형 : DP✔ 문제 풀이: 일의 자리 수에 어떤 수가 오느냐에 따라 경우의 수가 달라짐을 알고, 점화식을 세워 배열을 채워나간다. 코드import sysinput = sys.stdin.readlineMOD = 1000000000N = int(input())# 1 = 2: for i in range(2, N+1): DP[i][0] = DP[i-1][1] % MOD for j in range(1, 9): DP[i][j] = (DP[i-1][j-1] + DP[i-1][j+1]) % MOD .. -
11053 가장 긴 증가하는 부분의 수열 11053 가장 긴 증가하는 부분의 수열
https://www.acmicpc.net/problem/11053✔ 유형 : DP(LIS)✔ 문제 풀이: LIS(Longest Increase Sequence) 의 로직과 비슷하다. DP[i] 를 i 번째 까지 가장 긴 증가하는 부분 수열의 개수라고 정의했을 때. i보다 앞쪽에 있는 원소들과 비교해서 i번째의 수보다 작을 때 개수를 업데이트 한다. 정리하자면,DP[i] : 현재까지 계산된 i위치에서의 LIS의 길이DP[j] + 1 : j위치까지 LIS에 현재 원소를 추가한 길이 그리고 D[i] 는 위의 두 경우의 수 중 최대값으로 업데이트 해주어야한다. 따라서, "현재 원소를 이전 LIS 에 추가했을 때 더 긴 LIS가 되는가?"를 조건을 생각해주면 되는것이다. 코드import sysinput = s.. -
2156 포도주 시식 2156 포도주 시식
https://www.acmicpc.net/problem/2156✔ 유형 : DP✔ 문제 풀이: 점화식을 세우는 접근방식은 다음과 같다 1. 맨 마지막 포도주를 무조건 선택한다 했을 때, 연속 두개를 선택하고 싶다면, arr[i] ( 마지막 포도주 ) , arr[i-1]( 마지막에서 두번째 포도주), 그리고 3개를 연속해서 선택할 수 없으므로arr[i-2]는 선택하지 않는다. 2. 맨 마지막 포도주를 무조건 선택하고, 그 전 포도주는 선택하지 않을 때,arr[i] ( 마지막 포도주 )를 선택하고, arr[i-1]는 선택하지 않는다. 3. 맨 마지막 포도주를 절대 선택하지 않을 때DP[i-1] 포도주의 개수가 N-1때의 최대값을 반영하면 된다. 이를 일반화 하면DP[i]는 세가지의 경우의 수로 일반화 하.. -
1464 1로 만들기 1464 1로 만들기
https://www.acmicpc.net/problem/1463 ✔ 유형 : DP✔ 문제 풀이: 정수에 사용할 수 있는 연산은 총 3가지인데, 빠르게 1을 만들려면 세가지 연산을 시행했을 때 값이 가장 작아야 한다.X라는 수를 1로 만들으려 했을 때,위 세가지 연산을 시행하면 우선 1번의 연산을 한 것이 된다. DP[X] = 정수 X에 연산을 시행했을 때 1이 되는 최소 연산 수행 횟수라고 정의할 때 다음과 같이 문제를 작게 나눌 수 있다.DP[X] = 1 + DP[X에 세가지 연산중 하나로 실행한 결과]와 같게 된다. 따라서 X에 세 가지 연산을 실행한 결과 값 중 가장 작은 값을 반영해서최소 연산 횟수를 저장해 나갈 수 있다. 다시 정리해보면 아래 점화식을 세울 수 있다. 코드import sysN .. -
1923 연속합 1923 연속합
✔ 유형 : DP✔ 문제 풀이: 코드import sysimport copyinput = sys.stdin.readlineN = int(input())arr = list(map(int, input().split()))DP = copy.deepcopy(arr)for i in range(1, N): DP[i] = max(DP[i]+DP[i-1], arr[i]) #resultprint(max(DP))