분류 전체보기
[BaekJoon] 백준 1620번 나는야 포켓몬 마스터 이다솜
[BaekJoon] 백준 1620번 나는야 포켓몬 마스터 이다솜 문제: https://www.acmicpc.net/problem/1620 내코드 처음엔 무작정 배열에 넣어풀어봤다. 역시나 시간초과가 났다. N, M 최대값이 100,000인데 python의 list 자료형에서 index 메서드의 시간 복잡도가 O(n)이라서 총 O(M*N)의 시간 복잡도가 나오기 때문인가보다. 1억당 1초라 하면 100,000 * 100,000를 게산하면 1억을 훌쩍 넘겨버린다. # 틀린코드 N, M = map(int, input().split()) arr = ["" for _ in range(N)] for i in range(N): arr[i] = input() for _ in range(M): question = inp..
[BaekJoon] 백준 1074번 Z (Python)
[BaekJoon] 백준 1074번 Z 문제: https://www.acmicpc.net/problem/1074 내코드 처음에 생각한 방식은 다음과 같다. 1. 한변 길이가 4이상이면 나눠서 재귀로 돌기 2. 한변 길이가 2이면 r, c에 맞는 위치가 있는지 확인하고 없으면 다음 사분면 돌기 하지만 이렇게 하면 시간 초과가 났다. # 잘못 푼 코드 # BaekJoon1074.py def solv(n, x, y): global result if n == 2: if y == r and x == c: print(result) exit() elif y == r and x+1 == c: print(result + 1) exit() elif y+1 == r and x == c: print(result + 2) ex..
[Algorithm] Hash table
Hash Table 이란? (key, value)로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있다는 장점이 있다. 해시 테이블이 빠른 검색 속도를 제공하는 것은 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 각각의 key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색한다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. Ex) (key, value) = ("John Smith", "521-1234")를 크기가 16인 해시 테이블에 저장하면, 먼저 index = hash_function("John Smith") % 16으로 index를 구해서 array[index] = "521-1234"로 저장한다. 평균 시간 ..
[Algorithm] 이진 힙 Binary Heap
이진 힙이란? 이진힙은 우선 순위 큐를 위해서 만들어진 완전 이진 트리의 한 종류이다. 즉, 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조다. 이진 힙은 힙 중에서 가장 널리 쓰이며 힙의 특징(ex. 최대힙의 경우 부모 노드는 자식 노드보다 값이 커야 한다)을 만족한다. 참고로 이진 탐색 트리에서는 중복된 값을 허용하지 않지만, 힙 트리에서는 중복된 값을 허용한다. 종류 최대 힙 max heap: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙 min heap: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 구현 일반적으로 배열을 이용해서 구현한다. 구현을 쉽게 하기 위해서 배열의 첫 번째 인덱스인 0은 사용되지..
[Algorithm] Red Black Tree
레드 블랙 트리 (Red Black Tree)란? 레드블랙 트리는 지난번에 포스팅했던 트리에서 이어진다. 균형 이진 탐색 트리의 예시에서 레드블랙 트리를 언급했었고, 상당히 내용이 있는 이론이기 때문에 새로운 포스팅으로 옮겼다. 따라서 이진 탐색 트리에 대해서 안다고 가정하고 이어서 작성해보려고 한다. 특징 모든 노드는 빨간색 또는 검은색이다. 루트 노드는 검은색이다. 잎 노드는 검은색이다. (NIL 노드) 빨간 노드의 자식은 모두 검은색이다. (레드 노드는 연달아 나타날 수 없다.) 루트 노드에서 모든 잎 노드 사이에 존재하는 검은색 노드의 수는 모두 동일하다. 구현 탐색의 경우 기존의 BST와 동일하게 해주면 된다. 하지만 노드의 삽입과 삭제에서 문제가 발생한다. 트리의 균형이 유지가 안되기 때문이다..
[BaekJoon] 백준 11047번 동전 0
[BaekJoon] 백준 11047번 동전 0 문제: https://www.acmicpc.net/problem/11047 내코드 최소한의 동전으로 값을 표현해야한다. 그 순간 가장 최선의 선택인 특정 값보다 작은 값중 가장 큰 값을 선택해야 하므로 그리디 알고리즘이다. # BaekJoon11047.py n, k = map(int, input().split()) arr = [] for _ in range(n): arr.append(int(input())) result = 0 arr.sort(reverse=True) for i in arr: if k==0: break result += k // i k %= i print(result)
[BaekJoon] 백준 9461번 파도반 수열
[BaekJoon] 백준 9461번 파도반 수열 문제: https://www.acmicpc.net/problem/9461 내코드 i번째 수 + (i+1)번째 수의 합이 i+3번째에 놓이게 된다. 이를 이용해서 문제를 풀면 된다. # BaekJoon9461.py arr = [0 for i in range(101)] arr[1] = 1 arr[2] = 1 arr[3] = 1 for i in range(0, 98): arr[i + 3] = arr[i] + arr[i + 1] t = int(input()) for i in range(t): n = int(input()) print(arr[n])
[BaekJoon] 백준 9375번 패션왕 신해빈
[BaekJoon] 백준 9375번 패션왕 신해빈 문제: https://www.acmicpc.net/problem/9375 내코드 경우의 수로 푸는 수학문제였다. 각각 옷의 종류에 따라서 만약 a종류의 옷이 3벌이 있다면 각각을 선택하는 수 3 + 아무것도 선택안하는 경우 1가지 해서 총 4가지가 있고, b종류가 2벌이 있다면 동일하게 계산해서 3가지가 된다. 따라서 a종류 3벌, b종류 2벌이라면 4X3 = 12이고 각각 옷의 종류에서 아무것도 선택안하는 경우를 빼면 11가지가 답이된다. 이와 같이 코드를 작성해주면 된다. # BaekJoon9375.py test_case = int(input()) for _ in range(test_case): n = int(input()) clothe_type = ..