Partially Committed

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net N 명의 선수가 선분을 번갈아가면서 그리는 게임을 M 차례까지 진행했을 때, 중간에 사이클이 생긴다면 사이클이 생겼던 회차를, M 번 진행하는 동안 사이클이 발생하지 않았다면 0 을 출력하면 된다. 예제를 통해 생각해보자. 0 과 1 을 선택하여 0-1 선분을 긋는다는 것은 0 과 1 은 같은 집합으로 Clustering 된다는 것이다. m 번의 회차마다 주어지는 두 포인트를 같은 집합으로 ..

https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 브루트포스로 문제를 해결하기에는 N 이 너무 큰 경우에 시간 초과가 발생할 수 있다. 이때 다양한 방법으로 최적화를 시도할 수 있겠지만, 분할정복처럼 N 을 절반씩 나눠서 연산한 다음에 결과를 합쳐서 문제를 푸는 것을 meet in the middle 알고리즘이라고 한다. 다만, 재귀적으로 반복해서 N/2, N/4 ... 1 처럼 계속 쪼개는 게 아니고 맨 처음에 1회만 반으로 쪼개는 것이다. 예..

(title: [백준 13549/1956/1620/2629] 자바) A. 숨바꼭질3 BOJ 13549 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 난이도 Gold 5 풀이 시간 20 분 분류 다익스트라 / 0-1 BFS 시간복잡도 다익스트라 : O(nlogn) 0-1 BFS : O(V+E) = O(N+N) ~= O(N) 공간복잡도 일차원 그래프에서 다익스트라 알고리즘을 수행하여 쉽게 해결할 수 있다. 다익스..

https://school.programmers.co.kr/learn/courses/30/lessons/159994 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 요즘 백준에서만 문제를 풀고 있는데 외부 IDE 가 허용되지 않는 코딩테스트를 대비하여, 오랜만에 프로그래머스 플랫폼에서 가장 최신 문제를 하나 골라서 풀어보았다. String 이 담긴 cards1, cards2, goal 배열이 주어졌을 때 cards1, cards2 를 각각 순서대로 한 장씩 사용했을 때 goal 배열을 완성할 수 있는지 확인해야 한다. 말이 조금 번잡한데, 예시를 보면 이해..