본문 바로가기

Problem Solving34

[알고리즘] 이분 탐색, 매개 변수 탐색 & 백준(랜선 자르기, 나무 자르기, 공유기 설치, 히오스 프로게이머) 이분 탐색이란? 정렬된 배열에서 target의 존재 여부와 위치를 알려준다. 재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다. 매개 변수 탐색(Parametric Search)란? 이분 탐색과 유사하다. 탐색 범위를 반으로 줄이기 때문에 시간복잡도는 O(logN)이다. 최적화 문제를 결정 문제로 바꾸어 풀 때 사용한다. - 최적화 문제: 어떤 알고리즘의 최적 솔루션을 찾는 것 - 결정 문제: 답이 이미 결정되어 있다고 보고 문제를 푸는 것 이진 탐색과 매개변수 탐색의 차이점 이진 탐색은 배열에서 target과 일치하는 값을 찾으면 바로 함수를 종료하지만, 매개변수 탐색은 함수를 종료하지 않고 모든 배열을 살펴본다. 따라서, 매개변수 탐색은 어떤 조건을 만족하는 위치 중 .. 2022. 10. 6.
[알고리즘] 분할 정복 & 백준(곱셈, 행렬 제곱) 분할 정복(Divide & Conquer) 분할 정복은 문제를 여러개로 나누어서 푸는 알고리즘이다. 교수님께서 미친듯이 강조해서 "디바이드앤퀀쿼"만 기억이 난다.. * 동적 계획법(DP)과의 차이점 1. 동적 계획법은 분할한 문제들이 서로 영향을 미침. 2. 분할 정복은 분할한 문제들이 서로 영향을 미치지 않음. * 분할 정복의 필요조건 1. 문제를 나눌 수 있어야 한다. 2. 부분 문제의 답을 이용하여 원래 문제의 답을 계산하는 방법이 있어야 한다. * 분할 정복의 알고리즘의 접근법 1. 분할: 문제를 작은 문제로 분할하는 과정 2. 정복: 분할한 작은 문제들을 해결 3. 조합: 작은 문제에 대한 결과를 원본 문제에 대한 결과로 조합한다. 분할 정복을 이용한 거듭제곱 먼저, 거듭제곱이란 주어진 수를 주.. 2022. 10. 5.
[알고리즘] 행렬 곱셈, 행렬 제곱 행렬 제곱의 문제를 풀어야하는데, 행렬 곱셈을 하는 법부터 정확히 알지 못 했기 때문에 정리하는 글이다. 1. 2740: 행렬 곱셈 문제 N*M크기의 행렬 A와 M*K크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오. => 행렬의 곱셈 공식에 의해서 N*M, M*K 행렬을 곱하면 N*K 행렬이 된다. 오른쪽 사진에 의하면, 3 x 2 행렬과 2 x 3 행렬이다. 3 x 2 행렬과 2 x 3 행렬을 곱하면 3 x 3 행렬이 만들어진다. 두 행렬을 곱하면 위의 왼쪽 사진과 같은 결과가 나온다. 1) N과 K에 대해 이중 for문을 돌면서, 2) 벡터의 크기 M만큼 for 돌면서 행벡터와 열벡터의 각 요소 곱의 더하기 값을 구해주고 3)결과 행렬에(2차원 리스트) 넣어주면 된다. impo.. 2022. 10. 4.
[알고리즘] 우선순위 큐, 힙 & 백준(최대 힙, 최소 힙, 가운데를 말해요, 카드 정렬하기) 우선순위 큐란, 데이터 삽입은 어떤 순서로 해도 상관없지만 데이터를 삭제할 때는 우선순위에 맞춰 더 높은 우선순위를 갖는 데이터를 먼저 삭제하는 큐를 말한다. 우선순위 큐는 힙을 통해 구현할 수 있다. 힙이란 완전 이진트리의 일종으로 대표적으로 최대 힙과 최소 힙이 있다. - 최대 힙: 루트 노드가 가장 큰 값을 가지며, 부모 노드는 항상 자식 노드보다 큰 값을 갖는다. - 최소 힙: 루트 노드가 가장 작은 값을 가지며, 부모 노드는 항상 자식 노드보다 작은 값을 갖는다. 힙에서의 삭제는 항상 루트 노드를 먼저 삭제하며 노드 변동 시 힙의 성질을 만족하도록 힙을 변동시킨다. 이러한 힙의 특징을 이용하여 우선순위 큐를 구현하는 것이다. 사실상 우선순위 큐를 구현하는 것은 힙을 구현하는 것이다. 최대 힙 구.. 2022. 10. 3.
[Python] 파이썬 영문 대소문자 변환 참고 공부) https://mwultong.blogspot.com/2006/12/python-uppercase-lowercase-capitalize.html 2022. 9. 27.
[Python] 순열 permutations, 조합 combinations 순열과 조합을 직접 구현하려다가 구현의 벽에 부딪혔고, (ㅠㅠ) import itertools를 이용하여 간편하게 순열과 조합을 이용할 수 있는 방법을 찾았다. 순열 permutation 순열이란 몇 개를 골라 순서를 고려해 나열한 경우의 수를 말한다. 즉, '서로 다른 n개 중 r개를 골라 순서를 정해 나열한 경우의 수'이다. 순열은 순서를 고려하기 때문에 [A, B, C]의 리스트에서 2개의 원소를 골라 순서를 정해 나열하면 [(A, B), (A, C), (B, A), (B, C), (C, A), (C, B)] 이다. 즉, (A, B)와 (B, A)는 다른 것이다. import itertools arr = ['A', 'B', 'C'] nPr = itertools.permutations(arr, 2) .. 2022. 9. 27.
[Python] 리스트의 문자열을 int로 변환 1. map 함수 활용 # list_a = ['1', '2', '3', '4'] -> list_a = [1, 2, 3, 4] 로 바꾸고 싶을 때, list_a = map(int, list_a) 2. 입력 받은 n을 통해 n개의 int형 num 리스트를 출력 import sys n = int(sys.stdin.readline()) num = [int(sys.stdin.readline()) for i in range(n)] # int()를 씌워줌으로써 int 형태로 변환해준다. 3. 입력받기에서 int로 받고 싶다면 list(map(int, sys.stdin.readline().split())) 2022. 9. 27.
[Python] 파이썬 데이터 입력받기 # 1. 하나의 값만 입력받을 때 sys.stdin.readline().strip() # 2. 입력이 한 줄로 여러 값이 들어왔을 때 sys.stdin.readline().split() 결과: ['20', '1', '15', '8', '4', '10'] # 3. 입력이 한 줄로 여러 값이 들어왔을 때, 리스트의 요소들이 int일 경우 list(map(int, sys.stdin.readline().split())) 결과: [20, 1, 15, 8, 4, 10] # 4. 입력이 여러 줄로 들어왔을 때 N = int(sys.stdin.readline()) num = [sys.stdin.readline().split() for i in range(N)] data = list(map(lambda s: s.stri.. 2022. 9. 26.
[Python] 파이썬 숫자 각 자리수 분리 number = 123 num_list = list(map(int, str(number))) print(num_list) 2022. 9. 26.

티스토리툴바