본문 바로가기

알고리즘146

Udemy : 알고리즘 완전탐색 Udemy : 알고리즘 완전탐색 udemy 알고리즘 코딩 테스트 완전탐색 존재하는 모든 경우의 수를 탐색을 하며 결과를 도출해 낸다 장점 모든 경우의 수를 탐색하는 것이라서 반드시 답을 찾을 수 있다 단점 모든 경우의 수를 탐색하는 것이라서, 계산하는 시간이 느리다 브루트포스 완전 탐색 방법론을 사용하는 알고리즘이다 무차별 대입이라고도 한다 시간이 오래 걸려도, 답을 구할 수 있는 방법이라서, 많이 사용이 된다 순열 itertools from itertools import permutations from itertools import combinations 모든 경우의 수를 순서대로 살펴볼 때 용이하다 from itertools import permutations v = [0, 1, 2, 3] for i.. 2023. 3. 7.
[Python] 백준 1913 달팽이 🧑‍💻 [Python] 백준 1913 달팽이 Silver 3 - 구현 무조건 matrix[0][0]은 N * N 이다 시작을 N * N으로 하고, 내려가면서 -1 을 한다 만약에 다음 좌표가 0이 아니거나, 행렬을 나가게 된다면 왼쪽으로 90도를 돌아서 앞으로 가면서 -1을 하면 된다 이것을 좌표의 값이 1이 될때까지 진행을 한다 코드 N = int(input()) M = int(input()) matrix = [[0] * N for _ in range(N)] num, i, j = N * N, 0, 0 ans_row, ans_column = 0, 0 while num > 0: # 아래로 내려가기 while i < N and matrix[i][j] == 0: if num == M: ans_row, ans_.. 2023. 3. 4.
Udemy : 알고리즘 자료구조 Udemy : 알고리즘 자료구조 udemy 알고리즘 코딩 테스트 배열 파이썬은 리스트를 사용한다 arr = [10, 11, 12, 13] arr[2] = 5 # output : [10, 11, 5, 13] 탐색 : O(1) 삽입/삭제 : O(N) 스택/ 큐 Stack = LIFO (Last In First Out) 리스트 안에 제일 마지막에 추가된 요소를, 제일 먼저 뺀다 즉 append를 통해서, 리스트 제일 마지막에 값을 넣는다 pop을 통해서 리스트 제일 마지막 요소를 빼낸다 맨 마지막에 요소를 추가하거나, 맨 마지막의 요소를 빼는 것이라서 삽입/삭제가 O(1) 이다 Queue = FIFO (First In First Out) 리스트 안에 제일 처음에 추가된 요소를, 제일 먼저 빼는 것 deque를.. 2023. 3. 2.
[Python] 백준 13397 구간 나누기 2 🧑‍💻 [Python] 백준 13397 구간 나누기 2 Gold 4 - 이진 탐색 구간의 점수의 최댓값의 최솟값을 기준으로 mid를 구하는 것이다 즉 주어진 배열에서 순회하면서 구간의 최댓값과 최솟값을 구해서 mid보다 작거나 같으면 계속 탐색을 한다 그게 아니면 새로운 구간을 만들어서, 새로운 최댓값과 최솟값을 구해준다 코드 N, M = map(int, input().split()) array = list(map(int, input().split())) def groups(mid): min_num, max_num = array[0], array[0] count = 1 for i in range(N): min_num = min(min_num, array[i]) max_num = max(max_num, a.. 2023. 3. 1.
[Python] 백준 1300 K번째 수 🧑‍💻 [Python] 백준 1300 Gold 2 - 이진 탐색 이 문제를 통해 더 많은 고민을 하고, 문제를 풀어야겠다는 생각을 했다 그냥 이진 배열을 만들고, 그 배열을 다시 일차원으로 만들어서, 정렬을 한 후에, k번째 숫자를 구할 수 있다 하지만 테스트를 통과하지 않는다 이진 배열을 만들고, 또 일차원 배열로 만드는 것이 메모리 면에서, 굉장히 많이 잡아 먹는다 하지만 A[i][j]는 패턴이 있다 첫 열은, 모든 수를 1로 곱하면 된다 [1, 2, 3, 4, 5] 두 번째 열은, 모든 수를 2로 곱하면 된다 [2, 4, 6, 8, 10] 세 번째 열은 ,모든 수를 3으로 곱하면 된다 [3, 6, 9, 12, 15] 이런 식인 패턴이 있다 위의 패턴을 보게 된다면 특정 숫자를 만들 때에, 그 숫자보.. 2023. 2. 27.
[Python] 백준 2343 기타 레슨 🧑‍💻 [Python] 백준 2343 Silver 1 - 이진 탐색 블루레이의 개수를 구하고, 개수가 작거나 같으면 right = mid - 1 크면 left = mid + 1을 해준다 이유는, 블루레이는 강의들의 묶음으로 이루어져 있다 블루레이의 개수가 맞춰야 하는 개수보다 적다는 말은, 하나의 블루레이에 너무 많은 강의를 넣었다는 것이다 즉 강의를 더 분포를 시켜야 한다 즉 하나의 블루레이에 들어갈 수 있는 강의의 시간은 더 줄어든다는 것 반대로 블루레이의 개수가 맞춰야 하는 개수보다 크다는 것은, 하나의 블루레이에 너무 적은 강의를 넣었다는 것 코드 N, M = map(int, input().split()) def count_cd(time): count = 0 temp = 0 for lecture .. 2023. 2. 27.
[Python] 백준 2467 용액 🧑‍💻 [Python] 백준 2467 용액 Gold 5 - 이진 탐색 산성 용액과, 알칼리성 용액이 있으면, 어떠한 두 용액을 섞어서 0과 제일 가까운 용액을 만드는 것이다 여기서 산성은 산성끼리, 알칼리성은 알칼리성 용액끼리 섞을 수 있다 이진 탐색을 하기 위해서는 정렬을 꼭 해야 한다 두 용액을 섞어서, 전에 섞은 용액보다 0과 가깝다면, 두 용액과, 용액들을 섞어서 나온 숫자를 저장해야 한다 즉 3개의 변수를 지속적으로 수정해야 하는 것이다 코드 N = int(input()) array = list(map(int, input().split())) array.sort() left = 0 right = N - 1 current_min = abs(array[left] + array[right]) left.. 2023. 2. 18.
[Python] 백준 2512 예산 🧑‍💻 [Python] 백준 2512 예산 Silver 3 - 이진 탐색 예산 요청이 리스트로 주어진다. 그리고 국가가 사용할 수 있는 예산이 주어진다 요청 된 모든 예산들이 국가가 사용할 수 있은 예산 안에 들어가야 한다 그러기 위해서, 상한액을 정해서, 요청 리스트 안에 있는 예산들을 수정한다 코드 N = int(input()) array = list(map(int, input().split())) budget = int(input()) array.sort() left, right = 0, array[-1] if sum(array) 2023. 2. 18.
[Python] 백준 1967 트리의 지름 🧑‍💻 [Python] 백준 1967 트리의 지름 Gold 4 - DFS 두 노드 사이의 가중치들을 더했을 때에 가장 큰 숫자를 출력하는 것 여기서 1의 기준에서 가중치가 제일 큰 노드를 구한다 그 다음, 가중치가 제일 큰 노드를 시작으로 DFS를 하여, 제일 큰 가중치를 구한다 여기서 DFS를 하면 어디서든, 제일 끝에 있는 자식 노드에 가게 된다 문제풀이 첫 DFS를 한 후에,visited 리스트 다시 초기화 시켜야 한다 second_index = visited.index(max(visited))을 통해서 두번째 DFS를 할 때에, 시작 점을 찾는다 코드 import sys sys.setrecursionlimit(10 ** 9) def dfs(start, weight): for node, wei in.. 2023. 2. 16.

티스토리툴바