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

• 

  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.

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

• 

  5회차 - 알고리즘 기록 : 세 카드 문제3I-세 카드 본 문제는 앞 문제를 조금 변형하면 해결 할 수 있는 숙제 입니다. 선택해야 할 카드가 세 장일 때에도 앞의 문제와 같은 방법을 적용할 수 있을까 고민해보세요. 힌트> 문제의 입력 사이즈가 작아졌다! 실습 내용 지수가 살고 있는 이상한 나라에서는 독특한 복권제도가 존재한다. 이상한 나라에서는 매 주 당첨 될 자연수 번호를 정해두며, 복권을 구매한 사람은 그 자리에서 수 많은 카드들 중 하나를 뽑을 수 있는 기회가 세 번 주어진다. 즉, 똑같은 카드를 세 번 뽑을 수 도 있다. 이렇게 세 번에 걸쳐 뽑은 카드들에 적혀있는 세 자연수를 더하여 당첨 번호로 지정된 자연수와 일치한다면 그 사람은 당첨되는 것이다. 복권 담당자인 미주는 이번 주에 복권에 사용 될 당첨 번호들을 정하려고 한다. 하.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 7. 2.

• 5회차 - 알고리즘 기록 : 네 카드 📌 네 카드 예인이가 살고 있는 이상한 나라에서는 독특한 복권제도가 존재한다. 이상한 나라에서는 매 주 당첨 될 자연수 번호를 정해두며, 복권을 구매한 사람은 그 자리에서 수 많은 카드들 중 하나를 뽑을 수 있는 기회가 네 번 주어진다. 즉, 똑같은 카드를 네 번 뽑을 수 도 있다. 이렇게 네 번에 걸쳐 뽑은 카드들에 적혀있는 네 자연수를 더하여 당첨 번호로 지정된 자연수와 일치한다면 그 사람은 당첨되는 것이다. 복권 담당자인 미주는 이번 주에 복권에 사용 될 당첨 번호들을 정하려고 한다. 하지만 매 번 실제로 그 당첨번호가 네 카드에 적힌 숫자들의 합으로 만들어 질 수 있는지 (즉, 실제로 당첨될 수 있는 번호인지) 검사하는 과정이 너무 번거로워 고민을 하고 있다. 미주를 도와서 주어진 카드를 조합해 .. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 6. 13.

• 5회차 - 알고리즘 기록 : 두 카드 📌 두 카드 지애가 살고 있는 이상한 나라에서는 독특한 복권제도가 존재한다. 이상한 나라에서는 매 주 당첨 될 자연수 번호를 정해두며, 복권을 구매한 사람은 그 자리에서 수 많은 카드들 중 하나를 뽑을 수 있는 기회가 두 번 주어진다. 즉, 똑같은 카드를 두 번 뽑을 수 도 있다. 이렇게 두 번에 걸쳐 뽑은 카드들에 적혀있는 두 자연수를 더하여 당첨 번호로 지정된 자연수와 일치한다면 그 사람은 당첨되는 것이다. 복권 담당자인 미주는 이번 주에 복권에 사용 될 당첨 번호들을 정하려고 한다. 하지만 매 번 실제로 그 당첨번호가 두 카드에 적힌 숫자들의 합으로 만들어 질 수 있는지 (즉, 실제로 당첨될 수 있는 번호인지) 검사하는 과정이 너무 번거로워 고민을 하고 있다. 미주를 도와서 주어진 카드를 조합해 당.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 6. 13.

• 5회차 - 알고리즘 기록 : 팬미팅 📌 팬미팅 인기 아이돌 그룹 코들리즈(Codelyz)의 매니저인 당신은 우여곡절끝에 팬 사인회를 성공적으로 성공시켰다. 팬 카페에서도 이번 팬 사인회 선발 기준에 대한 긍정적인 반응들이 많았고, 회사에서도 당신의 문제해결능력을 칭찬하였다. 하지만 능력있는 사람은 항상 바쁜 법, 후배 매니저가 기획한 팬 사인회 내부 이벤트에 해결해야 할 문제가 있어 이를 도와주어야 한다. 후배 매니저가 기획한 이벤트는 아래와 같다. 팬 사인회에서 기본적으로 모든 팬들은 정해진 좌석에 앉아서 대기한다. 모든 좌석은 1부터 N번 사이의 자연수로 번호가 매겨져 있으며, 팬들은 좌석을 옮길 수 없다. 당신은 이 중 연속한 좌석 K개를 선택해 해당 좌석에 앉은 팬들을 대상으로 이벤트를 진행해야 한다. 이 이벤트는 생년월일 6자리를.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 6. 13.

• 5회차 - 알고리즘 기록 : 과유불금 📌 과유불금 인기 아이돌 코들리즈(Codelyz)의 매니저인 당신은 코들리즈의 팬 사인회를 기획하고 있다. 원래의 계획대로라면 팬들이 구매한 앨범의 시리얼 넘버를 추첨하여 팬 사인회 초대권을 증정할 계획이었지만, 얼마 전(문제3C)에 있었던 중복응모사건으로 인하여 다른 방법을 찾아야만 했다. 이 번에 당신이 준비한 방법은 다음과 같다. 당신은 미리 N개의 숫자카드들을 선정하여 임의의 순서대로 배치해두었다. 숫자카드의 순서는 바뀌지 않으며, 카드에 적힌 숫자와 별개로 1번 카드, 2번 카드, ... 로 번호를 붙였다. 각 카드에는 32비트 정수형 범위에 해당하는 숫자가 적혀있다. 다만 앨범을 구매하기 전 팬들에게 공개하지 않는다. 앨범은 한 사람 당 한 번만 구매할 수 있으며, 앨범을 구매한 사람은 1과 .. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 6. 13.

• 

  4회차 - 알고리즘 기록 : 색종이 📌색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역 넓이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다. 입력 형식 첫 줄에는 테스트케이스의 수 T가 주어진다. 각 테스트케이스의 첫 줄에는 색종이의 수 N이 1이상 100이하의 자연수로 공백없이 주어진다. 이후 N줄에 걸쳐서 각 색종이의 정보가 공백으로 구분된 90보다 작거나 같은 두 자연수로 주어진다. 첫 번째 .. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 6. 13.

• 4회차 - 알고리즘 기록 : 피보나치 나머지 📌피보나치 나머지 피보나치 수열이란 0, 1부터 시작해서 이 전의 두 값을 더해 새로운 값을 만들어나가며 전개되는 수열이다. 0, 1, 1, 2, 3, 5, 8, 13, 21, ... 피보나치 수열은 규칙이 간단하고 수학적으로 다양한 특징이 있기에 자주 사용되는 수열 중 하나이다. 하지만 수열이 진행될 수록 숫자가 급격히 커지기 때문에 손으로 계산하기에는 쉽지 않은 수열이다. 피보나치 수열과 8자리 전화번호의 관련성을 연구하고 있던 지애는 손으로 하던 계산을 프로그램으로 대체하기 위하여 당신에게 도움을 요청했다. 지애를 도와주기 위하여 어떤 수 N이 주어졌을 때, N번째 피보나치 수의 마지막 8자리 숫자를 정수형태로 출력하는 프로그램을 작성해주자. 예를 들어서 실제 수열의 값이 1,000,283,859이.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 6. 13.

• 4회차 - 알고리즘 기록 : 응모 📌응모 어느 한 아이돌 그룹의 팬 클럽 '아재리눅스'의 회원들은 앨범과 기념품 구매에 돈을 아끼지 않기로 유명하다. 이 아이돌 그룹의 소속사는 이번 새 2집 리패키지 앨범을 구매한 회원들을 대상으로 팬 사인회를 진행하기로 결정하였다. 예상과 같이 새 앨범은 출시와 동시에 엄청난 수량이 판매되었으며, 팬 사인회에서 수용할 수 있는 구매자의 수를 아득히 넘어섰다. 결국 모든 회원을 팬 사인회에 초청할 수 없었기에 판매 된 앨범의 시리얼 번호를 통하여 추첨을 하기로 하였다. 하지만 앨범을 구매한 모든 사람이 팬 사인회 참가가 가능한 것은 아니므로 참가를 희망하는 팬들에게 본인이 구매한 앨범의 시리얼 넘버를 통해 응모할 수 있도록 하였다. 하지만 너무나도 아이돌을 만나고 싶어하는 몇몇 삼촌 팬이 같은 시리얼 번.. TEAM STUDY/알고리즘 코딩 테스트 스터디 2022. 6. 13.