그래프, BFS/DFS 문제https://www.acmicpc.net/problem/21736 💡 풀이코드 (성공 - DFS 1)import sys sys.setrecursionlimit(10 ** 9) r, c = map(int, sys.stdin.readline().split())graph = []start = []visited = [[False] * c for _ in range(r)]dy = [0, -1, 0, 1]dx = [1, 0, -1, 0]cnt = 0for i in range(r): l = list(sys.stdin.readline().strip()) for j in range(c): if l[j] == "I": start.append((i,..

우선순위 큐 문제https://www.acmicpc.net/problem/1202  💡 풀이코드 (실패 - 10% 시간초과)# 10% 시간초과 코드 O(N*K) 코드, 이진탐색 내부의 pop(left) 때문에 O(N * logK)가 될 수 없음# 현재는 높은 가격의 보석부터 처리하는 코드 import sys import heapq N, K = map(int, sys.stdin.readline().split())jewel = []bag = []for _ in range(N): weight, price = map(int, sys.stdin.readline().split()) heapq.heappush(jewel, (-price, weight))for _ in range(K): weight ..

DP / Knapsack 문제https://www.acmicpc.net/problem/7579 냅색(Knapsack) 알고리즘간단하게 말하면, 한 도둑이 훔치는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.출처: 위키피디아 냅색 알고리즘은 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나눈다. 담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 분할가능 배낭문제(Fractional Knapsack Problem)담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제(0-1Knapsack Problem)해당 문제는 0-1 배낭문제의 경우다.  일반적인 배..

DP / Knapsack 문제https://www.acmicpc.net/problem/12865  냅색(Knapsack) 알고리즘 냅색 알고리즘은 대표적인 동적 계획법(DP) 문제 중 하나로, 주어진 가방에 담을 수 있는 무게 제한과 각 물건의 가치를 고려하여 최대한의 가치를 얻는 문제다. 이 알고리즘은 크게 두 가지 유형으로 나뉜다. 1. 분할 가능한 배낭 문제 (Fractional Knapsack): 물건을 부분적으로 쪼개어 담을 수 있는 경우에 해당한다.각 물건의 가치를 무게로 나눈 값(즉, 무게 대비 가격 비율)을 기준으로 물건을 정렬하여 높은 비율 순서대로 가방에 담는다.가방의 남은 용량보다 물건의 무게가 크다면, 물건을 잘라서 넣는다. 이렇게 하면 쉽게 최대 가치를 얻을 수 있다.2. 0-1 ..

[API Gateway Service란?]API GatewayAPI Gateway 서비스는 사용자가 설정한 라우팅 설정에 따라 각각의 엔드포인트로 클라이언트를 대신하여 요청하고, 응답을 받으면 클라이언트한테 다시 전달해주는 Proxy 역할 수행시스템의 내부 구조는 숨기고, 외부에 요청에 대해 적절한 형태로 가공해서 응답할 수 있다는 장점[그림 설명]마이크로서비스가 3개 있다 가정시, 클라이언트 사이드에서 마이크로서비스를 직접 호출하는 그림 즉, 클라이언트 측에서 마이크로서비스의 주소를 직접 이용하여 요청새로운 마이크로서비스가 추가되거나 기존에 있던 마이크로서비스의 주소가 변경 되었다고 가정해도 마이크로서비스 자체가 독립적으로 빌드, 배포되는 장점But, 클라이언트 사이드에서 마이크로서비스의 엔드포이트(주..

그래프, BFS/DFS 문제https://www.acmicpc.net/problem/1967 트리의 지름 트리의 지름이란?어떤 두 노드를 선택해서 당겼을 때, 가장 길게 늘어나는 경우의 두 정점 사이의 거리를 말한다.즉, 트리의 지름이란 트리 상에서 가장 먼 거리를 가지는 두 정점 사이의 경로이다.위의 그래프에서 9 노드와 12 노드의 사이의 거리는 45이며, 이 경로가 트리의 지름이 된다. 트리의 지름을 구하는 순서1. DFS를 통해 임의의 정점(x)로부터 가장 먼 정점(y)를 구한다.2. DFS를 통해 구해진 (y) 정점으로부터 가장 먼 정점(z)를 구한다.3. (y) 정점과 (z) 정점을 잇는 경로가 트리의 지름이 된다.  💡 풀이코드 (성공 - DFS)# DFS# visited 초기화 주의 im..