본문 바로가기

생각정리/코딩테스트

 (76)
[JAVA 알고리즘]BAEKJOON 9527번 1의 개수 세기 1의 개수 세기문제 설명두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자. ∑𝑥=𝐴𝐵𝑓(𝑥)입력 첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 10^16) 출력1의 개수를 세어 출력한다.제한사항없음입출력 예inputreturn2 1221문제 분석문제에서 주어지는 값이 10^16으로 int의 범위를 넘어 가므로 long을 사용해야 한다.비트마스크를 사용하기 위해서 최대 값인 10^16을 이진수로 했을 경우, 총 57자리의 크기가 필요하므로 최대크기를 57로 지정해 준다.이진수에서 ..
[JAVA 알고리즘]BAEKJOON 27172번 수 나누기 게임 수 나누기 게임문제 설명《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다.《수 나누기 게임》의 규칙은 다음과 같습니다.게임을 시작하기 전 각 플레이어는 1부터 1000000 사이의 수가 적힌 서로 다른 카드를 잘 섞은 뒤 한 장씩 나눠 가집니다.매 턴마다 플레이어는 다른 플레이어와 한 번씩 결투를 합니다.결투는 서로의 카드를 보여주는 방식으로 진행되며, 플레이어의 카드에 적힌 수로 다른 플레이어의 카드에 적힌 수를 나눴을 때, 나머지가 0이면 승리합니다. 플레이어의 카드에 적힌 수가 다른 플레이어의 카드에 적힌 수로 나누어 떨어지면 패배합니다. 둘 다 아니라면 무승부입니다.승리한 플레이어는 1점을 획득하고, 패배한 플레이어는..
[JAVA 알고리즘]BAEKJOON 10942번 팰린드롬? 팰린드롬?문제 설명명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그다음, 명우에게 질문을 총 M번 한다.각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니 다를 말해야 한다.예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.S = 3, E = 3인 경우 1은 팰린드롬이다.S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.자연수 N개와 질문 M개가 모두..
[JAVA 알고리즘]BAEKJOON 2812번 크게 만들기 크게 만들기 문제 설명 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 출력 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 제한사항 없음 입출력 예 input return 4 2 1924 94 7 3 1231234 3234 10 4 4177252841 775841 추가 반례 11 9 99912349111 99 문제 분석 N자리의 숫자와 K개의 숫자를 제거해 가장 큰 수를 만들어야 한다. 문제를 통해 알 수 있는 조건 K개의 숫자를 제거해야 한다. 최종 숫자의 ..
[JAVA 알고리즘]BAEKJOON 3661번 생일 선물 생일 선물 문제 설명 오늘은 선영이의 생일이다. 선영이의 친구들은 선영이에게 생일선물로 스타크래프트 2를 사주기로 했다. 선영이의 친구들은 비용을 공정하게 내기로 결정했다. 친구들 중 일부는 다른 친구들보다 돈이 많기 때문에, 각자 낼 수 있는 금액보다 더 많은 금액은 내지 않기로 했다. 모든 사람이 내는 돈은 1원의 배수이다. 즉, 분수로 낼 수는 없다. 친구들은 자신이 낼 수 있는 최대 금액을 적어서 냈다. 이제 이 정보를 이용해서 각자 낼 금액이 얼마인지 계산해보려고 한다. 공정하게 선물 비용을 내려면, 선물 금액의 1/n과 각 사람이 낸 금액의 차이의 최댓값을 최소로 해야 한다. 만약, 같은 경우가 나오는 경우에는 두 번째 차이의 최댓값을 최소로 해야 하고, 이런 식이다. 각 사람이 낼 수 있는 ..
[JAVA 알고리즘]BAEKJOON 9251번 LCS LCS 문제 설명 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 제한사항 시간 제한 0.4초 입출력 예 input return ACAYKP CAPCAK 4 문제 분석 문자열 2개가 주어지고 두 문자열을 비교를 하면서 순서가 섞이지 않게 연속된 같은 문자의 길이를 구해야 한다. 문자열은 최대 1000글자로 이루어져..
[JAVA 알고리즘]BAEKJOON 2343번 기타 레슨 기타 레슨 문제 설명 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다. 강토의 각..
[JAVA 알고리즘]BAEKJOON 3020번 개똥벌레 개똥벌레 문제 설명 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다. 아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림) 이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다. 위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다) 하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다. 동굴의 ..

티스토리툴바