개발시작

Hash Table은 중요한 자료구조이다. 유용하고 코드를 빠르게 만들어 줄 수 있다. Hash Table은 Key Value System을 이용하여 자료를 정리한다. Key Value System의 한 예시로는 사전을 들 수 있겠다. Key = 단어를 찾고 Value = 해당 단어의 뜻과 설명으로 표현 할 수 있을 것 같다. Array를 선형 탐색한다고 가정해 보면 걸리는 시간은 O(N) Hash Table 에서 검색을 한다고 가정하면 걸리는 시간은 O(1) 상수 시간의 시간이 걸린다. 즉, Hash Table에서 값을 찾거나, 삽입하거나 삭제할 때도 마찬가지로 1개의 Step 만 필요로하다. Hash Table에서 Key 랑 Value를 함께 저장하는 것 외에 Value 만 저장하여 빠르게 처리할 수..

input 값이 A,B,C 모두 2,147,483,647 이하의 자연수라고 명시되어 있다. 그렇기 때문에 반복문을 이용하여 문제를 풀게되면, 시간 초과가 나올 것이다. 시간 초과가 나왔던 풀이 1. 반복문 2. print((A**B) % C) 문제를 해결하기 위해 python method를 찾다가 pow라는 method를 발견했다. pow(x, y[, z]) 분할 정복 방식 지수가 짝수일 경우 A^B * A^B 로 나눌 수 있고, 지수가 홀수일 경우 A^B * A^B * A로 나눌 수 있다. B를 2에 대한 거듭제곱 형태로 계속하여 분할하여 B만큼 A를 거듭제곱 하는 것이 아니라 제곱을 한 뒤, 거기에 제곱을 또하고 또하는 방식을 취하여 연산 수를 최대한 줄여가는 방식이다. 참조: https://tmdr..

시간 제한을 못보고 문제 설명만 읽고 단순하게 풀었을 때 로직은 이런식으로 구성했다. 첫날에 나무를 오르고 목표 높이보다 작을경우 하루를 세고 B만큼 미끄러지고... 문제에서 목표 높이에 도달하는 순간 종료를 하기 때문에 Temp가 V와 같아지거나 목표 높이보다 커질 때 탈출하게 작성했지만 시간 초과가 떳다(PyPy3도 마찬가지로) 저 내용을 수식으로 정리를 하게되면 A + (A- B)*(Day) >= V 가 되고 문제에서 알고 싶어하는 것이 Day니까 (Day) >= (V - A) / (A - B) 가 된다. 이 경우에서 Day가 3.4 2.3 이런식으로 나누어 지는 경우에는 하루 더 올라가야 한다. (즉 나눴을 때, 나머지가 있을 경우) 맨 처음 문제 설명만 읽고 단순하게 풀면 기본 예제 수준의 문제..

문제에 대한 출력을 이해하는데 시간이 오래 걸렸던 문제이다. 입력에 대해서 맨 첫줄에 크기를 입력 받고 리스트에 n만큼의 수를 입력 받은 후에 Stack의 push, pop을 이용하여 리스트와 동일하게 만들 수 있는가 없는가 물어보는 문제이다. 우선 1부터 n까지 차례대로 입력 받는 Stack1이 존재한다. (입력 1의 일부만 설명) 8(+) 7(-) 4(+) 6(+) 7(+) 8(-) 3(+) 5(+) 6(-) 5 6 2(+) 3(-) 2 3 2 3 1(+) 4(-) 1 4 1 4 Stack1 Stack2 Stack1 Stack2 Stack1 Stack2 Stack1 에서 Pop을해서 다른 Stack2에 담아두었다고 생각하면 된다. 최종적으로 Stack2에 있는 값과 n만큼의 수를 입력 받은 리스트가 ..

스택(Stack) LIFO (Last In First Out) : 마지막에 들어간 것이 첫번째로 나오는 구조 Stack에 데이터를 넣고 뺄 때 항상 top에 있는 것이 먼저 나옴 자료가 없을 때 pop -> stack underflow, 크기 이상의 자료를 push -> stack overflow 데이터의 삽입과 삭제가 빠르며 (O(1)), 괄호 검사, 역순 문자열 만들기, 후위 표기법으로의 변환 문제에 사용한다. 큐(Queue) FIFO(First In First Out) : 맨 처음 들어간 것이 첫번째로 나오는 구조 선형 큐의 경우 Front와 Back을 둘 다 이동하면서 삽입, 삭제를 할 경우 배열의 끝에 저장되어 있는 상황이 되면 Back을 더 이상 이동시킬 수 없어서 overflow가 발생한다 ..

힙은 모든 부모노드가 자식보다 같거나 작은 값을 갖는 완전 이진트리 이다. 최대 힙은 자식의 키 값보다 크거나 같은 값을 가지고, 최소 힙은 자식의 키 값보다 작거나 같은 값을 가진다. 모든 K에 대하여 heap[k]

문제를 보고나서 노트에 잠깐 써보고 바로 풀어봤다... 해당 리스트를 1차원 리스트로 바꾼 후, sort() 나 reverse() 를 이용하여 len() - N or N - 1 번 째 출력하면 된다고 생각했다... 결론은 메모리 초과 2중 포문 때문에 그런 것 같다.. 파이썬 heapq를 이용하여 풀었다.. 행마다 N개를 최소 힙에 push ,pop을 반복하면서 힙에 N개를 유지하면 결국 top에 N 번째로 큰 수가 나온다. 문제에 맞는 풀이방식을 빠르게 적용 하고, 코드 구현이 막히지 않도록 문제를 많이 풀어봐야 겠다..

풀어본 문제는 Baekjoon 의 1920번 이다. 처음에 풀었던 방식은 단순하게 N[0] 하고 M[0 - 4] 를 비교 N의 리스트의 값을 1개 씩 증가해가며 있으면 1 출력 없으면 0 출력 이런 식으로 풀었는데 시간 초과가 발생하였다... 그래서 값을 비교할 때 사용하는 알고리즘 중에 시간 복잡도 O(logn)인 이진 탐색 알고리즘을 사용하여 푼 문제이다. 이진 탐색은 정렬되어 있는 리스트에서 값을 비교할 때마다 찾는 값의 범위가 중간 값보다 작으면 왼쪽 크면 오른쪽을 대상으로 하여 찾는 알고리즘 이다.

백준 13305번 문제이다. 거리 1키로당 기름 1리터를 사용하며, 기름 값을 최소로 지불하면 해결되는 문제 마지막 마을에서의 주유 비용은 비교할 필요 없으니 마지막 마을 까지의 거리 비용만 계산하여 구현하였다.

백준에서 가져온 문제이다. 사람마다 인출 시간이 다르기 때문에 인출 시간이 제일 긴 사람이 첫 번째로 줄을 선다면 전체 총 합이 커지기 때문에 오름 차순으로 정렬하는 것을 1순위로 생각했다. 오름차순 정렬 후 계산을 하면 홈페이지 문제 예시를 예로 들어 5명의 사람이 각각 1 2 3 3 4 분의 인출 시간을 가지고 있으며, 단순 계산식으로 표현하면 1 1+2 1+2+3 1+2+3+3 1+2+3+3+4 형태로 표현할 수 있다. 각 사람마다 앞에 사람의 인출하는데 걸리는 시간만큼 더 추가로 걸리기 때문이다. 간단하게 표현하자면 1*5 + 2*4 + 3*3 + 3*2 +4 N*인출시간 + (N-1)*다음 사람의 인출시간 ..... 이처럼 표현 가능하기에 이렇게 구현하였다.