본문 바로가기

백준

 (10)
[99클럽] 코딩테스트 스터디, 14일차 TIL - 비기너 (백준, 26042) 1. 문제풀이1) 문제, 식당 입구 대기 줄 (백준 26042)여러 명의 학생이 식사하기 위하여 학교 식당을 향해 달려가고 있다. 학교 식당에 도착한 학생은 식당 입구에 줄을 서서 대기한다. 학교 식당에 먼저 도착한 학생이 나중에 도착한 학생보다 식당 입구의 앞쪽에서 대기한다. 식사는 1인분씩 준비된다. 식사 1인분이 준비되면 식당 입구의 맨 앞에서 대기 중인 학생 1명이 식당으로 들어가서 식사를 시작한다. 식사를 시작한 학생은 항상 식사를 마친다. 학생이 학교 식당에 도착하고 식사가 준비되는 n개의 정보가 저장된 A가 주어진다. A에 저장된 첫 번째 정보부터 n번째 정보까지 순서대로 처리한 다음,식당 입구에 줄을 서서 대기하는 학생 수가 최대가 되었던 순간의 학생 수와 이때 식당 입구의 맨 뒤에 대기 ..
[99클럽] 코딩테스트 스터디, 12일차 TIL - 비기너 (백준, 2161) 1. 문제풀이1) 문제N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다.우선, 제일 위에 있는 카드를 바닥에 버린다. 그다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자.카드는 제일 위에서부터 1234 의 순서로 놓여있다.1을 버리면 234가 남는다.여기서 2를 제일 아래로 옮기면 342가 된다.3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다.마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다. N이 주어졌을 때..
[99클럽] 코딩테스트 스터디, 6일차 TIL - 비기너 1. 문제풀이1) 문제, 전주 듣고 노래 맞히기 (백준, 31562)윤수와 정환은 「전주 듣고 노래 맞히기」라는 게임을 할 예정이다. 「전주 듣고 노래 맞히기」는 주어진 노래의 전주를 듣고 먼저 제목을 맞히는 사람이 점수를 얻어 최종적으로 점수가 더 많은 사람이 이기는 게임이다. 절대 음감을 가진 윤수는 노래의 첫 네 음만 듣고도 어떤 노래든 바로 맞힐 수 있다. 따라서, 정환은 윤수를 이기기 위해 첫 세 음만으로 노래를 맞히게 해주는 프로그램을 만들려고 한다. 우선 정환이 알고 있는 노래 제목, 음이름 등을 데이터로 만든 뒤 프로그램을 구현하기 시작했다. 예를 들어, 다음은 TwinkleStar(반짝반짝 작은 별)의 악보 중 일부이다. 위 악보를 박자와 관계없이 음이름으로 표현하면 CCGGAAG가 된다..
[99클럽] 코딩테스트 스터디, 5일차 "모스부호" TIL - 비기너 (feat. 백준에서 자바스크립트 사용하기) 1. 문제풀이1) 문제, 모스 부호 (백준, 29701)혜민이는 요즘 모스 부호에 관심이 많아졌다. 모스 부호는 짧은 신호와 긴 신호를 적절히 조합하여 문자 기호를 표기하는 방식이다. 각 문자를 나타내는 방식은 미리 정해져 있는데, 예를 들어, 짧은 신호를 '.', 긴 신호를 '-'로 나타낸다면, 모스 부호로 알파벳 'A'는 '.-', 숫자 1은 '.----'와 같이 표기할 수 있다. 모스 부호를 알고 있으면 위험한 상황에서 구조 요청을 하는 데 유용할 것 같아, 혜민이는 평상시에 친구들과 연락을 주고받을 때도 모스 부호를 사용하려고 한다. 혜민이는 친구들이 보내온 모스 부호를 올바르게 해독했는지 바로바로 확인하고 싶어졌다. 알파벳 A-Z, 숫자 0-9, 기호 ',', '.', '?', ':', '-',..
[코딩테스트] 조합의 경우의 수(메모이제이션) 1. 문제. 우선 nCr = n-1Cr-1 + n-1Cr 공식이 어떻게 성립하는지부터 알아보자. n개의 서로 다른 원소 중 r개를 선택하는 경우의 수를 찾을 땐, 두 가지 경우가 발생한다. 하나는 선택된 원소를 포함하는 경우이고, 하나는 포함하지 않는 경우이다. 특정 원소를 이미 선택했다고 가정하면, 남은 n-1개의 원소 중, r-1개를 더 선택해야 하므로 경우의 수는 n-1Cr-1이 된다. 반대로 선택하지 않은 경우라면, n-1개의 원소 중, r개를 선택해야 하므로 경우의 수는 n-1Cr이 된다. 따라서 n개의 원소 중 r개를 선택하는 경우의 수는, 두 경우의 수를 합한 n-1Cr-1 + n-1Cr가 된다. 2. 문제 풀이 function solution(n, r){ let answer; let dy=..
[코딩테스트] 재귀로 팩토리얼 구현하기 1. 문제 자연수 N을 입력하면, N! 값이 출력되도록 만드시오. 1) 팩토리얼 팩토리얼은 n이 자연수일 때, 1부터 n까지의 자연수의 곱을 의미한다. n!으로 표시한다. 예를 들어, 5! = 5*4*3*2*1 = 120이다. 이는 5! = n*(n-1)*(n-2)... 이런 식으로 나타낼 수 있다. 위 식을 활용하면 재귀함수를 통해 간단하게 팩토리얼을 구현할 수 있다. 2. 풀이 function solution(n) { let answer; function DFS(n) { if (n === 1) return 1 else return n * (DFS(n - 1)); } answer = DFS(n); return answer } console.log(solution(5)); 팩토리얼 만드는 방법은 간단하다..
[코딩테스트] 재귀로 순열 구하기 1. 문제 : 순열 구하기 10 이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 순열은 주어진 집합에서 일부 원소를 순서대로 나열하는 것을 말한다. 중복 순열과 달리, 집합에서 각 원소들이 겹치면 안 된다. 2. 풀이 function solution(m, arr) { let answer = []; const n = arr.length; const ch = Array.from({ length: n }, () => 0); let tmp = []; function DFS(l) { if (l === m) { answer.push(tmp.slice()); } else { for (let i = 0; i < n; i++) { if (ch[i] === 0) { ch[i] ..
[코딩테스트] 중복순열 구하기 (feat. javascript) 1. 문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 첫 번째 줄에 자연수 N(3

티스토리툴바