TEAM STUDY156

• 8회차 - 배열 흔들기 (+) 8회차 - 배열 흔들기 8회차 - 배열 흔들기 프로그래머 지수는 제비뽑기 프로그램을 만들고 있다. 자신이 이미 정해둔 N개의 배열에 각각 임의의 번호들을 저장해 두고 사용자들이 0~(N-1)의 정수 번호를 하나 입력하면 그 칸에 있는 숫 soobindeveloper8.tistory.com 배열 흔들기에 대해서 다시한번 이해하기 nNumbers 에 배열의 원소의 수를 저장한다. nCommands에는 처리할 명령어의 수를 저장한다. ShiftingArray 객체에 index 와 value 를 입력 받아 저장할 예정이다. ShiftingArray .set => 현재 배열에서 'index'번째에 존재하는 원소를 'value'로 변경하는 함수 ShiftingArray .set 을 이용해 배열 값을 저장한다. pu.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 8. 1.

• 8회차 - 공약수 게임 평소 모든 게임을 다 잘하는 예인이는 게임의 여왕으로 불린다. 하지만 이번 MT에서 똑똑한 수정이가 준비한 게임은 수학적인 아이디어를 요구하기 때문에 애를 먹고 있다. 수정이가 준비한 게임은 아래와 같은 규칙으로 진행된다. 게임을 하는 참가자는 가장 먼저 자연수가 적힌 카드 N개를 받는다. 참가자는 자신이 원하는 횟수만큼 아래의 동작을 반복할 수 있다. 게임이 종료될 때 각 사람은 자신이 들고있는 카드들에 적힌 숫자들 전부의 최대공약수 만큼 점수를 획득한다. 예인이는 제한 시간동안 마구잡이로 여러 방법을 시도해보고 있지만, 자신이 얻은 점수가 높은 점수인지 확신을 할 수 가 없었다. 예인이를 도와서 처음에 주어진 숫자 카드를 통해 얻을 수 있는 최고의 점수를 계산하는 프로그램을 작성해주자. 입력 형식 첫.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 7. 23.

• 8회차 - 골드바흐의 추측 1742년에 독일의 수학자 골드바흐는 자신의 추측한 바를 정리하여 오일러에게 편지로 전했다. 골드 바흐의 추측은 아래와 같다. "4보다 큰 모든 짝수 자연수는 홀수인 두 소수의 합으로 표현될 수 있다." 아래와 같은 예시들에서 골드바흐의 추측이 성립한다. 8 = 3 + 5 20 = 3 + 17 42 = 5 + 37 당신은 실제로 골드바흐의 추측이 성립하는지 프로그램을 작성해 확인해보고자 한다. 여러 숫자가 주어질 때 그 숫자들에 골드바흐의 추측이 성립하는지 확인하는 프로그램을 작성하시오. 입력 형식 첫 줄에는 테스트케이스의 수 T가 주어진다. T는 100이하의 자연수이다. 테스트케이스의 각 줄에는 골드바흐의 추측이 성립하는지 확인해보고자 하는 6이상 백만이하의 자연수가 하나 주어진다. 출력 형식 각 테스.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 7. 23.

• 8회차 - 카잉 달력 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M 과 N 보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 X < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 예를 들어, M = 10.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 7. 23.

• 8회차 - 배열 흔들기 프로그래머 지수는 제비뽑기 프로그램을 만들고 있다. 자신이 이미 정해둔 N개의 배열에 각각 임의의 번호들을 저장해 두고 사용자들이 0~(N-1)의 정수 번호를 하나 입력하면 그 칸에 있는 숫자를 알려주게 된다. 하지만 자신의 제비뽑기 프로그램을 사람들이 사용하는 모습을 지켜보던 지수는 배열에 저장된 데이터들이 고정적이기 때문에 게임을 반복할 수록 사람들이 숫자를 추정할 수 있다는 문제점을 발견했다. 그래서 지수는 아래와 같은 두 가지 기능을 구현하여 주기적으로 배열에 저장된 원소들의 위치들을 바꿔주고자 한다. 배열의 원소들을 모두 왼쪽으로 한 칸씩 옮긴다. 이 때 0번 칸에 있던 원소는 (N-1)번 칸으로 이동된다. 배열의 원소들을 모두 오른쪽으로 한 칸씩 옮긴다. 이 때 (N-1)번 칸에 있던 원소는 .. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 7. 23.

• 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.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 7. 23.

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

• 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부.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 7. 16.

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

• 

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

• 

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

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