쿠와와의 하루정리

접근법. DP는 메모리를 사용해서 실행 시간을 줄여야 하는 알고리즘 -> 중간중간의 결과값을 저장해서 실행시간을 줄이는 방법으로 접근하는게 포인트 Level 3 N으로 표현 코딩테스트 연습 - N으로 표현 programmers.co.kr # dynamic_1.py N = 5 # 2 number = 12 # 11 # 4, 3 def solution(N, number): S = [0, {N}] if N == number: return 1 for i in range(2, 9): case_set = {int(str(N)*i)} for j in range(1, i//2+1): # S[i_half] S[1] for x in S[j]: for y in S[i-j]: case_set.add(x+y) case_set.a..

그리디 알고리즘 - 동적 프로그래밍 사용시 지나치게 많은 일을 한다, 그래서 보완하는 개념으로 나옴 미래를 생각하지 않고 최선의 선택을 하는 방법, 즉 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 최종 해답에 도달하는 문제 해결 방식 1번. 체육복 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr # greedy_1.py n = 5 # 전체 학생 lost = [2, 4] # 잃어버림 reserve = [1, 3, 5] # 여벌 def solution(n, lost, reser..

완전탐색 무식해 보여도 사실은 최고의 방법일 때가 있지요. 가능한 모든 상황을 조사해 문제를 풀어보세요. ▷ '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 바로 모든 경우의 수를 넣어보는 것으로 가능한 방법을 전부 만들어 보는 알고리즘을 뜻한다. ▷ 완전 탐색은 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다. ▷ (예제) n개의 원소 중 m개를 고르는 모든 조합을 출력하는 코드 ▷ 완전 탐색 방법 Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법 비트마스크 비트를 이용한 기법으로써 알고리즘보다는 테크닉 중 하나로써, 정수의 이진수 표현을 활용한 기법 순열 : 순열의 시간..

힙(Heap)이란? 힙 트리(Heap Tree), 보통 줄여서 힙(Heap)이라고 부른다. 힙은 부모 노드의 값이 항상 하위 노드의 값보다 작거나 큰 구조의 트리이다. 트리의 일종으로 완전 이진 트리이면서, 부모 노드의 값이 항상 하위 노드의 값보다 작거나 큰 구조의 트리이다. 힙의 사전적인 의미가 '쌓아 올린 더미'인 것 처럼, 데이터가 위에서부터 규칙적으로 쌓여있는 구조이다. - 우선순위 큐를 위하여 만들어진 자료구조 - 여러 개의 값 중 최댓값과 최솟값을 빠르게 찾기위한 구조 - 부모 노드의 값이 자식 노드의 키 값보다 항상 큰 이진트리 - 힙은 중복된 값을 허용 종류 최대 힙 Max Heap 부모 노드의 값이 항상 하위 노드의 값보다 크거나 같다. 부모_key >= 자식_key 최소 힙 Min H..

문제 : programmers.co.kr/learn/courses/30/parts/12198 K번째 수 # sort_1.py array = [1, 5, 2, 6, 3, 7, 4] commands = [[2, 5, 3], [4, 4, 1], [1, 7, 3]] def solution(array, commands): return [(sorted(array[a-1:b])[c-1]) for a, b, c in commands] print(solution(array, commands)) # return [5, 6, 3] 가장 큰 수 # sort_2.py from functools import reduce numbers = [40, 403] # [3, 30, 34, 5, 9] # [6, 10, 2] # [3, 30..

스택 스택은 말 그래도 쌓아올린다는 것이다. 무엇을? 데이터를 순서대로 메모리에 올리고 꺼낸다는 것이다. 특징 - 같은 구조와 크기의 자료를 정해진 방향으로만 쌓고 꺼낼 수 있다. - 메모리에 삽입하는 연산을 Push라고 한다. - 메모리에 삭제하는 연산을 Pop이라고 한다. - 마지막에 삽입된 자료가 가장 먼저 삭제된다. (후입선출) - 비어있는 스택에서 원소 추출하려고 하면 Underflow, 메모리가 꽉 찾을 때 더 넣으려고 하면 Overflow라고 한다. 예) 방문 기록, 실행 취소, 후위 표기법 계산 큐 큐의 개념은 도로로 생각하면 한 방향 일반통행이라고 생각하면 된다. 우리가 원한다고 유턴할 수 있는 것이 아니고 한 번 들어오면 반대쪽으로 나갈 수 밖에 없는 구조를 가진다. 즉 선입선출 스택의..

블록체인, 암호화폐 기술에 항상 등장하는 것 중 하나가 해쉬함수이다. 해쉬함수란 간단히 말하면 어떤 길이의 데이터를 입력해도 정해진 길이의 결과를 주는 함수를 이야기한다. 특징. - 어떤 길이의 데이터도 입력으로 사용될 수 있다. - 결과는 정해진 길이로 나온다. - 계산 시간이 합리적으로 추정 가능해야한다. - 입력 길이에 제한이 없기 때문에 최소한 입력 길이에 선형적으로 비례하는 특성은 있어야한다. - 결과값이 중복될 일은 거의 없다. - 입력값을 알 수 없다. - 결과값을 알려주고 입력값을 찾을 수 있는 특벽한 공식이 없다. 나는 좀 더 자세한 설명은. www.youtube.com/watch?v=Vi0hauJemxA ( 내 youtube 채널 아님 )에서 설명을 들었다. 소스 예제는 (program..

P 란? Polynomial time 이내에 해결 가능한 알고리즘을 말한다. 즉, 알고리즘의 복잡도가 O(n^x)로 표현되는 모든 문제들을 말한다. 이때, 해결 이란 단어에 대해 자세히 말하고 싶은데, 여기서 말하는 해결이란 어떠한 instance에 대해 동일하게 해답을 내놓을 수 있는 방법을 말한다. Certifiers NP Polynomial time에 답의 존재유무를 확인 할 수 있는 문제를 말한다. NP는 non-deterministic polynomial time의 약자 NP에 속하는 문제들이 다항시간에 해결 가능한지, 불가능한지 모르기 때문이다. 마찬가지로 답을 확인한다는 것에 대해 말하고 싶은데 흔히 결정문제라고도 말한다. 해결 방법은 모르지만 답의 유무는 확인 가능한 문제들의 집합이다. P..

Optimal Binary Search Tree Solution 1 : n 개의 key 를 가지는 가능한 모든 BST 를 생성하여, 그 중 total search cost 가 최소인 것을 고르기. - n 개의 node 를 가진 BST 는 대략 O(4n) 개 정도 된다 à exponential time ! Solution 2 : Dynamic programming approach 1.Subproblem 정의 : 임의의 1 ≤ i ≤ j ≤ n 에 대해 C (i, j) 를 전체 key ki, ki+1, …, kj 을 각각 fi, fi+1, …, fj 번 검색한다 할때, optimal BST 의 total search cost 라고 하자. 따라서 C (1, n) 이 우리가 원래 구하고자 하는 optimal B..

Shortest Path Problem -벨만 포드 알고리즘 구현 Algorithm outline (negative cycle 이 없다 가정 시) 1.알고리즘은 총 0 ~ n-1 의 stage (iteration) 으로 구성되며, i 번째 stage 가 끝날 때 마다 G 의 모든 vertex v 에 대해 dist (i, v) 가 dist (v) 에 저장된다 (invariant). 2.0 번째 stage 에서는 앞선 base case 에 맞게 dist 값을 정해 준다. 3.이후 i 번째 stage 마다 모든 edge (u, v) 에 대해 다음 작업을 반복한다. à dist (v) > dist(u) + w (u, v) 인 경우 dist (v) 를 dist (u) + w (u, v) 로 update 시간 복잡..