1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제를 단순히 요약하자면 0과 1이 n * m 테이블 형태로 주어졌을 때 1이 모여있는 집단의 개수를 구하라고 요구하고 있다. 그리고 모여있다의 정의는 문제 설명에 나와있다. 첫번째 제출에서는 반례가 나왔고, 두번째 제출에서는 시간 초과가 발생했다. 각각 어떤 이유로 틀렸고 시간초과가 발생했는지 살펴본 뒤 정답 코드를 설명해 보겠다. 틀렸습니다 아래는 처음 제출했던, 반례가 발견된 코드다. const fs = require("fs"); let input = fs .readF..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제 풀이 위 문제의 주제는 최소한의 작업 시간으로 땅을 평탄화시키는 것이고, 이를 잘 생각해보면 최소한의 작업 시간으로 땅을 평탄화를 시켰을 때 나올 땅의 높이를 구하면 된다는 것을 알 수 있다. 마침 땅의 높이도 ( 0 Number(item))); let [N, M, B] = input.shift(); let blocks = [].concat(...input); let min_height =..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 위 문제는 전형적인 동적 계획법 (Dynamic Programming), DP 문제이다. 동적 계획법(DP)의 정의는 큰 문제를 작은 문제로 나누어 푸는 방식을 말한다. 큰 문제를 작은 문제로 나누어 푸는 방식을 동적 계획법(DP)이라고 부른다면 분할과 정복과 어떤 차이가 있는지 궁금할 수 있다. 가장 큰 차이점은 동적 계획법은 분할과 정복과 다르게 하위 문제의 해결이 상위 문제에서 사용 되기 때문에, 하위 문제의 해결을 재사용한다는 것이다. 그리고 이렇게 하위 문제를..

https://www.acmicpc.net/problem/24060 24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다. if (p < r) then { q

최근 근황 길고 짧았던 우아한 테크 코스의 마지막 프리코스 미션이 엊그제로 끝이 났다. 프리코스를 진행하는 동안은 학교 프로젝트도 백준도 뒷전이고 하루종일 미션에만 신경 썼던 것 같다. 원래 아직 내가 도전하기에는 많이 모자라다고 생각해서 참가할지 말지에 대해 고민했었는데, 프리코스 미션들을 진행하며 정말 도전해보길 잘했다고 생각했다. 결과는 아직 나오지 않았지만, 프리코스 자체만으로도 너무 많은 인사이트와 지식들을 얻을 수 있었다. '백준 문제 매일 풀기'도 다행히 단계별로 풀기에서 비교적 쉬운 부분들이어서 매일 하루에 30분정도 금방 투자해서 풀 수 있었다.    그런데 마지막 미션을 수행하던 기간 중 120을 향해 달려가던 스트릭이 끊어지고 말았다. 안그래도 멀티태스킹 능력이 현저히 떨어지던 내가 ..

https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제를 처음 읽었을 때는 지난번 풀었던 스택 문제에서 큐로 바뀌기만 했구나 싶어서 크게 어려울 것 없겠다고 생각했다. 그래서 아래와 같이 배열의 shift() 함수를 사용하여 큐의 pop을 구현했었다. const fs = require("fs"); const input = fs .readFileSync("/dev/stdin") .toString() .trim() .spli..