개발하는 리프터 꽃게맨입니다.

스패닝 트리 임의의 그래프가 있다고 생각해봅시다. 스패닝 트리란 부분 그래프 중 하나로 다음과 같은 조건을 만족해야 합니다. 1) 그래프 내의 모든 정점을 포함하는 부분 그래프 2) 사이클이 없는 그래프 이런 그래프를 신장 트리 (혹은 스패닝 트리)라고 합니다. 스패닝 트리를 찾는 것은 매우 단순합니다. 단순 BFS, DFS를 하면 스패닝 트리를 찾을 수 있죠. 그런데 가중치 그래프의 경우를 생각해봅시다. 모든 노드를 다 방문하는데 비용이 다 다르다면, 아무래도 최소 비용으로 방문하는 것이 가장 좋겠죠? 그래서 중요하게 다뤄지는 알고리즘이 최소 신장 트리 (최소 스패닝 트리) 이며, 이는 모든 노드를 방문하는 최소 비용의 신장트리를 찾는 것을 목적으로 합니다. 더보기 최소 비용 경로 알고리즘과 무엇이 다..

https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 아이디어 우선순위 큐를 이용한 스케줄링 문제입니다. 큰 아이디어는 이렇습니다. 1) 작업의 길이가 짧은 것을 먼저 해야한다. 2) 1)을 만족해도 요청되는 작업만 수행해야한다. 즉, 이 2가지를 고려해서 해결해야합니다. 풀이이 먼저 1) 이전에 2를 해결하기 위해 jobs를 실행시간 기준으로 오름차순 정렬해줍니다. 그러면 일단 2)를 해결했고, 다음은 1)을 해결해야하는데 현재 jobs 배열..

https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 1. 아이디어 첫 번째로 떠올린 아이디어는 '시뮬레이션'이었습니다. 직접 시뮬레이션을 돌려서 문제를 해보고자했죠. 그래서 작성한 코드가 다음과 같습니다. 말그대로 방향을 바꿔가면서 움직여보는 것이였죠. 시간 제한이 0.15초 이고, t가 한 없이 커도 w*h 를 간격으로 똑같은 패턴을 보이기 때문에 나머지를 통해 for문을 돌리면 시간초과가 나오지 않을 것이라 생각했습니다. 하지..

https://www.acmicpc.net/problem/11062 11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 아이디어 처음에는 그리디 알고리즘 문제인줄 알고 deque를 이용해서 현재 최고 가치를 가지는 카드를 뽑는 방식을 로직을 사용했는데, 최선의 전략으로 게임이 끝났을 때, 최고 점수를 얻어야 하는 것이더라구요. 그러면 현재 최선의 선택잉 미래에는 최선이 아닐 수 있습니다. 이럴 때는 다이나믹 프로그래밍을 사용해야죠! dp[i][j] 는 i번째 카드 ~ j번째 카드가 있을 때, 근우의 최대 점수를 뜻합니..

https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 1. 문제 2. 아이디어 이 문제는 기본적으로 스위핑 알고리즘을 사용해서 풀이합니다. 스위핑 알고리즘은 뜻 그대로 휩쓸고 지나가며 문제를 해결하는 방식으로, 특정 기준에 따라 정렬한 후 순서대로 처리하는 알고리즘입니다. 그러므로 스위핑 알고리즘의 복잡도는 O(N log N + N) = O(N log N) 의 복잡도를 가집니다. 즉, 이 문제는 선..