자료구조를 공부하다 보면 배열 다음으로 만나게 되는 것이 바로 연결 리스트(Linked List)입니다. 배열의 한계를 보완하면서도 동적으로 크기를 조절할 수 있는 연결 리스트는 많은 프로그래밍 상황에서 핵심적인 역할을 합니다. 오늘은 연결 리스트의 개념부터 실제 구현, 그리고 실무 활용까지 체계적으로 알아보겠습니다.연결 리스트란 무엇인가?연결 리스트는 리스트 내의 요소(노드)들을 포인터로 연결하여 관리하는 선형 자료구조입니다. 마치 기차처럼 각 칸(노드)이 다음 칸을 가리키는 연결고리로 이어져 있다고 생각하면 됩니다.연결 리스트의 핵심 구성 요소노드(Node): 데이터와 다음 요소에 대한 포인터를 가진 기본 단위HEAD: 첫 번째 노드를 가리키는 포인터TAIL: 마지막 노드를 가리키는 포인터// 노드의..

최근 실전 면접 라이브 코딩에서 "두 개의 스택으로 큐를 구현하라"는 문제를 처음 접했습니다. 평소에는 백준, 프로그래머스 등에서 알고리즘 문제만 풀어왔기에, 이렇게 직접 자료구조를 구현하는 문제는 예상치 못해 당황스러웠습니다. 이 글에서는 그때의 경험을 바탕으로, 문제의 개념과 구현 방법, 그리고 느낀 점을 정리합니다.문제 소개: 알고리즘 문제만 풀다가 만난 직접 구현 과제자료구조 면접에서 "스택(Stack)과 큐(Queue)의 차이"는 종종 등장하지만, 실제로 스택 두 개로 큐를 직접 구현하라는 문제는 저에게도 처음이었습니다. 단순히 개념을 아는 것과, 직접 코드를 짜는 것은 완전히 다르다는 점을 실감했습니다.스택(Stack): LIFO(Last-In-First-Out, 후입선출)큐(Queue): F..

문제 요약5×5 빙고판에 1~25까지의 수가 한 번씩 적혀 있습니다.사회자가 25개의 수를 한 번씩 부를 때,각 수가 불릴 때마다 빙고판에서 해당 수를 지웁니다.가로, 세로, 대각선 중 5개가 모두 지워진 줄이 3개 이상이 되는 순간철수는 "빙고!"를 외치게 됩니다.사회자가 몇 번째 수를 부른 후 빙고가 완성되는지 구하는 문제입니다.접근 방식빙고판과 사회자가 부르는 수의 순서를 2차원 리스트로 입력받습니다.각 숫자가 불릴 때마다, 빙고판에서 해당 숫자를 찾아 체크합니다.매번 가로, 세로, 두 대각선에 대해5개가 모두 체크된 줄(빙고 줄)의 개수를 셉니다.빙고 줄이 3개 이상이 되는 순간,그때까지 부른 수의 개수를 출력하고 종료합니다.실생활 비유로 설명하면,"빙고판에 체크 표시를 하면서가로, 세로, 대각선..

문제 요약9×9 크기의 스도쿠 보드가 주어집니다.각 행, 각 열, 그리고 3×3 박스마다 1~9가 중복 없이 한 번씩만 등장해야 합니다.아직 채워지지 않은 칸은 0으로 주어지며,모든 빈 칸을 조건에 맞게 채운 "가장 사전순으로 앞서는" 해답을 출력하는 문제입니다.접근 방식이 문제는 대표적인 "백트래킹" 유형입니다.먼저, 빈 칸(0)의 좌표를 모두 저장합니다.각 빈 칸에 대해 1~9 중 가능한 숫자를 하나씩 시도합니다.숫자를 넣었을 때 행, 열, 3×3 박스에 중복이 없으면 다음 칸으로 진행합니다.만약 모든 빈 칸을 채웠다면, 그 즉시 답을 출력하고 탐색을 종료합니다(사전순 보장).불가능하면 백트래킹(원상복구)하여 다른 숫자를 시도합니다.실생활 비유로 설명하면,"빈 칸마다 1~9 중 가능한 숫자를 하나씩 ..

문제 요약N개의 집이 일렬로 있고, 각 집을 빨강, 초록, 파랑 중 하나로 칠해야 합니다.각 집을 각 색으로 칠하는 비용이 주어질 때, 1번 집의 색은 2번, N번 집의 색과 달라야 하고 N번 집의 색은 N-1번, 1번 집의 색과 달라야 하며 나머지 집도 인접한 집과 색이 달라야 합니다.이 조건을 모두 만족하면서 모든 집을 칠하는 최소 비용을 구하는 문제입니다.접근 방식이 문제는 "원형" 형태의 인접 제약이 추가된 RGB거리 문제입니다.즉, 1번 집과 N번 집도 서로 색이 달라야 하므로,단순한 DP로는 해결이 어렵고,1번 집의 색을 고정한 뒤, 1번 집을 빨강/초록/파랑 각각으로 칠하는 경우를 모두 시도 그에 따라 N번 집이 같은 색이 되지 않도록 DP를 돌려 세 경우 중 최소값을 정답으로 선..

문제 요약DDR(Dance Dance Revolution) 게임에서,중앙(0)과 네 방향(1: 위, 2: 왼쪽, 3: 아래, 4: 오른쪽) 발판이 있습니다.처음엔 두 발 모두 중앙(0)에 있고, 주어진 스텝 순서대로 한 발씩 움직여야 합니다. 같은 위치에 두 발이 동시에 있을 수는 없습니다(시작 제외).한 발이 이미 해당 위치에 있다면, 그 발로 반복해서 눌러야 합니다.발을 움직일 때 드는 힘은 다음과 같습니다:중앙(0) → 다른 위치: 2같은 위치 반복: 1인접한 위치로 이동: 3반대편(예: 위↔아래, 왼↔오른) 이동: 4모든 스텝을 밟는 데 필요한 최소 힘을 구하는 문제입니다.접근 방식이 문제는 "상태"를 잘 정의해서 DP(동적 프로그래밍)로 해결해야 합니다.각 스텝마다, 왼발과 오른발이 각각 어디..

문제 요약두 개의 정수 배열 A, B가 주어집니다.각 배열에서 연속된 부분 구간(부 배열)을 하나씩 골라,A의 부 배열의 합 + B의 부 배열의 합 = T가 되는 쌍의 개수를 구하는 문제입니다.예를 들어,A = [1, 3, 1, 2], B = [1, 3, 2], T = 5라면A의 부 배열과 B의 부 배열을 각각 골라 합이 5가 되는 경우의 수를 모두 세야 합니다.접근 방식처음에는 모든 부 배열 쌍을 직접 만들어 합을 비교하는 완전탐색을 떠올릴 수 있습니다.하지만 배열의 길이가 최대 1,000이므로,O(N² × M²) 방식은 시간 초과가 발생합니다.여기서 "부 배열의 합"이라는 조건에 주목하면,각 배열의 모든 부 배열 합을 미리 구해놓고,A의 부 배열 합 + B의 부 배열 합 = T즉, A의 부 배열 합이..

문제 요약여러 명의 플레이어가 각각 1~1,000,000 사이의 서로 다른 수가 적힌 카드를 한 장씩 받습니다.각 플레이어는 본인을 제외한 모든 플레이어와 한 번씩 결투를 하며, 내 카드의 수로 상대의 수를 나누어 떨어지면 승리(+1점), 반대로 상대가 내 수를 나누어 떨어뜨리면 패배(-1점), 둘 다 아니면 무승부(점수 변화 없음)이렇게 모든 결투가 끝난 뒤, 각 플레이어의 최종 점수를 구하는 문제입니다.접근 방식처음에는 모든 플레이어 쌍을 비교하는 완전탐색을 떠올릴 수 있습니다.하지만 플레이어 수 N이 최대 100,000명, 카드 숫자 범위도 1,000,000까지라서O(N²) 방식은 시간 초과가 발생합니다.여기서 "나누어 떨어진다"는 조건에 주목하면,각 카드의 배수(2배, 3배, ...)가 다른..

들어가며프론트엔드 개발을 시작할 때 가장 먼저 만나는 코드 중 하나가 바로 입니다. 하지만 이 한 줄이 웹 페이지 렌더링에 미치는 영향을 정확히 아는 개발자는 많지 않습니다. 이 글에서는 DOCTYPE의 역할부터 실무에서의 중요성까지 체계적으로 알아보겠습니다.DOCTYPE이란? 브라우저에게 주는 첫 번째 신호기본 정의DOCTYPE(Document Type Definition)은 HTML 문서의 맨 위에 위치하여 브라우저에게 해당 문서가 어떤 HTML 버전으로 작성되었는지 알려주는 선언문입니다. 안녕하세요!💡 핵심 포인트: DOCTYPE은 HTML 요소가 아니라 브라우저에게 주는 지시사항입니다.실생활 비유: 요리 레시피의 조리법 버전DOCTYPE을 이해하는 가장 쉬운 방법은 요리 레시피에 비유하는 ..

들어가며백엔드 개발을 공부하다 보면 URI, URL, URN이라는 용어를 자주 접하게 됩니다. 하지만 이 세 개념의 차이점을 명확히 구분하지 못하는 경우가 많습니다. 특히 면접에서도 자주 나오는 질문 중 하나죠. 이 글에서는 URI, URL, URN의 차이점과 실무에서의 활용법을 체계적으로 알아보겠습니다.기본 개념: URI, URL, URN이란?전체 구조 이해하기URI (Uniform Resource Identifier)├── URL (Uniform Resource Locator)└── URN (Uniform Resource Name)💡 핵심 포인트: URI는 URL과 URN을 포함하는 상위 개념입니다.정의 비교표구분의미특징예시URI자원을 식별하는 문자열URL + URN을 포함하는 상위 개념모든 웹 주..