ayeongjin 님의 블로그

최소 스패닝 트리 (MST)란?최소 스패닝 트리(MST, Minimum Spanning Tree)는 그래프 이론에서 중요한 개념 중 하나로, 주어진 그래프에서 모든 정점을 연결하는 트리 중에서 가중치의 합이 최소인 트리를 의미한다.간단히 말해, 각 정점들이 연결되어 있으며, 연결된 모든 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제최소 스패닝 트리의 특징트리 구조:MST는 반드시 트리 형태 (트리 : 사이클이 없는 연결된 그래프)트리의 특성상, N개의 정점이 있을 경우, 간선의 수는 항상 N-1최소 가중치:MST는 모든 간선의 가중치 합이 최소가 되어야 한다. (ex. 가중치가 의미하는 것 : 도로의 비용, 네트워크 연결의 비용 등)그래프 연결:MST는 그래프에 있는 모든 정점들을 연결해야 하므로,..

https://www.acmicpc.net/problem/13460 문제 조건 1. 보드 상하좌우로 욺직여서 구슬 이동2, 빨간구슬만 빼내기3. 각 단계마다 네방향으로 기울이며 두 구슬을 동시에 이동3-1. 파란구슬이 구멍에 빠지면 실패3-2. 빨간구슬이 구멍에 빠지면 성공4. 10회 반복 후, 성공 못하면 -1 접근 방법 # 문제 1먼저 상하좌우로 이동하며 그때마다 턴을 반복해야한다는 건 이해했지만, 두 개의 구슬이 같은 위치에 겹치면 어떻게 처리해야할지 생각하는 데 오래걸렸다.그래서 구슬의 위치와 현재 방향을 바탕으로 어떤 구슬이 먼저 움직어야하는지 계산할까 생각했지만 너무 복잡해서 포기했다.위의 방법을 고민하던 중, 어떤 구슬이 먼저 움직어야하는지 계산을 하지 말고 일단 그냥 두 개의 구슬을 똑같..

https://www.acmicpc.net/problem/1522 문제 조건은1. 모든 a를 한곳에 모아야한다2. 문자열은 원형 구조라 처음과 끝이 이어져있다. 따라서 문제 풀이는1. 최종 완성되어야할 연결된 a의 수 구하기2. 문자열은 원형구조이므로 두배로 이어 붙이기3. 문자열 i부터 i+a 까지 슬라이싱해서 그 안에 있는 b의 수의 최솟값 구하기 # 성공 코드const str = require("fs").readFileSync("/dev/stdin").toString().trim();const aCnt = [...str].filter((c) => c === "a").length;const strDouble = str + str;let result = Number(Infinity);for (let ..

https://www.acmicpc.net/problem/2240 이문제를 풀면서 가장 어려웠던 점은 dp 테이블을 어떻게 설계해야하는지에 대한 고민이었다.처음에는 dp 테이블에 저장할 값을1. T 시간만큼 순회하는 동안 현재 시간까지의 이동 수2. 현재 위치3. 그 이동 수와 현재 위치에 따라 얻을 수 있는 최대 자두의 수이렇게 저장하려고 생각했다.하지만 이동 수에 따라서 현재 나무 위치와 자두 최댓값을 어떻게 점화식을 세울지 너무 헷갈렸다.그래서 처음부터 다시 생각했다. 먼저1. 처음 위치는 똑같이 1번 나무에서 시작2. 만약에 3번 이동했다면, 1 -> 2 -> 1 -> 2 로 2번 나무2-2. 따라서 현재 나무 위치를 dp 테이블에 저장할 필요는 없음 (이동 횟수에 따라서 알 수 있으므로)3. 그..

https://www.acmicpc.net/problem/17822 매 T 마다 반복되는 동작은1. 원판 회전2-1. 인접한 값 중 서로 같은 값이 있으면 그 값들 삭제2-2. 인접하면서 같은 수가 없는 경우에는 원판 수의 합보다 작은 수는 += 1, 큰 수는 -= 1 그래서 세가지 함수를 만들었다.  1. 원판 회전def turn(x, d, k): # x의 배수인 원판을 d(0: 시계, 1: 반시계) 방향으로 k칸 회전 for i in range(x, N+1, x): if d == 0: # 시계 방향 circles[i-1] = circles[i-1][-k:] + circles[i-1][:-k] else: # 반시계 방향 circ..

https://school.programmers.co.kr/learn/courses/30/lessons/42584 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 비슷한 문제로 백준에서 17298번 오큰수 풀었던 기억이 났다.그때도 스택으로 풀었던 거 같아서 이번에도 스택으로 풀어보려고 했는데 꽤 시간이 걸렸다.오큰수는 배열을 거꾸로 순회하면서 스택에 int 하나만 저장하고 오큰수가 될 수 없는 값을 pop 하면서 풀이했는데,이 문제는 주식가격 유지 시간을 구해야했기 때문에 순서대로 순회하면서 가격과 idx를 튜플로 스택에 append했다. # 스택def solution(prices): n = le..

https://www.acmicpc.net/problem/17143 매 초마다 기억해야할 것1. 위치별 상어가 몇마리 들어있는지 (가장 큰 상어가 잡아먹기위해)2. 각 상어의 속도, 방향, 크기 그래서 낚시터 배열 mp 와 상어의 속도, 방향, 크기를 저장할 sharks 딕셔너리를 만들었다. 상어 정보 저장mp = [[[] for _ in range(C)] for _ in range(R)]sharks = {}direction = [(-1, 0), (1, 0), (0, 1), (0, -1)] # 위, 아래, 오른쪽, 왼쪽for i in range(M): r, c, s, d, z = map(int, input().split()) # 위치, 속력, 이동방향, 크기 heappush(mp[r-1][..

https://www.acmicpc.net/problem/2212 센서 설치 구간을 중점으로 반지름이 일정하게 센서가 수신된다는 뜻인줄알고 예제를 이해하기 어려웠다.그래서 센서 설치 구간부터 양옆으로 거리가 일정하지 않아도 된다면 예제가 맞길래 그렇게 이해하고 풀었다. [예제 1]621 6 9 3 6 7 여기서 센서의 좌표를 정렬하면1 3 6 6 7 9이렇게 되고 이때 최솟값은 (1 3) (6 6 7 9) 이렇게 묶으면 거리의 합이 5로 최솟값이 된다.이때 K개의 묶음의 수를 만들 수 있는 방법은 센서 배열에서 K-1번 자르면(예제에서는 정렬 후 3과 6 사이)K개의 묶음이 나온다고 생각했다. 어디를 자를지 생각하다가 조합으로 모든 경우의 수를 구할까 했는데, 시간 초과가 날 것 같았다.그래서 다시 생각..

이분 그래프(Bipartite Graph) 1. 이분 그래프란?이분 그래프는 정점 집합을 두 그룹으로 나눌 수 있는 그래프다. 이분그래프 조건정점을 두 집합 U, V로 나누었을 때 모든 간선은 반드시 U의 정점과 V의 정점 사이에만 존재해야 한다.(즉, 같은 집합에 있는 정점끼리는 연결되면 안 됨) 그래프를 색칠하는 관점에서 보면 두 가지 색만으로 인접한 정점끼리 서로 다른 색을 칠할 수 있다면 이분 그래프 완전 이분 그래프 부분 연결 이분그래프 불완전 이분그래프 예시친구 관계 그래프에서 "남자 ↔ 여자"만 연결되어 있는 구조체스판처럼 흑백이 번갈아 연결되어 있는 구조2. 이분 그래프 판별 방법 (BFS / DFS)이분 그래프인지 판별하는 대표적인 방법은 그래프 탐색 (BFS 또는 DFS) 를 활용..

https://www.acmicpc.net/problem/19238 처음에는 모든 출발지와 도착치의 좌표가 겹치는 경우가 없다고 생각해서 출발지와 목적지를 전부 mp에 대입해버렸다.그리고 택시의 처음 위치부터 시작해서 너비우선탐색으로 가장 가까운 출발지점을 찾고, 해당 번호의 도착지를 찾은 후, 연료와 택시 위치를 갱신해서 풀었다.그렇게 해서 1퍼센트에서 틀렸습니다 떴다. # 실패 코드 1'''현재 위치에서 가장 가까운 손님에게 가기 (거리가 같을 경우 행번호 -> 열번호 순서로 탐색)현재 택시와 같은 위치라면 거리 = 0한칸 이동마다 연료 1 소모목적지 도착시 승객 이동 중 소모한 연료의 두배 충전이동중 연료 바닥나면 영업 종료 (도착과 동시에 연료 바닥날시에는 이동 성공)'''from collecti..