본문 바로가기

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

 (31)
9회차 - 탑 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4..
9회차 - 괄호 문자열 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열이 V..
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 이 될때까지 ..
8회차 - 배열 흔들기 (+) 8회차 - 배열 흔들기 8회차 - 배열 흔들기 프로그래머 지수는 제비뽑기 프로그램을 만들고 있다. 자신이 이미 정해둔 N개의 배열에 각각 임의의 번호들을 저장해 두고 사용자들이 0~(N-1)의 정수 번호를 하나 입력하면 그 칸에 있는 숫 soobindeveloper8.tistory.com 배열 흔들기에 대해서 다시한번 이해하기 nNumbers 에 배열의 원소의 수를 저장한다. nCommands에는 처리할 명령어의 수를 저장한다. ShiftingArray 객체에 index 와 value 를 입력 받아 저장할 예정이다. ShiftingArray .set => 현재 배열에서 'index'번째에 존재하는 원소를 'value'로 변경하는 함수 ShiftingArray .set 을 이용해 배열 값을 저장한다. pu..
8회차 - 공약수 게임 평소 모든 게임을 다 잘하는 예인이는 게임의 여왕으로 불린다. 하지만 이번 MT에서 똑똑한 수정이가 준비한 게임은 수학적인 아이디어를 요구하기 때문에 애를 먹고 있다. 수정이가 준비한 게임은 아래와 같은 규칙으로 진행된다. 게임을 하는 참가자는 가장 먼저 자연수가 적힌 카드 N개를 받는다. 참가자는 자신이 원하는 횟수만큼 아래의 동작을 반복할 수 있다. 게임이 종료될 때 각 사람은 자신이 들고있는 카드들에 적힌 숫자들 전부의 최대공약수 만큼 점수를 획득한다. 예인이는 제한 시간동안 마구잡이로 여러 방법을 시도해보고 있지만, 자신이 얻은 점수가 높은 점수인지 확신을 할 수 가 없었다. 예인이를 도와서 처음에 주어진 숫자 카드를 통해 얻을 수 있는 최고의 점수를 계산하는 프로그램을 작성해주자. 입력 형식 첫..
8회차 - 골드바흐의 추측 1742년에 독일의 수학자 골드바흐는 자신의 추측한 바를 정리하여 오일러에게 편지로 전했다. 골드 바흐의 추측은 아래와 같다. "4보다 큰 모든 짝수 자연수는 홀수인 두 소수의 합으로 표현될 수 있다." 아래와 같은 예시들에서 골드바흐의 추측이 성립한다. 8 = 3 + 5 20 = 3 + 17 42 = 5 + 37 당신은 실제로 골드바흐의 추측이 성립하는지 프로그램을 작성해 확인해보고자 한다. 여러 숫자가 주어질 때 그 숫자들에 골드바흐의 추측이 성립하는지 확인하는 프로그램을 작성하시오. 입력 형식 첫 줄에는 테스트케이스의 수 T가 주어진다. T는 100이하의 자연수이다. 테스트케이스의 각 줄에는 골드바흐의 추측이 성립하는지 확인해보고자 하는 6이상 백만이하의 자연수가 하나 주어진다. 출력 형식 각 테스..
8회차 - 카잉 달력 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M 과 N 보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 X < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 예를 들어, M = 10..
8회차 - 배열 흔들기 프로그래머 지수는 제비뽑기 프로그램을 만들고 있다. 자신이 이미 정해둔 N개의 배열에 각각 임의의 번호들을 저장해 두고 사용자들이 0~(N-1)의 정수 번호를 하나 입력하면 그 칸에 있는 숫자를 알려주게 된다. 하지만 자신의 제비뽑기 프로그램을 사람들이 사용하는 모습을 지켜보던 지수는 배열에 저장된 데이터들이 고정적이기 때문에 게임을 반복할 수록 사람들이 숫자를 추정할 수 있다는 문제점을 발견했다. 그래서 지수는 아래와 같은 두 가지 기능을 구현하여 주기적으로 배열에 저장된 원소들의 위치들을 바꿔주고자 한다. 배열의 원소들을 모두 왼쪽으로 한 칸씩 옮긴다. 이 때 0번 칸에 있던 원소는 (N-1)번 칸으로 이동된다. 배열의 원소들을 모두 오른쪽으로 한 칸씩 옮긴다. 이 때 (N-1)번 칸에 있던 원소는 ..

티스토리툴바