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

• 9회차 - 탑 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 8. 6.

• 9회차 - 괄호 문자열 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열이 V.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 8. 6.

• 7회차 - 수열의 순환 (+) 7회차 - 수열의 순환 7회차 - 수열의 순환 1부터 시작해서 1씩 증가하다가 특정 숫자에 도달하면 다시 1로 돌아오는 수열을 순환 수열이라고 하자. 예를 들어서 5에 도달하면 다시 1로 돌아오는 순환 수열은 아래와 같다. 1, 2, 3, 4, 5, 1, 2, soobindeveloper8.tistory.com numbers 은 수열의 주기를 뜻한다. getLCM 에 numbers 를 보내고 getLCM는 1번째 수를 기준으로 그 이후 모든 수를 한번씩 for 문을 돌린다. a b 10 2 3 4 5 7 10 2 3 4 5 7 10 2 3 4 5 7 10 2 3 4 ,,, 7 getLCM ( a , b ) 는 a * b / getGCD 를 구하고, getGCD 는 a 와 b 의 나머지가 0 이 될때까지 .. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 8. 1.

• 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.