본문 바로가기

백준55

Udemy : 알고리즘 DFS, BFS, 백트래킹 Udemy : 알고리즘 DFS, BFS, 백트래킹 udemy 알고리즘 코딩 테스트 그래프 자료구조 그래프는 노드와 링크로 이루어진 자료구조다 노드는 점들이고, 노드를 이어주는 링크, Edge 또는 간선이라고 한다 SNS / 메신저 관계도를 그래프로 만들 수 있다 지도 / 네비게이션 같이 그래프를 실생활에 사용될 수 있다 무방향 또는 방향 그래프로 만들 수 있다 무방향이나 양방향 그래프는 동일한 개념이다 트리 자료구조 순환성이 없는 무방향 그래프다 코드를 그래프로 나타날 때에는 인접 리스트와 행열을 만들 수 있다 연결 행 연결 리스트 DFS (Depth First Search) 깊이 우선 탐색 스택 또는 재귀를 사용해서 구현을 한다 DFS는 완전 탐색이다 BFS (Breadth First Search) 너.. 2023. 3. 13.
[Python] 백준 3107 IPv6 🧑‍💻 [Python] 백준 3107 IPv6 Gold 5 - 구현 이 문제는 IPv6를 고려해서, 상황들을 생각해서 코드를 짜면 되는 것이다 특히 ::를 집중적으로 생각해야 한다 :: 만 없었다면 그냥 0만 채우면 되는 문제 예) 25:09:1985:aa:091:4846:374:bb 같은 경우 그냥 0025:0009:1985:00aa:0091:4846:0374:00bb으로 바꿔주면 된다 그래서 입력을 먼저 받을 때에 : 기준으로 나눠서 리스트에 넣는다 그리고 그 리스트 안에 있는 요소들을 순회한다 만약 중간에 ::가 있으면, 리스트에는 ''으로 반환되어 있을 것이다 리스트 길이가 8이면 그대로 0만 채워 넣으면 된다 하지만 리스트 길이가 8이 아니면, ::를 채워 넣어줘야 한다 리스트 길이를 8로 맞출.. 2023. 3. 12.
[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.
[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.

티스토리툴바