1. 재귀 함수란? 코드 내에서 본인을 호출하는 함수를 재귀함수라고 한다. 하지만 단순히 아래와 같이 자기 자신을 호출만 한다면 함수는 위 송강호씨처럼 영원히 자기 자신을 호출하기를 반복하게 될 것이다. function recursive() { recursive(); } recursive(); 이를 방지하기 위해서 재귀함수는 코드 내에 탈출 조건을 포함하고 있어야 하고, 본인을 호출할 때마다 입력 파라미터가 탈출 조건에 수렴하는 양상으로 변화해야 한다. function recursive(n) { if(n < 0){ //탈출 조건 return; } recursive(n - 1); //변화하는 파라미터, 0으로 수렴 } recursive(5); 2. 반복문 vs 재귀 함수 대부분의 재귀 함수 동작은 변수값을..

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/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..

https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 문제 해석 문제는 위 그림에 "한 명씩만 설 수 있는 공간"을 활용하여 "간식받는 곳"에 수들을 오름차순으로 받아올 수 있을 경우에는 "Nice"를 출력하고 "한 명씩만 설 수 있는 공간"을 활용하여도 "간식받는 곳"에 수들을 오름차순으로 받아올 수 없을 경우에는 "Sad"를 출력하면 되는 문제이다. 우선 설명하기에 앞서 일단 편의를 위해, 그리고 구현된 전체 코드를 더 쉽게 이해하기 위해 간식..

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 단계별로 풀어보기도 어느새 스택 알고리즘에 도착했다. 이제 곧 재귀함수, 백트래킹, 조합 , 백트래킹 등 난이도 있는 문제들을 푸는날도 얼마 남지 않은 것 같다. 문제 해석 먼저 균형잡힌 문자열이 아닌 경우의 수들을 나눠보자. 여는 괄호 '(' 또는 '[' 없이 닫는 괄호 ']' 또는 ')'가 있다면 균형잡힌 문자열이 아니다. 닫는 괄호 바로 이전의 여는 괄호의 종류가 매칭되..