2023년 9월 8일 알고리즘 문제풀이 문제 1 백준 9273 문제 링크 1차 시도 나의 생각 결국 두 자연수 a,b에 대하여 1/n = 1/a + 1/b 가 성립해야 한다고 생각했다. 따라서 이 수식을 고쳐서 b = na/(a-n) 으로 만들었다. 이 함수를 a,b 에 대한 함수로 이해해보자. b-n = (n^2)/(a-n). 유리함수중에 분수 함수라고 할 수 있다. 점근선은 x =n, y = n이다. 아래와 같은 함수이다. 이 그래프에서 x,y가 모두 자연수인 함수 위 좌표를 찾았다. x가 0일 때 y가 n이다. x가 1이면 y는 자연수일 수 없다. 따라서 x가 2부터 1씩 증가하다가 y값이 음수면 멈췄다. ...
2023년 9월 7일 알고리즘 문제풀이 문제 1 백준 2748 문제 링크 1차 시도 나의 생각 기본적인 다이나믹 프로그래밍 문제였다. 재귀를 이용하면 시간초과가 되니 정의한 함수를 저장하는 배열을 만들어서 이를 참조하자. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import sys n = int(sys.stdin.readline()) dp = [0 for _ in range(n+1)] dp[1] = 1 def fibo(x): if x == 0: return dp[0] elif x == 1: return dp[1] else: if dp[x]: return dp[x] else: dp[x] = fibo(x-1) + fibo(x-2) return dp[x] print(fibo(n)) 문제 2 백준 1904 문제 링크 ...
5. 확률적 분석과 랜덤화된 알고리즘 5.1 고용 문제 직업 소개소에서 면접자를 추천 받으려면 적은 소개료를 지불해야 한다. 소개받아 면담한 후 일을 잘할 수 있는 사람이면 해고하고 새로운 지원자를 고용하면 된다. 고용하면 많은 소개료를 지불해야 한다. 이 떄 비용을 알고자 한다. Hire-ASSISTANT(n) 1 2 3 4 5 6 best = 0 // 0번은 가장 낮은 점수를 갖는 가상의 지원자 for i = 1 to n 지원자 i를 면접한다. if 지원자 i가 지원자 best보다 나은가? best = i 지원자 i를 고용한다. 위 의사코드가 비용을 의미한다. ...
2023년 9월 4일 알고리즘 문제풀이 문제 1 백준 1167 문제 링크 1차 시도 나의 생각 입력값을 list로 받은 후 가장 앞인 0번 index는 어떤 정점의 정보인지를 나타낸다고 생각하였고 그 이후 둘 씩 짝지어서 도착 정점과 거리로 설정하였다. 이를 바탕으로 인접리스트를 만들고 index를 2씩 뛰어넘어 -1이 나오면 더이상 정보가 없으므로 다음 줄로 넘어갔다. 이후에는 두 점간의 거리를 bfs를 통해 탐색하도록 하였다. 모든 점간의 거리를 찾아 최댓값을 도출하였다. 하지만 메모리,시간초과가 뜬다… 다찾아보면 안되나보다. ...
2023년 9월 2일 알고리즘 문제풀이 문제 1 백준 1948 문제 링크 1차 시도 나의 생각 위상정렬을 이용해 풀고자 하였다. 단 시작지점은 진입차수가 0인 것이 문제의 조건이므로 큐에 시작도시를 넣고 반복하였다. 결국 도착지에 갈때까지 비용을 계속 더해주고, 간선을 이용할 떄마다 카운트 해주었다. 예제를 입력했을 떄 결과값이 실제 정답보다 크게 나오기도 했고, 경로 탐색이 내가 예상한대로 되지 않았다. 아무래도 문제를 제대로 이해하지 못한채 그냥 위상정렬만 적용해서 해결하지 못하고 있는것 같다. 애초에 이 문제를 왜 위상정렬로 풀어야 하는지도 모르겠다.. 공부해봐야겠다. ...
2023년 9월 1일 알고리즘 문제풀이 문제 1 백준 2252 문제 링크 1차 시도 위상정렬에 대한 개념을 다 까먹어서 어떻게 풀지 감이 안왔다.. 해서 위상정렬을 공부해보고 풀었다. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말하면 순서가 정해져있는 작업을 차례대로 수행할 때 순서를 결정하는 방법이다. 이번 문제도 어떤 학생들은 순서에 맞게 배열해야 하니 위상 정렬 문제로 풀 수있다. 위상 정렬의 과정은 다음과 같다. 방향이 있는 간선들의 정보가 주어지면 인접그래프를 만든다. 정점의 번호를 index로 하는 배열을 만든 후 해당 정점이 도착지가 되는 간선이 있을 떄마다 정점의 값을 1 올린다. 이 정점의 값이 진입차수를 의미한다. 해당 정점으로 진입하는 간선이 몇개인지를 나타내는 것이다. 위 과정이 완료되면 값이 0인 정점은 큐에 삽입한다. 큐에서 한 정점씩 꺼내어 해당 정점과 연결된 간선을 모두 제거한다. 이 과정에서 값이 0이 된 정점은 큐에 삽입하고 과정을 반복한다. 큐에서 꺼내지는 순서가 작업의 순서이다. 이 문제에 대입해보면, 문제의 입력값에서 순서가 있는 학생이 주어진다. 학생을 정점이라 생각하고 배열의 선후관계를 간선의 방향이라고 생각하면 된다. 코드는 다음과 같다. ...
2023년 8월 31일 알고리즘 문제풀이 문제 1 백준 16439 문제 링크 1차 시도 나의 생각 세 종류의 치킨을 고르는 것은 조합(Combination)을 이용했다. 근데 라이브러리를 사용하지 않고 3중 for문으로 구현했다. 라이브러리 쓰는 법도 익혀야지.. 어쩄든 한 사람은 세 종류의 치킨 중 선호도가 가장 높은 것으로 점수를 나타내니 최소힙을 이용하되 음수로 바꾼 후 넣은 후 heappop하여 점수를 구했다. 그리고 각 조합 때마다 현재까지 최고 점수랑 비교하며 업데이트 해주었다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 import sys from heapq import heappop, heappush n, m = map(int, sys.stdin.readline().split()) graph = [] for _ in range(n): graph.append(list(map(int, sys.stdin.readline().split()))) def cal(): max_val = 0 for i in range(m): for j in range(m): if j == i: continue for k in range(m): ans = 0 if k == i or k == j: continue for person in range(n): arr = [] heappush(arr, -1*graph[person][i]) heappush(arr, -1*graph[person][j]) heappush(arr, -1*graph[person][k]) tmp = heappop(arr) tmp *= -1 ans += tmp max_val = max(max_val, ans) return max_val answer = cal() print(cal()) 문제 2 백준 1939 문제 링크 ...
4.분할정복 4.5 점화식을 풀기 위한 마스터 방법 T(n) = aT(n/b) + f(n) 마스터 방법은 위와 같은 점화식을 푸는 기본 지침을 제공한다. 여기서 a≥1, b>1 인 상수이고 f(n)은 점근적으로 양인 함수다. 마스터 정리 정리 4.1 (마스터 정리) a≥1, b>1 인 상수이고 f(n)이 양의 함수라 하고, 음이 아닌 정수에 대해 T(n)이 다음 점화식에 의해 정의된다고 하자. T(n) = aT(n/b) + f(n) 여기서 n/b는 ⌈n/b⌉ 또는 ⌊n/b⌋을 뜻하는 것으로 이해한다. 그러면 T(n)의 점근적 한계는 다음과 같다. ...
2023년 8월 28일 알고리즘 문제풀이 문제 1 프로그래머스 숫자 짝꿍 문제 링크 1차 시도 나의 생각 두 문자열에서 각 숫자가 몇번 등장하는 지를 확인한다. 사용할 수 있는 수는 각 숫자의 등장 횟수 중 적은 쪽이다. 예를 들어, 숫자 5가 X에서는 3번, Y에서는 7번 등장한다면 짝꿍을 위해 숫자 5는 3번 쓰일 수 있다. 짝꿍은 가장 큰 수를 나타내야 하므로 사용 가능한 정수 중 큰것부터 소모하면 된다. 사용 가능한 숫자가 0만 있을 경우와 아무것도 없을 경우도 조건문을 통해 따로 체크한다. ...
2023년 8월 26일 알고리즘 문제풀이 문제 1 프로그래머스 전력망을 둘로 나누기 문제 링크 1차 시도 나의 생각 한 간선이 없어질 때마다 값을 모두 구한 후 가장 절대값이 작을 때를 찾았다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 from collections import deque def solution(n, wires): answer = n d = len(wires) for i in range(d): arr = deque() arr.append(0) graph = [[] for _ in range(n)] visited = [False for _ in range(n)] visited[0] = True for j in range(d): if j == i: continue else: a,b = wires[j] graph[a-1].append(b-1) graph[b-1].append(a-1) while arr: now = arr.popleft() for x in graph[now]: if not visited[x]: visited[x] = True arr.append(x) cnt = visited.count(True) cnt = abs(n-2*cnt) answer = min(answer,cnt) return answer 문제 2 프로그래머스 쿼드압축 후 개수 세기 문제 링크 ...