Hi

https://www.acmicpc.net/problem/2470📌 문제 접근서로 다른 두 용액을 선택하여 합이 0에 가장 가까운 두 수를 찾는 문제이다.입력 크기를 보면 전체 용액의 수 N은 2 이상 100,000 이하 이기 때문에 완전 탐색으로 풀 경우 시간 초과가 발생한다.따라서 투포인터를 사용해야겠다고 생각했다.🧐 첫 번째 풀이N = int(input())arr = list(map(int, input().split()))arr.sort()L = 0R = N - 1mx = float('inf')mxL = arr[L]mxR = arr[R]while L 투 포인터 문제를 오랜만에 풀다 보니 가장 기본이 되는 포인터 이동 조건을 제대로 고민하지 못했다. 두 용액 합의 절댓값을 기준으로 더 작아지면..

https://www.acmicpc.net/problem/20055 📌 문제 접근보자마자 구현문제라고 생각을 했다. 전체 길이 2N의 컨베이어에서 1번은 로봇이 올라가는 위치, N번은 로봇이 내려가는 위치이다.동작과정은 아래와 같다.벨트와 벨트 위 로봇이 함께 한 칸 회전한다.가장 먼저 올라간 로봇부터 순서대로, 이동할 수 있다면 한 칸 이동한다.이동 조건: 이동하려는 칸에 로봇이 없고, 내구도가 1 이상 남아 있어야 한다.올리는 위치의 내구도가 남아 있다면 새로운 로봇을 올린다.내구도가 0인 칸이 K개 이상이면 과정을 종료한다. 아니면 다시 1번으로 돌아간다. 💡구현 아이디어처음엔 두 가지 방법을 생각했다.윗줄/아랫줄 컨베이어를 나눠서 따로 관리인덱스를 직접 이동시키면서 관리하지만 구현이 생각보다..

https://www.acmicpc.net/problem/2573📌 문제 접근빙산은 1년 동안 동서남북 방향으로 접한 바닷물 칸수만큼 줄어든다.빙산이 두 덩어리가 됐을 때가 몇 년 후 인지 구하는 문제이다. 단 두 덩어리가 되지 못하면 0을 출력해야 한다.문제를 읽으며 dfs나 bfs로 풀면 되겠다고 생각했다. 🧐 첫 번째 풀이: DFS (실패)처음에는 DFS로 연결된 빙산을 탐색했다.def dfs(x, y): visited[x][y] = 1 for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]: nx, ny = x + dx, y + dy if 0 = 2: break if cnt == 0: year..

https://www.acmicpc.net/problem/2096 📌 문제 접근원룡이가 한줄씩 내려가면서 얻을 수 있는 최대 점수와 최소 점수를 구하는 문제이다.DP를 이용해서 풀면 된다고 생각했다. 🔍 첫 번째 풀이 (실패)처음에는 이중 for문 + 2차원 DP 테이블을 사용했다.N = int(input()) arr = [[0] + list(map(int, input().split())) + [0] for _ in range(N)] mxdp = [[0] * (N + 2) for _ in range(N)] mxdp[0] = arr[0] for i in range(1, N): for j in range(1, N + 1): mxdp[i][j] = max(mxdp[i - 1][j - 1], ..

https://www.acmicpc.net/problem/1916 📌 문제 접근문제를 보자마자 며칠 전에 푼 택배 배송이 떠올랐다. 도시의 개수 N과 버스 노선 M이 주어지고, 각 버스 노선은 출발 도시, 도착 도시, 비용으로 표현된다. 목표는 특정 시작 도시에서 도착 도시까지 드는 최소 비용을 구하는 것이다. 즉, 다익스트라를 이용한 최단 거리 문제로 풀 수 있다.🔍 문제 풀이import heapqN = int(input()) # 도시 개수M = int(input()) # 버스 노선 개수# 인접 리스트 그래프graph = [[] for _ in range(N + 1)]for _ in range(M): s, e, cost = map(int, input().split()) graph[s..

https://www.acmicpc.net/problem/5972 📌 문제 접근1번 헛간에서 출발해 N번 헛간까지 이동하는 과정에서, 각 길을 지날 때마다 소에게 줄 여물의 비용이 발생한다. 목표는 여물의 총합이 최소가 되는 경로를 찾는 것이다. 즉, 최단 경로 문제로 풀면 된다.간선의 가중치가 모두 양수이므로 다익스트라 알고리즘을 적용할 수 있다N과 M의 범위가 1 ~ 50,000이기때문에 우선순위 큐를 이용하여 구현했다.[Python] 다익스트라(Dijkstra) 알고리즘 [Python] 다익스트라(Dijkstra) 알고리즘💡 기본 개념최단 경로 알고리즘 중 하나시작 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이다.방향그래프와 무방향그래프에서 사용할 수 있다. 💡 시간 복잡도V: 정점..

https://www.acmicpc.net/problem/11725   📌  문제 접근처음에 트리를 그린 후 부모를 찾으려고 하니, 기준이 없어서 도대체 부모를 어떻게 찾아야하나 한참 헤멨다.그러나 문제를 다시 읽어보니"루트는 1이다." 라는 조건이 있었다. (문제를 잘 읽자 .. )이걸 기반으로 1번 노드부터 탐색했다. 🔍 문제 풀이1. DFS 처음에는 DFS로 풀었다. 현재 노드에서 연결된 노드로 이동하면서,아직 방문하지 않은 노드에 대해 방문처리 + 부모 저장을 동시에 진행한다.하지만  RecursionError (런타임 에러) 가 발생해서 재귀제한을 늘려줘야했다. import syssys.setrecursionlimit(10**6)def dfs(n): if n > N+1: r..

https://www.acmicpc.net/problem/19949 🔹 접근 방법백트래킹을 이용해서 문제를 풀어야겠다고 생각했다.답을 선택하면 visited에 답을 저장해두고 3개 연속으로 같은 정답을 선택하지 않도록 했다.또한 답을 선택할때 정답일 경우 점수를 1점씩 올렸다.   🔹 코드 구현def dfs(n, score): global cnt # 10문제를 모두 푼 경우 if n >= len(answers): if score >= 5: cnt += 1 # 5개 이상 정답을 맞췄을 경우 카운트 증가 return for i in range(1, 6): # 1~5 중에서 선택 # 연속된 3개의 답이 같은 경우 제외 ..