2023년 9월 9일 알고리즘 문제풀이 문제 1 백준 12865 문제 링크 1차 시도 나의 생각 입력값을 받을 때 무게 제한보다 무거운 물건은 아예 받지 않도록 조건을 추가한다. 큐를 이용한 최소힙을 통해 물건의 무게와 가치를 원소로 하는 배열에서 무게가 낮은 순서로 하나씩 pop한다. 배낭을 나타내는 배열에 [0,0]을 추가하여 아무것도 없는 상태를 만든다. pop할 때마다 기존 가방에 있는 것에 현재 물건을 더한 것을 추가해준다. 이 방식이면 원소갯수가 2배씩 늘어난다. 비어있는것 1개 => 첫번째 물건 더한것과 안더한것 2개 => 앞의 2개에 각각 두번째 물건을 더한것과 안더한 것 해서 총 4개 => 8개 => … ...
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 문제 링크 ...
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 문제 링크 ...
2023년 8월 28일 알고리즘 문제풀이 문제 1 프로그래머스 숫자 짝꿍 문제 링크 1차 시도 나의 생각 두 문자열에서 각 숫자가 몇번 등장하는 지를 확인한다. 사용할 수 있는 수는 각 숫자의 등장 횟수 중 적은 쪽이다. 예를 들어, 숫자 5가 X에서는 3번, Y에서는 7번 등장한다면 짝꿍을 위해 숫자 5는 3번 쓰일 수 있다. 짝꿍은 가장 큰 수를 나타내야 하므로 사용 가능한 정수 중 큰것부터 소모하면 된다. 사용 가능한 숫자가 0만 있을 경우와 아무것도 없을 경우도 조건문을 통해 따로 체크한다. ...
2023년 8월 25일 알고리즘 문제풀이 문제 1 백준 3055 문제 링크 1차 시도 나의 생각 물을 따로 생각하지 말고 이미 방문해서 방문할 수 없는 곳으로 처리한다면 크게 복잡하지 않을 수도 있겠다는 생각을 했다. 따라서 고슴도치가 이동할 곳을 BFS로 탐색하되, 방문처리를 통해 물이 있는 곳과 바위가 있는 곳을 표시하면 되겠다고 생각했다. 주어진 예시는 답을 출력했는데, 고슴도치가 다음 턴에 물이 찰 곳으로 이동할 수 없는 조건이 적용되지 않았다. 따라서 이동할 수 없는 경우가 누락되어 오답처리되었다. ...
2023년 8월 24일 알고리즘 문제풀이 문제1 백준 1916 문제 링크 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 29 30 31 32 33 34 import sys from heapq import heappop, heappush n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) graph = [[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(m): s, a, c = map(int, sys.stdin.readline().split()) graph[s][a] = c start, arrive = map(int, sys.stdin.readline().split()) def search(x): cost = [10**9 for _ in range(n+1)] cost[x] = 0 arr = [] heappush(arr,[0, x]) while arr: price, now = heappop(arr) if price > cost[now]: continue for i in range(1, n+1): if not graph[now][i]: continue new_money = price + graph[now][i] if new_money < cost[i]: cost[i] = new_money heappush(arr,[new_money, i]) return cost ans = search(start) print(ans[arrive]) 2차 시도 나의 생각 원인을 찾아냈다. 나는 두 도시간의 비용을 인접행렬로 표현했다. 즉 행렬의 값이 두 도시의 이동 비용이다. 하지만 문제에서 각 도시 간의 노선이 하나라는 보장이 없다.. 그래서 두 도시간의 버스 비용이 중복해서 주어진다면 내 코드는 가장 마지막에 입력된 것만 나타내게 된다. 하지만 먼저 입력된 버스비용이 더 작다면? 내 코드에선 정답을 도출할 수 없었다. ...