Kwin's Development Diary.

문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경 대신 렌즈를 착용하거나 해야 한다. 해빈이가 가진 의상들이 주어졌을 때 과연 해빈이는 알몸이 아닌 상태로 며칠 동안 밖에 돌아다닐 수 있을까? 입력 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다. 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다. 모든 문자열은 1 이상 20 이하의 알파벳 소문자로 이루어져 있으며 같은 이름을 ..

문제 안녕? 내 이름은 이다솜. 나의 꿈은 포켓몬 마스터야. 일단 포켓몬 마스터가 되기 위해선 포켓몬을 한 마리 잡아야겠지? 근처 숲으로 가야겠어. (뚜벅뚜벅) 얏! 꼬렛이다. 꼬렛? 귀여운데, 나의 첫 포켓몬으로 딱 어울린데? 내가 잡고 말겠어. 가라! 몬스터 볼~ (펑!) 헐랭... 왜 안 잡히지?ㅜㅜ 몬스터 볼만 던지면 되는 게 아닌가...ㅜㅠ (터벅터벅) 어? 누구지? 오박사 : 나는 태초마을의 포켓몬 박사 오민식 박사라네. 다솜아, 포켓몬을 잡을 때는, 일단 상대 포켓몬의 체력을 적당히 바닥으로 만들어놓고 몬스터 볼을 던져야 한단다. 자, 내 포켓몬 이상해 꽃으로 한번 잡아보렴. 포켓몬의 기술을 쓰는 것을 보고 포켓몬을 줄지 안 줄지 결정을 하겠네. 자 한번 해보아라. 다솜아. 이다솜 : 이상해..

문제 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다. 케빈 베이..

Priority Queue : 삽입되는 순서와 관계없이 큐에 저장된 원소들 중 우선순위가 높은 순으로 삭제되는 자료구조 [자료구조] 큐(Queue)에 대한 설명 글 [자료구조] 큐(Queue) 큐 (Queue) - 스택과 마찬가지로 삽입과 삭제의 위치가 제한된 유한 순서 리스트 - 선입선출 구조(FIFO, First-In-First-Out) : 삽입 순으로 나열되어 가장 먼저 삽입한 원소가 가장 먼저 삭제된다. 삭제 kwin0825.tistory.com 선언 import java.util.PriorityQueue; import java.util.Collections; // 정렬에 필요한 경우 PriorityQueue 변수명 = new PriorityQueue(); ㄴ 에 넣은 자료형만 삽입, 삭제 가능 ..

위상 정렬 알고리즘 (Topological Sort Algorithm) : 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 정렬하는 알고리즘 위상 정렬 알고리즘 ① 진입 차수가 0인 정점들 모두 enQueue ② 큐에서 deQueue 해서 반환받은 정점 출력 ③ 출력한 정점에서 뻗어나가는 간선이 도착하는 정점의 진입 차수 -1 ④ 진입 차수를 -1 해준 정점의 진입 차수가 0이 되면 enQueue ⑤ 큐가 Empty상태가 될 때까지 ② ~ ④과정 반복 더보기 결괏값 >>> V0 - V1 - V2 - V3 - V4 - V5 - V6 의사 코드(Pseudo Code) Topological() Q ← createQueue(); for(Vi ← 0; Vi

문제 수직선 위에 N개의 좌표 X1, X2,..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2,..., XN에 좌표 압축을 적용한 결과 X'1, X'2,..., X'N를 출력해보자. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2,..., XN이 주어진다. 1 ≤ N ≤ 1,000,000 -109 ≤ Xi ≤ 109 출력 첫째 줄에 X'1, X'2,..., X'N을 공백 한 칸으로 구분해서 출력한다. 문제 접근 방법 이번 문제는 입력된 수의 크기 순위를 0부터 매겨 수를 압축하여 출력하는 문제이다. 따라서, 숫자를 정렬하여 해당 숫자가 입력된 수..

서론 정말 시간이 빠르다. 풀릴 것 같지 않던 날씨가 점점 풀리고 옷차림도 이전에는 두 겹 세 겹 껴입었다면 이제는 한 겹만 입어도 해가 따스한 날에는 땀이 나기 시작한다. 이번 기간에는 크고 작은 일이 있었다. 사고를 치기도 했고, 분대장도 달았고, 하여간 정말 정신없는 바쁜 기간을 보내고 있다. 지금은 게다가 훈련 기간이라 하루에 1문제를 푸는 것조차 버겁다. 숙영을 하고 오면 아예 공부할 시간이 하나도 없고 최근에는 피곤해서 개인 정비 시간에 곯아떨어지기 일쑤다. 본론 이번 기간에는 훈련으로 인한 공백이 있다. 그러나 이를 제외한 나머지 날은 하루에 한 문제씩 꼬박꼬박 열심히 채워나갔다. 이제 슬슬 골드 상위 티어 문제를 접하다 보니 새로운 자료구조를 접하기보다는 이전에 나왔던 자료구조를 이용하여,..

문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러 개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -2^31보다 크고, 2^31보다 작다. 출력 입력에서 0이 주어진..

문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j ≤ N 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 문제 접근 방법 이번 문제는 누적 합 문제인데 개인적으로 다이나믹 프로그래밍 문제와 같다고 생각한다. 누적 합을 저장할 배열을 n+1칸만큼 선언해주고, 1번 인덱스부터 n번 인덱스까지 [idx] =[idx-1] + 입력된 수 해주..

문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1 ×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄..