본문 바로가기

Algorithm19

Kakao 2022 Blind Test - Lv2. 양궁대회 (Java) 문제 요약 양궁대회에서 라이언이 우승할 수 있는 방법들 중 가장 낮은 점수를 더 많이 맞힌 경우를 찾아 return, 없다면 [-1] return [문제 설명 및 제한 조건] 어피치와 라이언이 양궁대회 결승전에 올라왔다. 다양한 선수가 양궁대회에서 우승할 수 있도록 하기 위해, 운영위원회는 라이언에게 불리하도록 결승전 규칙을 정하였다. k점에 여러발을 맞추었더라도, k점만 획득할 수 있다. k점을 어피치가 a발, 라이언이 b발을 맞췄을 경우, a >= b 일 경우에 어피치가 k 점을 획득한다. [입출력] n: 각 양궁 선수가 화살을 쏠 수 있는 총 개수 (1 ≤ n ≤ 10) info: 어피치가 쏜 화살의 정보 (0 ≤ info의 원소 ≤ n, info의 원소 총합 = n) 라이언이 어피치를 이길 수 없.. 2022. 6. 11.

Kakao 2022 Blind Test - Lv2. k진수에서 소수 개수 구하기 (Java) 문제 요약 양의 정수 n을 k진수로 바꿨을 때, 변환된 수 안에 10진수 기준 소수가 몇 개인가? [제한 조건] P는 소수 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우 P처럼 소수 양쪽에 아무것도 없는 경우 예를 들어 숫자가 222인 경우, 숫자를 분해하여 소수를 판별하지 않음 = 소수가 아닌 수 단, P는 각 자릿수에 0을 포함하지 않는 소수 예를 들어, 101은 P가 될 수 없음 [입출력] n: 양의 정수 (1 ≤ n ≤ 1,000,000) k: k진수 (3 ≤ k ≤ 10) n k result 437674 3 3 문제 접근 자세한 접근 법은 코드의 주석을 확인하세요 🙂 // 2.. 2022. 6. 4.

Kakao 2021 Blind Test - Lv3. 광고 삽입 (Java) 문제 요약 시청자들의 누적 재생 시간이 가장 많이 나오는 곳에 공익 광고를 삽입하려 한다. 공익 광고가 들어갈 가장 빠른 시작 시각을 구해서 return [문제 설명] 동영상 재생 시간 길이 play_time이 주어진다. 공익 광고 재생 시간 길이 adv_time이 주어진다. logs는 시청자들이 해당 동영상을 재생했던 구간 정보이다. 누적 재생 시간이 가장 많이 나오는 곳에 공익 광고를 삽입하려 할 때, 공익 광고가 들어갈 가장 빠른 시각 return ** 누적 재생 시간이란? - 전체 동영상 구간 중 광고가 들어갈 수 있는 구간에 / 시청자들이 끊이지 않고 동영상을 재생한 시간 [생각의 과정] 시청 시간 중 가장 빨리 시작한 시청 시각과 겹치는 다른 시청 시각의 시작 시간을 한 구간으로 하여 각 구역.. 2022. 6. 2.

Kakao 2021 Blind Test - Lv3. 합승 택시 요금 (Java) 문제 요약 A, B 두 사람이 출발점(s)에서 출발해 각각의 도착 지점까지 택시를 탄다고 할 때, 최저 예상 택시요금을 계산 [문제 설명] A와 B가 출발지에서 도착지까지 택시를 탄다. A와 B는 어느 특정 지점까지 합승할 수 있다. 합승한 지점에서 내린 후 각자의 도착지까지 따로 택시를 탄다. 합승하여 도착지까지 가는 것이 최소 비용인가? 따로 택시를 타서 도착지까지 가는 것이 최소 비용인가? [생각의 과정] 처음에 합승하여 도착지까지 가는 것과 // 따로 택시를 타서 도착지까지 도착하는 비용(합승하지 않는 경우)을 구분하여 생각하려 하였습니다. 그러나 어느 지점까지 합승하였는지를 답하는 곳은 없습니다. 이는 출발점에서 모든 지점까지의 최소 요금을 구한 뒤 임의의 합승 지점을 선택하여 또 다른 모든 지.. 2022. 6. 2.

Next Permutation을 이용한 순열 배열을 오름차순 정렬한 뒤, 사전 순으로 다음 순열을 생성하는 방법 절차 배열을 오름차순으로 정렬 다음이 과정의 반복하여 순열 생성 (가장 큰 내림차순 순열을 만들 때까지 반복) 뒤쪽부터 탐색하여 교환위치(꼭대기 바로 직전) 찾기 (꼭대기 - 가장 큰 수) 뒤쪽부터 탐색하여 교환위치와(꼭대기 바로 직전) 교환할 큰 값 위치 찾기 (교환위치보다 큰 수 중 가장 가까운 수) 두 위치 값 교환 꼭대기부터 맨 뒤까지 오름차순 정렬 ex. 1 2 3 -> 3 2 1 까지 만드는 과정 import java.util.Arrays; public class NextPermutation { static int R, N, nums[], set[]; public static void main(String[] args) { /.. 2022. 5. 17.

Next Permutation을 이용한 조합 flag를 Next Permutation을 이용하여 구현한 것 nCr 을 구하고자 할 때, 크기 n의 배열을 생성하여 r 개의 크기만큼 0 이 아닌 값 초기화 5C2 이면, 00011 로 초기화 Next Permutation 알고리즘 이용 00011을 사용하여 NP를 돌리고 1의 위치에 원소 값이 선택되어 조합을 만든다. Next Permutation 한 번 이용할 때마다 조합이 만들어 진다. (0이 아닌 값의 위치가 변경된다) => r개의 크기 만큼, 즉, 0이 아닌 값이 세팅된 곳에 원소를 선택하여 조합을 만든 것이다. import java.util.Arrays; public class Combination { static int N, R, nums[]; public static void main(S.. 2022. 5. 17.

비트마스킹을 이용한 순열, 조합 비트 0 = false = 사용 중 X 1 = true = 사용 중 O 비트 연산자 & : AND 연산 | : OR 연산 ^ : XOR 연산 (같으면 0, 다르면 1) ~ : 모든 비트 반전 : 비트 열을 오른쪽으로 이동 (빈 공간은 부호비트로 채운다) >>> : 비트 열을 오른쪽으로 이동 (빈 공간은 0으로 채운다) &’은 해당 숫자가 사용중인지, ‘|’은 해당 숫자를 사용 중임을 나타내기 위해 사용 1. 순열 코드 - 비트 마스킹 사용 import java.util.Arrays; public class Permutation_BitMasking { static int R, N, nums[], set[]; public static void main(String[] args) { //nPr R = 2; N.. 2022. 5. 17.

이전 1 2 3 다음

티스토리툴바