본문 바로가기

TEAM STUDY/알고리즘 코딩 테스트 스터디

(31)

8회차 - 소수세기 입력 형식 첫 줄에는 테스트케이스의 수 T가 주어진다. T는 1이상 10이하의 자연수이다. 각 테스트케이스의 입력으로는 한 줄에 1이상 100만이하의 두 자연수 L과 R이 공백으로 구분되어 주어진다. L R 순서로 주어지며 L은 항상 R이하의 값이다. 출력 형식 각 테스트케이스에 대하여 두 줄씩 정답을 출력한다. 테스트케이스의 첫 줄에는 테스트케이스의 번호를 Case #%d: 형식으로 출력한다. 두 번째 줄에는 L이상 R이하의 소수의 갯수를 공백없이 출력한다. 입/출력 예시 : 공백 : 줄바꿈 : 탭 예시 1 입력 3 210 50100 1001000 출력 Case#1: 4 Case#2: 10 Case#3: 143 import java.io.*; import java.lang.*; import java.u..

7회차 - 소인수 분해 소인수 분해 자연수를 소인수 분해한 결과를 출력하는 프로그램을 작성해보자. 입력으로 주어진 자연수를 소인수분해 한 후 해당 숫자의 소인수들을 나열하면 된다. 입력 형식 첫 줄에는 테스트케이스의 수 T가 주어진다. T는 1이상 100이하의 자연수이다. 각 테스트케이스는 한 줄로 구성되며 소인수 분해를 할 자연수가 주어진다. 이 자연수는 2이상 10억이하이다. 출력 형식 각 테스트케이스에 대한 정답을 두 줄씩 출력한다. 테스트케이스의 첫 줄에는 테스트케이스의 번호를 #%d: 와 같은 형식으로 출력한다. 두 번째 줄에는 입력으로 주어진 숫자들의 소인수들을 공백으로 구분하여 오름차순으로 출력한다. 여러 번 곱해진 소인수는 그 횟수 만큼 출력한다. import java.io.*; import java.lang.*..

7회차 - 수열의 순환 1부터 시작해서 1씩 증가하다가 특정 숫자에 도달하면 다시 1로 돌아오는 수열을 순환 수열이라고 하자. 예를 들어서 5에 도달하면 다시 1로 돌아오는 순환 수열은 아래와 같다. 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 이때 순환 주기가 서로 다른 수열들도 언젠가는 다시 모두가 1이 되는 시점이 존재한다. 예를 들어서 순환 주기가 2와 3인 아래의 두 수열을 보자. 1, 2, 3, 1, 2, 3, 1, 2, 3, ... 1, 2, 1, 2, 1, 2, 1, 2, 1, ... 위의 두 수열은 서로 다른 순환 주기를 가지고 있지만 7번째 숫자에서 다시 동시에 시작하는 부분이 등장하게 된다. 그렇다면 총 N개의 순환 수열이 존재한다고 할 때, 모든 수열이 다시 1부..

7회차 - 최대공약수와 최소공배수 최대공약수와 최소공배수 두 자연수의 최대 공약수와 최소 공배수를 계산하는 프로그램을 작성해보자. 최대공약수(GCD)란 두 정수 A와 B에 모두 나누어 떨어지는 가장 큰 공통의 약수를 의미한다. 최소공배수(LCM)란 A의 배수이면서 동시에 B의 배수가 되는 가장 작은 공통의 배수를 나타낸다. 입력 형식 첫 줄에는 테스트케이스의 수 T가 1이상 100이하의 자연수로 주어진다. 이후 총 T줄에 걸쳐서 한 줄에 하나의 테스트케이스에 대한 입력이 주어진다. 각 테스트케이스의 입력은 한 줄에 두 자연수가 공백으로 구분되어 주어진다. 각 자연수는 1이상 10억이하의 자연수이다. 출력 형식 각 테스트케이스마다 두 줄에 걸쳐 결과를 출력한다. 각 테스트케이스의 첫 줄에는 테스트케이스의 번호를 Case #%d: 형식으로 ..

7회차 - Probing Probing 행사 기획자인 수정이는 이 번에 자신이 담당하게 된 행사에서 행운권 추첨을 기획하고 있다. 이번 행사에서는 최대 수천명 정도의 사람이 방문할 수 있기 때문에 어떻게 하면 공평하고 불규칙적으로 행운권 번호를 배정할 수 있을지가 큰 관건이었다. 하지만 똑똑한 수정이는 아래와 같은 아이디어를 냈다. 모든 행운권 번호는 0~(N-1)의 정수로 총 N개이다. 모든 고객은 회원번호를 가지고 있으며 회원 번호는 자연수이다. 입장한 고객은 자신의 회원 번호를 N으로 나눈 나머지를 계산해 그 번호와 같은 행운권을 지급받는다. 고객들은 순서대로 한 명씩 입장하며 한번 지급된 행운권 번호는 교환할 수 없다. 수정이는 행사 중간에도 바쁠 예정이기에 당신에게 이를 자동화할 수 있는 프로그램을 작성해달라고 요청했다..

7회차 - 스도쿠 보드 문제4A-스도쿠 보드 스도쿠란 아래의 그림 처럼 9행 9열의 보드에 1~9사이의 숫자들을 규칙에 맞게 채워넣는 게임을 말한다. 9행 9열의 보드에는 총 81개의 칸이 있는데 지수는 보통 각 칸을 1~81로 번호를 붙여서 구별한다. 가장 왼쪽 위의 (1행 1열의)칸이 1번 칸이 되고 그 이후 오른쪽으로 가면서 번호를 하나 증가시킨다. 그리고 해당 행이 다 차면 다음줄로 넘어가 이를 반복한다. 스도쿠는 게임의 특징상 각 행과 각 열 그리고 3x3모양의 9칸으로 구성된 그룹에 1~9의 숫자가 하나씩만 들어가야 한다는 규칙이 있다. 그래서 각 칸에 숫자를 배치할 때 그 칸이 속한 그룹을 파악하고 규칙에 맞는지 확인하는 작업이 필요하다. 하지만 지수와 같이 스도쿠 게임을 하고 있는 예인이는 지수가 말하는 칸의 번..

6회차 - 알고리즘 기록 : 과유불급 (어려웠던거 다시!) - 여러개의 카드중에 L 부터 R 까지의 숫자를 더하고자한다. - L 부터 R 의 합을 한 수가 제일 큰 사람을 구한다. - 같은 숫자일 경우 먼저 구매한 사람을 구한다. 아래와 같은 나열된 카드가 있을 경우에 1번 카드 2번 카드 3번 카드 4번 카드 5번 카드 1 -1 5 2 3 예를들어보면 아래와 같다. 2번부터 4번의 합 6 1번부터 3번의 합 5 이렇게 계산하는 것을 부분합, 구간합이라고 한다. 선형공간에서 주어진 범위의 원소들에 대한 합을 계산하는 문제. 가장 쉬운 방법은 FOR 문을 이용해 L 부터 R 까지 더하는 것이지만 최악의 시간 복잡도를 가지고 있다. 고차원적이고 복잡한 정보는 단순한 여러 정보들의 조합으로 표현될 수 있다. - 고차원 적 정보 : 왼쪽 끝과 오른쪽 끝으로 표현된 범위..

6회차 - 알고리즘 기록 : 네 카드 (어려웠던거 다시!) 중복을 포함해 네 카드의 합으로 만들 수 있는 당첨번호들의 리스트를 반환하는 함수 @param n 카드의 수 @param m 검사하려는 당첨번호의 수 @param cards 각 카드에 적힌 숫자들 @param target 검사하려는 각 당첨번호 리스트 @return 네 카드의 합으로 표현될 수 있는 당첨번호들의 오름차순 리스트 네 카드는 모든 카드의 네 가지 수의 조합이 타겟과 같은가 ? 라는 질문을 하는 알고리즘이다. 네 카드는 즉 ( 하나의 카드 + 하나의 카드 ) + ( 하나의 카드 + 하나의 카드 ) 이다. CardPair 는 모든 두 개의 카드로 생성되는 객체다. 즉 두 개의 카드의 합이다. 모든 cards 의 배열을 순회하면서 모든 두 개의 카드의 조합을 생성한다. ArrayList pairs..

이전 1 2 3 4 다음

티스토리툴바