알고리즘 124
핵심 접근 — 자식 반환값으로 병합 판정하는 상향식 분할 정복
핵심 접근 — 부분 순열 백트래킹 + set 중복 제거 + 시행 나눗셈 판정
핵심 접근 — a+b > b+a 비교자로 정렬해 이어 붙이기
핵심 접근 — 다리를 길이 고정 큐로 두고 빈 칸 0을 밀어 1초를 표현
핵심 접근 — 라운드 k+1번 벨만-포드 + prev 스냅샷으로 연쇄 갱신 차단
핵심 접근 — 짝수는 +1, 홀수는 최하위 0비트를 켜고 그 아래를 끈다
핵심 접근 — queue 를 최소 힙으로 바꾼 다익스트라, INF 는 -1
핵심 접근 — 연산 비용이 모두 1이므로 BFS 최초 도달이 곧 최소 횟수
핵심 접근 — 멀티소스 BFS + visited 를 1부터 시작하는 +1 인코딩
핵심 접근 — 접미 종류 수를 미리 세두고 접두를 훑으며 비교
핵심 접근 — 조건을 차수로 번역해 cnt[i] == n-1 한 줄로 접기
핵심 접근 — 답을 기다리는 인덱스를 단조 감소 스택에 쌓아 O(n)
핵심 접근 — 인접 행렬 그대로 두고 int 반환 DFS로 판정문 제거
핵심 접근 — 사전순 == DFS 방문순서, 사전을 만들면서 순번을 센다
핵심 접근 — 인접 리스트 + BFS 큐, 재귀 DFS는 깊이 20만에서 죽는다
핵심 접근 — 시각을 분으로 정규화하고 map 두 개로 미출차·누적을 분리
핵심 접근 — 0을 구분자로 토큰 분리 + 제곱근 소수 판정, 토큰은 long long
핵심 접근 — 고를 것은 수가 아니라 부호, 자리마다 두 갈래 DFS
핵심 접근 — 그리디 반례가 예제 자체, 8! 순열 백트래킹 + 제약 가지치기
핵심 접근 — FIFO 큐로 순서를 지키고 우선순위 큐로 남은 최댓값만 조회
핵심 접근 — 완성일로 환산 후 큐 앞을 기준으로 묶는 O(n)
핵심 접근 — 해시맵 카운팅 + 곱의 법칙
핵심 접근 — 프리픽스 합 + 해시맵(등장 횟수 카운팅)
핵심 접근 — 프리픽스 합(prefix sum) 전처리
핵심 접근 — 정의대로 3중 루프, 순회 순서만 i-k-j
핵심 접근 — 배열을 만들지 않고 인덱스에서 값을 역산
핵심 접근 — 내림차순 정렬 후 경계 찾기
같은 격자 BFS인데 한쪽은 매번 visited를 리셋해야 하고 다른 쪽은 절대 하면 안 됐다. 기준은 '각 시작점이 독립된 답을 내는가'였고, 세 번째 문제는 상태 갱신 순서가 답을 갈랐다.
핵심 접근 — 시작점 x 길이 완전탐색 + set
슬라이딩 윈도우의 본질은 구간을 옮기는 게 아니라 직전 계산을 버리지 않는 것이다. 빠지는 값과 들어오는 값만 반영해 O(1)로 갱신하는 원리를 두 가지 변형으로 확인했다.
핵심 접근 — 가변 크기 슬라이딩 윈도우 + 마지막 등장 위치 기록
핵심 접근 — 고정 크기 슬라이딩 윈도우
핵심 접근 — 같은 BFS 골격에서 누적값·큐 사용만 바꾸는 심화 4문제
핵심 접근 — 정렬 후 (고정 + 투 포인터)
핵심 접근 — 양끝 투 포인터
핵심 접근 — 약수 완전탐색 O(sqrt(N))
핵심 접근 — 반복 + 나머지 누적 O(n)
'한 사람이 같은 사람을 여러 번 신고해도 1회'라는 지문 한 줄을 어디서 처리하느냐로 정답과 오답이 갈린다. 그 함정과, 해시맵을 둘로 나눠 카운팅한 구현.
핵심 접근 — 해시맵 카운팅 O(report)
패러다임이 다른 세 문제를 풀었는데 막힌 지점은 셋 다 알고리즘이 아니라 한 끗이었다. 회의실 배정·계단 오르기·MT 장보기에서 그 한 끗이 왜 답을 가르는지.
핵심 접근 — DP (0/1 냅색 / subset sum)
핵심 접근 — - 좌상단 (0,0), N=행-1 / S=행+1 / W=열-1 / E=열+1
핵심 접근 — - 득점과 득점 사이 구간마다 그 구간 동안 누가 앞서 있었는지 판정
DFS는 한 번 외우면 끝날 것 같지만 문제마다 반환값과 매개변수를 바꿔야 한다. 네 문제를 이어 풀며 세 변형으로 확장하고, 단방향·양방향을 가르는 지점과 visited 초기화 타이밍까지.
핵심 접근 — - 양방향 인접 리스트 구성
핵심 접근 — - 양방향 인접 리스트 구성
핵심 접근 — - 'A B' 입력 → v[b].push_back(a) (단방향, 역방향 저장)
핵심 접근 — - 인접 리스트로 그래프 구성
핵심 접근 — 모든 '#'을 감싸는 최소 경계 사각형(bounding box)
핵심 접근 — 지표마다 부호 있는 점수 하나로 압축
핵심 접근 — 스택으로 재료를 쌓되, 새 재료를 push할 때마다 위 4개를 확인한다.
핵심 접근 — skip 알파벳을 bool[26] 룩업 테이블에 표시(O(1) 조회).
자료구조도 유형도 다른 일곱 문제에서 같은 한 줄이 계속 나왔다. 그 변환 하나가 map을 배열로 대체하고 문자열 문제를 카운팅 문제로 바꾸는 과정을 문제별로 따라갔다.
핵심 접근 — DP (격자 in-place)
핵심 접근 — DP + 롤링 변수
핵심 접근 — 그리디 1-pass O(n)
핵심 접근 — 그리디 + 투 포인터
핵심 접근 — 각 패턴을 주기로 순환 비교해 점수 집계, 최고점자를 번호 순으로 수집 — O(n)
핵심 접근 — 내림차순 정렬하면 매 m번째 원소가 그 상자의 최저점.
핵심 접근 — used 배열로 방문 체크, path push→재귀→pop 백트래킹으로 n!개 순열 생성.
핵심 접근 — 재귀 진입마다 현재 path를 답에 저장, start 인덱스로 중복 부분집합 차단.
핵심 접근 — 크기 k의 최소 힙 유지. 매일 점수를 넣고 k를 넘으면 최솟값을 제거,
핵심 접근 — 보유 병 n이 a 이상인 동안 교환 반복.
정렬된 distinct integer 배열 nums와 target이 주어진다.
핵심 접근 — n번째 글자 1차 키, 같으면 문자열 전체 사전순 2차 키로 정렬 — O(m log m)
핵심 접근 — 각 영단어를 대응 숫자로 치환한 뒤 정수 변환 — O(|s|)
pow(x, n) 구현 — x의 n제곱을 반환
핵심 접근 — 길이 p인 부분문자열을 슬라이딩하며 수 비교.
핵심 접근 — 길이가 13 이하로 작아 세 개를 모두 고르는 완전탐색 — O(n³)
피보나치 수열 F(n)을 계산하여 반환
핵심 접근 — n%3로 하위 자릿수부터 뽑아 answer=answer*3+자릿수로 쌓으면
문제 요약 — 프로그래머스 입문 문제 — 기초 구현 풀이
정수 배열 nums를 오름차순으로 정렬하여 반환
핵심 접근 — 같은 위치 원소를 순회하며 더함 — O(행*열)
오름차순 정렬된 두 배열 nums1(m개), nums2(n개)를 하나의 배열로 병합
부족한 금액 계산하기 — N번째 이용료가 price×N으로 늘어날 때 부족한 금액을 for문 누적과 등차수열 합 공식 두 가지로 푼 풀이
프로그래머스 모의고사 — 수포자 3인의 찍기 패턴을 나머지 연산으로 순회하며 점수를 비교하는 완전탐색 풀이
문제 요약 — 프로그래머스 입문 문제 — 기초 구현 풀이
문제 요약 — 프로그래머스 입문 문제 — 기초 구현 풀이
문제 요약 — 프로그래머스 입문 문제 — 기초 구현 풀이
핵심 접근 — 홀수면 가운데 1글자, 짝수면 가운데 2글자를 substr로 추출 — O(1)
문제 요약 — 프로그래머스 입문 문제 — 기초 구현 풀이
옛날 전화기 다이얼로 단어를 입력할 때 걸리는 시간을 구하시오.
그룹 단어: 단어에 존재하는 모든 문자가 연속해서 나타나는 경우
0부터 9까지의 숫자 중 일부가 numbers 배열에 담겨 있을 때,
알파벳 대소문자로 이루어진 단어가 주어졌을 때,
'개수를 센다'는 문제를 보면 반사적으로 map을 꺼내게 되는데, 키 범위가 알파벳 26자로 고정이면 이야기가 달라진다. 두 구현을 각각 짜서 무엇이 갈리는지 비교했다.
전화번호가 문자열 phone_number로 주어질 때,
정수 배열 absolutes와 부호 배열 signs가 주어질 때,
영어 대소문자와 공백으로 이루어진 문자열에서 단어의 개수를 구한다.
문자열에서 소괄호 '()' 와 대괄호 '[]' 의 균형이 맞는지 판단
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램
큐·스택·문자열 세 문제를 풀었는데 막힌 지점은 전부 알고리즘 밖이었다. 빈 컨테이너에서 front·top·pop을 부르면 미정의 동작이고, 공백이 섞인 입력은 읽는 방식부터 골라야 한다.
vector
arr에서 int divisor로 나누어 떨어지는 원소만 골라 오름차순 정렬해서 반환. vector
seoul에서 'Kim'의 인덱스를 찾아 '김서방은 x에 있다'를 반환 — find + 이터레이터 거리 계산 push·pop·size·empty·top 명령을 처리하는 스택 구현 — STL stack 사용
괄호 문자열(PS)이 주어질 때, 올바른 괄호 문자열(VPS)인지 판단
언리얼에서 C++ 클래스를 만들면 VS에서 자동완성과 오류 표시가 바로 붙지 않는다. 'VS로는 안 된다'고 결론 내리기 전에 Rider와 같은 작업을 나란히 돌려 원인을 확인했다.
핵심 접근 — 선형 탐색으로 'Kim'의 인덱스를 찾아 문자열로 조립 — O(n)
배열에서 원소의 위치를 찾는 두 방법. 둘 다 O(n)이라 성능 차이는 없지만 std::find는 위치가 아니라 이터레이터를 돌려주기 때문에 한 단계가 더 붙는다.
백준 5597 — bool 배열 인덱스 마킹으로 미제출자 찾기
백준 10807 — 고정 배열 저장 후 선형 탐색으로 개수 세기
백준 10818 — 단일 순회로 최솟값·최댓값 찾기
난이도가 비슷한 배열 기초 세 문제인데 저장 전략은 셋 다 달랐다. 배열을 아예 안 쓰거나, 고정 배열을 쓰거나, 값을 인덱스로 써서 정렬까지 생략하거나 — 그 갈림길의 기준.
백트래킹을 'DFS인데 되돌아가는 것'으로만 알면 문제 앞에서 구분이 안 된다. 인접 행렬과 인접 리스트 선택 기준, DFS와 BFS를 나누는 축, 그리고 가지치기 조건.
순회 순서만 외우면 문제 앞에서 다시 헷갈린다. 전위는 복사, 중위는 정렬 출력, 후위는 삭제·계산으로 붙여 두고, 배열 표현과 인접 리스트의 갈림길, BST가 O(N)으로 무너지는 조건까지.
백준 2562 — max_element로 최댓값과 위치(1-based) 찾기
백준 1000 — cin/cout 기본 입출력 익히기
max_element가 돌려준 이터레이터에서 begin()을 빼면 인덱스가 나온다. 값도 위치도 맞게 구했는데 오답이 난 이유는 문제가 요구한 '몇 번째'가 1부터 세는 값이었기 때문.
시뮬레이션에서 시간을 잃는 건 알고리즘이 아니라 좌표 변환 규칙을 매번 다시 떠올리는 일이다. dy/dx 방향 배열과 경계 체크, 전치·대칭·회전을 코드로 굳혀 두기.
연속된 세 개의 정수를 더해 12가 되는 경우는 3, 4, 5입니다. 두 정수 num과 total이 주어집니다. 연속된 수 num개를 더한 값이 total이 될 때, 정수 배열을 오름차순으로 담아 return하도록 solution함수를 완성해보세요.
total이 num으로 나눠떨어지는 경우와 아닌 경우로 갈라 풀다 루프 변수 추적이 꼬였다. 필요한 값이 첫 항 하나뿐이라는 걸 알고 분기를 통째로 없앤 과정.
머쓱이는 태어난 지 6개월 된 조카를 돌보고 있습니다. 조카는 아직 'aya', 'ye', 'woo', 'ma' 네 가지 발음을 최대 한 번씩 사용해 조합한(이어 붙인) 발음밖에 하지 못합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요.
문자열을 앞에서부터 토큰으로 갉아먹는 문제. 알고리즘이 아니라 실패 판정을 어느 루프에 두느냐 때문에 답이 어긋났다. string::compare 3인자 오버로드와 조기 실패 제거.
문제 요약 — 다음에 올 숫자
배열이 빠른 이유는 연속 메모리 하나로 전부 설명된다. 거기서 O(1) 임의 접근과 중간 삽입 비용이 갈리는 지점, 그리고 그 위에서 정렬 알고리즘을 고르는 기준.
정수 num1과 num2가 매개변수로 주어집니다. 두 수가 같으면 1 다르면 -1을 retrun하도록 solution 함수를 완성해주세요.
문제 요약 — 나이출력
재귀는 기저 조건과 문제 축소 두 부품으로 조립된다. 호출 트리로 O(N)·O(2^N)·O(logN)을 읽는 법, 피보나치의 지수 폭발을 메모이제이션으로 O(N)까지 끌어내린 과정.
문제 요약 — 프로그래머스 입문 문제 — 기초 구현 풀이
코테에서 시간을 잃는 두 지점 — 복잡도를 잘못 잡아 시간 초과가 나거나, 입력 파싱을 손으로 짜다 시간을 태우거나. 입력 최대값에서 복잡도를 역산하는 기준과 stringstream 파싱.
문제 요약 — 프로그래머스 입문 문제 — 기초 구현 풀이
문제 요약 — 프로그래머스 입문 문제 — 기초 구현 풀이
문제를 읽자마자 코드를 치던 순서를 바꿨다. 분석에 70%를 쓰는 4단계 절차와, 로컬에서 통과한 코드가 채점 서버에서 컴파일 에러가 나는 걸 막는 -std=c++17 환경 세팅.