🌊

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 투 포인터 문제를 오랜만에 풀다 보니 가장 기본이 되는 포인터 이동 조건을 제대로 고민하지 못했다. 두 용액 합의 절댓값을 기준으로 더 작아지면..

1️⃣ 기본 개념서로소 집합(Disjoint Set) 자료구조를 관리하는 알고리즘이다. 두 가지 연산을 수행한다.Find: 특정 원소가 속한 집합의 대표 원소를 찾는다.Union: 두 원소가 속한 집합을 하나의 새로운 집합으로 통합한다.집합을 트리 구조로 표현하며 트리의 루트 노드가 집합의 대표 원소가 된다. 2️⃣ 시간 복잡도$ O(\alpha(N)) $ 로, N의 크기에 관계없이 매우 빠른 연산이 가능하다$\alpha(N)$은 아커만 함수(Ackermann function)의 역함수이다. 3️⃣ 동작 과정초기화: 모든 원소에 대해 자기 자신을 부모로( $\text{parent}[i] = i$ ) 설정한 N개의 집합을 만든다Find 동작: 원소의 루트를 찾기 위해 $\text{parent}[x]$를 따..

https://school.programmers.co.kr/learn/courses/30/lessons/12980📌 문제 접근N번째 칸까지 가면서 순간이동 또는 점프를 이용할 수 있다.점프는 이동한만큼 건전지 사용량이 증가하고, 순간이동은 현재까지 이동한 칸수*2의 위치에 도달한다.문제를 읽으면서 DP를 이용하면 된다고 생각했다. 🧐 첫 번째 풀이: DP (실패)너무나 당연하게 통과할 줄 알았는데 시간초과가 났다 ㅠㅠdef solution(n): dp = [float('inf')]*(n+1) dp[0] = 0 for i in range(n): # 점프 dp[i+1] = min(dp[i]+1, dp[i+1]) # 순간이동 if 0 제한..

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..

프로그래밍에서 $0.1 + 0.2$을 계산하면 $0.30000000000000004$이 나온다. 그 이유는 무엇일까?결론부터 말하자면 부동소수점 때문이다!컴퓨터는 내부적으로 이진법을 사용해서 표현하고 있다.정수의 경우 이진수로 정확하게 표현할 수 있지만 소수 부분은 조금 다르다.📌이진법 소수 표현먼저 $0.625$를 2진수로 바꿔보자.0.625 = 1/2 + 0/4 + 1/8 → 0.101(2)정확히 가능하다. 하지만 $0.1$의 경우에는 조금 다르다.0.1 = 0.0001100110011001100...(2)0.1에 가까워지기만 할 뿐 정확히 도달하지 못한다. ✅ 오차가 생기는 이유컴퓨터는 메모리에 유한한 비트만 저장할 수 있다.따라서 2진수로 무한 소수가 되어버리는 0.1, 0.2와 같은 수는 가까..

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..

💡 개발 배경매일 알고리즘 문제를 고르기가 너무 귀찮아서 랜덤으로 추천해주는 사이트가 있다면 좋겠다는 생각을 하다가그냥 내가 만들어버리자!!라는 마음으로 시작하게 되었다.구현한 사이트는 여기 처음에는 백준 온라인 저지의 API를 활용하고 싶었는데 공식적으로 제공되지 않았다. 대신 solved.ac API를 활용했다. 여기서 문제가 발생했다..클라이언트에서 fetch로 Solved.ac API를 호출하려 하니 Network Error가 발생하는 것 ㅠ알아보니 CORS가 적용되어 있어서 차단되고 있는 것 같았다. 즉, 클라이언트에서 요청을 바로 보낼 수 는 없다는 것이었다! 📌 처음 구상: Express.js 백엔드 구축처음에는 Express.js 서버를 구축하면 된다고 생각을 했다. 구현한 코드는 👇..

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