본문 바로가기

study

 (104)
[알고리즘] 다이나믹 프로그래밍(동적 계획법) - 2 공부 : 동빈나 유튜브 + 책 실전문제 - 효율적인 화폐 구성 N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 만들기 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분 첫째줄에 N, M ( 1
[알고리즘] 다이나믹 프로그래밍(동적 계획법) - 1 공부 : 동빈나 유튜브 + 책 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 구현은 일반적으로 Top-Down(하향식)/Bottom-Up(상향식)으로 구성된다. - Top-Down은 재귀로 / Bottom-Up은 반복문으로 구현 가능 - 다이나믹 프로그래밍의 전형적인 형태는 Bottom-Up 방식 결과 저장용 리스트는 DP 테이블이라고 부른다. - 다이나믹은 자료구조의 동적과 다르게 별다른 의미 없이 사용된 단어 더보기 자료구조에서 동적 할당(Dynamic A..
[알고리즘/프로그래머스] 그리디 - 조이스틱 탐욕법(Greedy) > 조이스틱 (개인적으로 어려웠음) 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수 만들기 실패한 코드 아래의 코드는 테스트케이스 11번이 틀림 --> "ABAAAAAAAAABB" 일 때 7이 출력되야 하는데 15가 출력됨 한 방향으로 가는 것만이 아니라 2번째 B까지 갔다가 다시 돌아가는 것이 빠르기 때문에 출력값이 다름 def s..
[알고리즘/프로그래머스] 2019 KAKAO BLIND RECRUITMENT - 실패율 2019 KAKAO BLIND RECRUITMENT > level1 실패율 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 실패율 : 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수/스테이지에 도달한 플레이어 수 N : 전체 스테이지 개수 stages : 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 실패율이 높은 스테이지부터 내림차순으로 스테이지 번호가 담겨있는 배열을 리턴 import heapq def solution(N, stages): fail = {} heapq.heap..
[알고리즘 / 자료구조] 트리(Tree) 공부 : 동빈나 유튜브 트리 : 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 트리 관련 용어 - 루트 노드(root node) : 부모가 없는 최상위 노드 - 단말 노드(leaf node) : 자식이 없는 노드 - 크기(size) : 트리에 포함된 모든 노드의 개수 - 깊이(depth) : 루트 노드부터의 거리 - 높이(height) : 깊이 중 최댓값 - 차수(degree) : 각 노드의 자식 방향 간선 개수 -- 자식의 개수 - 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1 이진 탐색 트리 (Binary Search Tree) : 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료..
[알고리즘 / Oracle] 프로그래머스 - 보호소에서 중성화한 동물, 우유와 요거트가 담긴 장바구니 프로그래머스 level4 보호소에서 중성화한 동물 코딩테스트 연습 - 보호소에서 중성화한 동물 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr -- 중성화 X Intact -- 중성화 0 Spayed or Neutered SELECT INS.ANIMAL_ID, INS.ANIMAL_TYPE, INS.NAME FROM ( (SELECT ANIMAL_ID, ANIMAL_TYPE, NAME FROM ANIMAL_INS WHERE SEX_UPON..
[알고리즘 / 자료구조] 우선순위 큐(Priority Queue)와 힙(Heap) 공부 : 동빈나 유튜브 + https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html 우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 구현 방법 1) 단순히 리스트를 이용하여 구현 2) 힙(heap)을 이용하여 구현 ( 파이썬 - import heapq) 우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 ( 힙 정렬 ) -- O(NlogN) Heap - 완전 이진 트리 자료구조의 일종 - 항상 roo..
[알고리즘 / Oracle] 프로그래머스 - 입양 시각 구하기(2) 프로그래머스 level4 입양 시각 구하기(2) 코딩테스트 연습 - 입양 시각 구하기(2) ANIMAL_OUTS 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블입니다. ANIMAL_OUTS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, NAME, SEX_UPON_OUTCOME는 각각 동물의 아이디, 생물 programmers.co.kr SELECT H.HOUR, NVL(COUNT, 0) as COUNT FROM (SELECT TO_CHAR(DATETIME, 'HH24') AS HOUR, COUNT(*) AS COUNT FROM ANIMAL_OUTS GROUP BY TO_CHAR(DATETIME, 'HH24')) A RIGHT JOIN (SELEC..

티스토리툴바