Dev Note

문제를 풀다가 궁금증이 생겼다. 같은 배열을 heapq 모듈을 사용하여 heap 자료구조를 만드는데 heappush 방식과 heapify 방식의 결과가 다르다. 힙(heap)이란? 힙은 "부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리" 이다. 힙은 "0부터 요소를 셀 때, 모든 k에 대해 a[k]

코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 이해도 ★☆☆☆☆ 접근방법 왜 이 문제가 그리디 문제일까? 생각해보았다. 그리디 문제인 이유는, 상하 움직이고 좌우 움직일 때 덜 움직이는 방향을 선택해야 하기 때문이다. 1. 상 - 하 방향의 관점 A 부터 오름차순으로 알파벳을 찾는게 빠를지, Z부터 내림차순으로 찾는게 빠를지 비교한다. 각 알파벳마다 상하조정 중 min 값으로 최소 횟수를 담아두는 배열을 만든다. 2. 좌 - 우 방향의 관점 방법 1) 왼쪽에서 오른쪽으로만 이동하는 경우 ..

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 이해도 ★★☆☆☆ 접근법 반복문 접근하면 메모리 초과가 나서 우선순위 큐를 구현해야 한다. 우선순위 큐는 힙으로 구현한다. 한 행씩 진행한다. 힙이 비어있다면 푸시하고, 비어있지 않은데 가장 작은 수보다 큰 수가 나오면 푸시하고, 추가된 힙에서 가장 작은 수를 pop 한다. 하나씩 추가했다 뺏다를 반복하므로 가장 큰 수부터 N개의 숫자가 힙에 담겨있다. 그 중 가장 작은 수를 출력한다. 왜 메모리 초과 ..

문제 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 이해도 ★★☆☆☆ 소감 이름 갯수(1~20개 알파벳 소문자), 동명이인 여부에 낚여서 헤매었다. 이 문제에서는 필요가 없었다. 해시를 어떻게 적용해야할지 고민이 되어서 쉬운 문제인데도 접근이 어려웠다. 인덱스를 비교해도 되고, 해시맵을 사용해도 된다. 방법 1. 반복문 돌며 인덱스 비교하기 두 리스트의 인덱스를 비교해서 해당 값이 다르면 완주를 못한 사람임을 알 수 있다. 먼저 인덱스를 비교하기 위해 각 리스트를 정렬해야 한다. 원본 리..

코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 이해도 ★★★☆☆ 소감 힙 자료구조에 대해 알게되었다. 파이썬 힙큐(heapq) 모듈을 사용하여 구현하는 방법을 알게 되었다. 힙을 만드는 방법 방법 1. 빈 리스트 생성 후 heappush 함수로 넣기 방법 2. heapify 함수로 리스트를 바로 힙으로 바꾸기 -> 처음에 이 두 개를 같이 써서 시간초과가 났었다. heapify 사용할 경우, 새로운 변수에 넣는게 아니라 리스트를 힙 자체로 변환한다는 점에 주의하자! heapify 하면 기존 리스..

https://www.toptal.com/developers/sorting-algorithms/ Insertion Sort - Sorting Algorithm Animations Animation, code, analysis, and discussion of insertion sort on 4 initial conditions. www.toptal.com 시간복잡도 빠르기 비교 O(1) > O(logN) > O(N) > O(NlogN) > O(n^2) 시간복잡도 비교 선택 정렬 삽입 정렬 버블 정렬 병합 정렬 퀵 정렬 힙 정렬 카운팅 정렬 시간복잡도(평균) n^2 n^2 n^2 nlogn nlogn nlogn n 시간복잡도(최악) n^2 n^2 n^2 nlogn n^2 nlogn n 가장 빠른 경우 일정..

Intro stack 을 활용하면 infix notation을 postfix notation으로 변환할 수 있다. 1972년에 도입된 최초의 휴대형 계산기 HP-35는 postfix notation을 기반으로 계산한다. 당시에 괄호를 처리하는게 어려웠기 때문이다. 일단 postfix notation으로 변환하고 나면 계산기 입장에서는 계산이 쉬워진다. 왼쪽부터 차례대로 읽는다. (Read the expression from left to right) 현재 요소가 피연산자(숫자)이면 스택에 넣는다. (If current element is a value (e.g. Integer) push it to the stack) 연산자(operator)이면 마지막 두 요소를 꺼내 (pop last two operan..

이해도 ★★★★★ 문제 접근방법 stack 이 빌 때까지 반복하며 여러 경우의 수를 처리한다. 스택이 다 비면 1, 그렇지 않으면 0, 중간에 여러 경우의 수에 걸리면 0을 출력한다. left 리스트의 인덱스와 right 리스트의 인덱스가 일치하면 짝이 맞는 괄호이다. [경우의 수] 1. 스택은 비어있는데 우측 괄호가 나온 경우 ex. ) or } 2. 스택의 마지막 괄호와 다음 괄호의 인덱스가 다른 경우 ex. ({) 3. data를 다 돌았는데 stack이 남아있는 경우 ex. ) , } , )} , { ,...etc 나의 코드 while 반복문 사용 left, right 분리 T = int(input()) for tc in range(1, T+1): data = list(input()) left =..