Kwin's Development Diary.

비트 마스킹 / 비트 마스크 (BitMasking / BitMask) : 정수의 이진수 표현을 사용하는 기법 장점 1. 연산 시간이 빠름 - 비트 마스킹은 bit연산이므로 거의 모든 연산이 O(1)의 시간 복잡도를 갖고 있다. 따라서 다른 연산자를 이용한 연산보다 연산 시간이 빠르다. 2. 코드가 짧음 - 다양한 집합 연산을 비트 연산자를 이용하여 한 줄로 작성이 가능하다. 3. 메모리 사용량이 적다 - 데이터를 미리 계산하여 저장 가능하고, boolean 자료형의 경우 1byte(= 8bit)의 메모리가 필요한 반면, 비트로 저장하면 1bit만 사용한다. => 동적 계산법 (DP : Dynamic Programming)에 유리 비트 연산자 비트 연산자 논리 의미 & AND 양쪽 비트가 모두 1인 경우에..

문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. ..

문제 네 개의 명령어 D, S, L, R을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다. S: S는 n에서 1을 뺀 결과 n-1을 레지스터에 저장한다. n이 0이라면 9999 가 대신 레지스터에 저장된다. L: L 은 n의 각 자릿수를 왼편으..

문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경 대신 렌즈를 착용하거나 해야 한다. 해빈이가 가진 의상들이 주어졌을 때 과연 해빈이는 알몸이 아닌 상태로 며칠 동안 밖에 돌아다닐 수 있을까? 입력 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 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부터 매겨 수를 압축하여 출력하는 문제이다. 따라서, 숫자를 정렬하여 해당 숫자가 입력된 수..

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