데구리 블로그

문제 링크 https://www.acmicpc.net/problem/23328 23328번: 마을 구하기 미소가 사는 마을에는 $N$채의 집이 일렬로 있다. 어느 날 밤, 마을 내 모두가 잠든 사이에 집마다 폭탄 혹은 폭탄 쉴드가 배치되었다. 폭탄과 폭탄 쉴드는 다음과 같은 특징이 있다. 폭탄은 알파 www.acmicpc.net 풀이 몇 번 끄적여보며 잘 관찰하면, '사전순으로 가장 앞서는 배치'라는 조건 때문에 폭탄을 연속으로 배치해야 한다는 사실을 알 수 있습니다. 예를 들면 다음처럼요. 'bBBbb' < 'bBbBb' 위 사실을 전제로 폭탄을 배치해 봅시다. 확정적인 케이스부터 처리해 나가면 어렵지 않습니다. 터지는 폭탄을 bomb, 그에 맞는 쉴드를 shield, 터지지 않는 폭탄을 upper, ..

문제 링크 https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 개요 문제가 복잡합니다. 과정별로 반복되는 행동을 정리해서 구현합시다. 기본적으로 어항들을 이차원 배열로 관리합니다. 함수형 패러다임을 이용하면 과정별로 함수를 만들어 잘 조립해주기만 하면 됩니다. 1. 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다. 이를 addFish() 함수에서 구현합니다. 2. 어항을 규칙에 따라 쌓는다. 설명이 복잡하지만 어항을 돌돌 말아버린다고..

문제 링크 https://www.acmicpc.net/problem/25289 25289번: 가장 긴 등차 부분 수열 길이가 $N$인 수열 $A$가 주어진다. $A$의 부분 수열 중, 등차 수열인 가장 긴 부분 수열의 길이를 출력하는 프로그램을 작성하자. 부분 수열과 등차 수열이 무엇인지 잘 모르는 친구들은 친절한 준 www.acmicpc.net 풀이 등차수열의 공차가 고정되었다고 생각하면 정말 간단한 dp 문제가 됩니다. $d[\text{num}]$: 공차 $\text{diff}$에 대해, $\text{num}$이 끝 부분에 위치하는 등차수열의 최대 길이. $d[\text{num}] = d[\text{num} - \text{diff}] + 1$ 원소의 범위가 1 ~ 100이기 때문에 공차의 범위는 -9..

문제 링크 https://www.acmicpc.net/problem/25288 25288번: 영어 시험 aa(abba), ab(abba), ba(abba), bb(abba) 를 모두 부분 수열로 갖는다. www.acmicpc.net 풀이 주어진 알파벳과 자릿수가 주어졌을 때, 중복 순열의 모든 케이스가 답이 될 수 있습니다. 각 자리에 어떤 알파벳이든 올 수 있어야 하므로 자리마다 모든 알파벳을 배치해줍시다. 예를 들어 길이가 4, 알파벳이 abc인 경우, abc / abc / abc / abc처럼 구성하면 가능한 모든 케이스를 고려할 수 있습니다. 정답 코드 // @BOJ ------------------------------------------ const fs = require('fs'); cons..

문제 링크 https://www.acmicpc.net/problem/25287 25287번: 순열 정렬 $1$부터 $N$까지의 정수를 임의로 배열한 순열은 총 $N! = N\times(N-1)\times(N-2)\times\cdots\times1$가지가 있다. 예를 들어 $1$부터 $3$까지의 수를 임의로 배열한 순열은 $\lbrace1,2,3\rbrace, \lbrace1,3,2\rbrace, \lbra www.acmicpc.net 풀이 앞에서부터 탐색하며 각 자리의 수를 결정합니다. $i$와 $N-i+1$ 중, 앞자리의 수보다 크면서, 더 작은 수를 선택하면 됩니다. 정답 코드 // @BOJ ------------------------------------------ const fs = require..

문제 링크 https://www.acmicpc.net/problem/25286 25286번: 11월 11일 11월 11일에는 농업인의 날, 가래떡 데이, 보행자의 날, 대한민국 해군 창설 기념일, 유엔참전용사 추모의 날, 빼빼로 데이 등 다양한 의미를 가진 날이다. 성현이는 11월 11일의 11일 전은 10월 31일, www.acmicpc.net 풀이 JS는 Date 객체를 이용하면 간단하게 풀 수 있습니다. 다만 Date 객체는 기본적으로 로컬 타임에 맞춰버리니 UTC라고 명시해줘야 편합니다. 정답 코드 // @BOJ ------------------------------------------ const fs = require('fs'); const stdin = fs.readFileSync('/dev..

문제 링크 https://www.acmicpc.net/problem/25285 25285번: 심준의 병역판정검사 병역판정검사는 병역의무자들의 상태를 검사해 징병 여부와 징병 시 어느 방향으로 복무를 시키는 게 좋을지 판정하는 검사로, 남성들은 만 19세가 되는 해에 모두 병역판정검사를 받는다. 신체 www.acmicpc.net 풀이 여러 개의 조건문을 이용하여 풀어주면 됩니다. 저 같은 경우는 명확히 키만으로 급수가 나오는 경우를 classifyWithHeight() 함수로, 그 외의 경우를 classifyWithBMI() 함수로 빼서 판단했습니다. 정답 코드 // @BOJ ------------------------------------------ const fs = require('fs'); cons..

문제 링크 https://www.acmicpc.net/problem/22983 22983번: 조각 체스판 높이 $N$, 너비 $M$의 정사각형 격자에 검은색과 흰색 중 한 가지 색이 칠해져 있다. 머릿속이 체스로 가득찬 현채는 문득 이 격자를 잘랐을 때 체스판이 되는 경우가 몇 가지인지 궁금해졌다. 체 www.acmicpc.net 풀이 유사한 문제로 가장 큰 정사각형을 찾는 문제가 있습니다. (BOJ 1915 - 가장 큰 정사각형) 여기에 더해서 체스판이 될 수 있는 정사각형의 개수를 구해야 합니다. 잘 생각해보면, $(i, j)$번 칸을 기준으로 새로운 체스판을 만들었을 때 추가되는 체스판의 개수는 그 칸을 끝점으로 하는 모든 체스판의 개수와 동일합니다. $(i, j)$칸을 끝점으로 하는 가장 큰 체스..

알고리즘은 몇 달만 손을 놔도 감이 죽는 것 같다. 결과적으로 6솔 마무리를 하긴 했는데 상당히 불만스러운 코테였다. 마지막 한시간 빼곤 코테 내내 긴장된 상태로 덜덜 떨면서 보고.. 문제를 잘못 봐서 맞왜틀만 계속하고.. 너무 슬펐다. 어디까지 엠바고가 걸려있는질 몰라서 풀이는 간략하게 느낌만 써놔야겠다. 전체적으로 역대 카카오 코테보단 훨씬 쉽게 나왔다. 1번) 사실 문제가 기억 안 난다. 그냥 쉬운 구현 문제였던 걸로 기억함.. JS로 슥삭했다. 2번) JS로 슥삭 했다. 간단한 파싱 + 소수 판별 문제 3번) 이제는 카카오 국룰이 되어버린 시간 파싱 문제였다. 스크롤 압박은 심하지만 문제 자체는 간단했다. 이것도 JS로 슥삭했다. 4번) 카카오 국룰 완탐 문제였다. 문제는 쉬운데 정답 우선순위 조..

문제 링크 https://www.acmicpc.net/problem/22991 22991번: 수요응답형 버스 현대오토에버는 In-Car와 Out-Car 영역 전반의 소프트웨어와 인프라 관련 업무를 수행하는 회사이다. 현재 현대오토에버에서 수요응답형 버스(MOD)를 개발하고 있다. 수요응답형 버스는 승객이 호 www.acmicpc.net 풀이 버스의 최대 배정 배차 요청에 탑승 인원, 대기 가능시간이, 버스에 정원과 도착 예정 시간이 있습니다. 어떤 배차 요청에 버스가 배정되려면 (탑승 인원 $\leq$ 버스 정원), (대기 가능 시간 $\geq$ 도착 예정 시간)을 만족해야 합니다. 인원을 $x$축으로, 시간을 $y$축으로 두고 그래프를 그려봅시다. 검은 점은 배차 요청을, 빨간 x는 버스를 나타냅니다...