비트(Bit)와 비트마스킹(Bitmasking) 비트마스킹 기법에 대해 학습한 내용을 정리해둔다. 자바의 비트 연산자와 비트 이동 연산자를 알아보고, 비트마스킹이 무엇인지 알아보도록 하겠다. 자바 비트 연산자 & bit AND 연산자 비교하는 비트가 모두 1이면 1 # a = 22, b = 14 # a & b 00010110 (AND) & 00001110 ------------------ 00000110 | bit OR 연산자 비교하는 비트 중 하나라도 1이면 1 # a = 22, b = 14 # a | b 00010110 (OR) | 00001110 ------------------ 00011110 ^ bit XOR 연산자 양쪽 비트가 같으면 0, 다르면 1 # a = 22, b = 14 # a ^ b..

백준 문제 풀이 : 부분수열의 합(1182번)(Java) 문제 문제 확인하기 풀이 n개의 정수들을 원소로 갖는 수열 arr이 있을 때, arr의 부분 집합의 총 원소의 합이 s인 경우가 몇개인지 구하는 문제이다. n의 최대값, 그러니까 수열 arr의 최대 길이는 20이므로, 완전 탐색을 이용하여 문제를 해결할 수 있다. 단순히 모든 경우를 고려하면 된다. n이 4인 수열 {1, 2, 3, 4}가 주어졌다고 가정하자. 이 수열의 부분 집합은 {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 2, 3, 4}가 존재한다. 이 부분 집합들을 하나씩 찾으면서 해당 부분 집합의 ..

백준 문제 풀이 - 포도주 시식 (2156 문제) 문제 문제 확인하기 풀이 조건부터 확인해보자. 포도주 n잔이 주어진다고 했다. 입력받은 n잔의 포도주를 담은 배열을 wines라는 배열로 초기화하겠다. 첫번째 잔을 1로 표시하기 위해 wines[n+1]로 선언하고 인덱스 1부터 n까지 초기화 하자. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] wines = new int[n + 1]; for (int i = 1; i

백준 문제 풀이 - 가장 긴 증가하는 부분 수열 (11053 문제) 문제 문제 확인하기 풀이 증가하는 부분 수열이란 배열 arr이 주어졌을 때, 특정 몇몇 원소를 제외한 수열이 계속해서 이전 원소보다 큰 형태의 수열을 말한다. 예를 들어 { 1, 3, 7, 4, 2, 5, 6 } 이라는 배열이 있다고 하자. 이 배열에 대한 증가하는 부분 수열은 { 1, 3, 7 } { 1, 3, 4, 5, 6 } { 1, 2, 5, 6 } 와 같은 수열이 될 수 있다. 가장 긴 증가하는 부분 수열이란, 위 증가하는 부분 수열들 중에서 가장 긴 길이의 수열을 말한다. 여기서는 { 1, 3, 4, 5, 6 } 수열이 길이 5로 가장 길기 때문에, 해당 수열이 가장 긴 길이의 수열이 된다. 어떻게 이를 구할 수 있을까? 내가..

백준 문제 풀이 - 쉬운 계단 수 (10844번 문제) 백준 10844번 : 쉬운 계단 수 본문 제한 시간 제한 메모리 제한 1초 256MB 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력 1 1 예제 출력 1 9 예제 입력 2 2 예제 출력 2 17 풀이 어떻게 문제를 풀 수 있을지 '계단 수'를 직접 작성해보면서 규칙을 확인해보자. 먼저 N이..

피보나치 함수 (BOJ : 1003) 백준 1003번 : 피보나치 함수 본문 제한 시간 제한 메모리 제한 0.25초 128MB 문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fib..

프로그래머스 : 부대복귀 (Java) 문제 링크 확인 풀이 최단 거리를 구하는 문제이다. 문제가 어려운 것 같지만 차근차근 읽어보면 생각보다 쉽게 문제를 풀 수 있다. 문제에서 주어진 조건을 정리하자면 다음과 같다. n은 총 지역의 수를 의미한다. roads는 roads[x][2]의 크기로 roads[x][0]과 roads[x][1]은 서로 이어진 경로가 있다는 것을 의미한다. road[x][0]에서 road[x][1]로 경로가 있다는 것은, road[x][1]에서 road[x][0]으로도 이동할 수 있다는 의미이다. 각 지역의 이동 비용은 1이다. sources는 1차원 배열로 부대원들이 각각 출발하는 지역을 의미한다. destination은 부대원들이 도착해야 할 목적지를 말한다. 여기서 중요한 점은..

프로그래머스 : 디펜스 게임 (Java) 문제 링크 확인 풀이 처음 가지고 있는 병사 수 n, 무적권의 수 k, 라운드마다 등장하는 적의 수를 담은 1차원 배열 enemy가 주어진다. i번째 라운드의 적의 수 enemy[i]를 막으려면 n개의 가지고 있는 병사(목숨)에서 enemy[i] 만큼을 차감하고, 차감한 후의 n값이 0 이상이어야 해당 라운드를 통과한 것으로 본다. 간단하게 로직을 구상해보자. 남은 병사 수 remain을 선언한다. 초기값은 n 값과 같다. 최대 enemy 배열 길이만큼 아래 내용을 반복한다. (현재 i번째 반복) remain에서 enemy[i]를 빼준다. 조건을 만족하는 한가지를 진행한다. 만약 enemy[i]를 뺀 remain이 0보다 작다면 라운드를 통과할 수 없다. rema..

프로그래머스 : 점 찍기 (Java) 문제 링크 확인 풀이 입력되는 정수 k, d에 대하여 조건을 만족하는 (x, y) 좌표를 찾아야 한다. 문제에서 조건은 다음과 같다. 원점(0, 0)과의 거리가 d를 넘지 않아야 한다. 좌표의 x, y 값은 k의 배수이다. 기본적으로 원점과 x=0 일 때 y 좌표값, y=0 일 때 x 좌표값들의 개수를 추가해둔다. 코드로 나타내면 아래와 같다. long answer = 1; // 원점 1개 // d : 최대 거리 // d를 k로 나눈 값에 2를 곱해주면, // x=0 일 때, y=0 일 때의 좌표값들의 개수이다. answer += ((d / k) * 2); 이제 x, y가 0이 아닐 때 좌표 조합을 구해야 한다. (x, y) 좌표와 원점과의 거리가 d를 넘지 않아야 ..

예산(BOJ : 2512) 백준 2512번 : 예산 본문 제한 시간 제한 메모리 제한 1초 128MB 문제 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 1..