본문 바로가기

전체 글17

다이나믹 프로그래밍 핵심 정리 코딩테스트에 거의 항상 출제되는 다이나믹 프로그래밍(Dynamic Programming, DP)에 대해 정리해 보겠습니다.DP의 기본 원리와 접근법다이나믹 프로그래밍(Dynamic Programming, DP)은 처음 들으면 어려워 보이지만, 사실 중학교에서 배우는 수학적 귀납법과 비슷한 원리입니다.수학적 귀납법수학적 귀납법을 가볍게 복습해 봅시다. 어떤 주장이 모든 자연수에 대해 성립한다는 것을 증명할 때, 우리는 두 단계로 나눠 증명합니다:기본 단계: 가장 작은 수(보통 1)에서 성립함을 보여줍니다.귀납 단계: n에서 성립한다면, n+1에서도 성립한다는 것을 보여줍니다.예를 들어, "1부터 n까지의 자연수 합은 n(n+1)/2이다"라는 공식을 증명할 때:기본 단계: n=1일 때, 1 = 1(1+1)/.. 2025. 3. 25.
모른다는 것도 모르는 것을 알기 위해서 Unknown Unknown의 개념소프트웨어 개발 세계에서 "unknown unknown"이란 우리가 모른다는 사실조차 인식하지 못하는 지식의 영역을 의미합니다. 이 개념은 전 미국 국방장관 도널드 럼스펠드의 유명한 말에서 유래했습니다: "우리가 아는 것들이 있고(known knowns), 우리가 모른다는 것을 아는 것들이 있으며(known unknowns), 우리가 모른다는 사실조차 모르는 것들(unknown unknowns)이 있다."프로그래밍 맥락에서 이 세 가지 지식 상태를 생각해 봅시다:Known knowns: 개발자가 확실히 알고 있는 지식입니다. 예를 들어, 자신이 능숙한 프로그래밍 언어의 문법, 자신이 만든 코드의 기능, 또는 자주 사용하는 라이브러리의 API 등이 여기에 해당합니다.Kno.. 2025. 3. 24.
이분탐색 까다로운 구현 마스터하기 알고리즘 문제를 풀다 보면 자주 만나게 되는 이분탐색(Binary Search)은 개념은 단순하지만, 막상 구현하려면 생각보다 많은 함정에 빠지기 쉽습니다. 아래와 같은 경우를 다 고려해야 하기 때문이죠:시작점이나 끝점을 넘어가는 경우. ex) 배열에 (3,5,7,9)가 저장되어 있는데 1을 찾음답이 없는 경우. ex) 배열에 (3,5,7,9)가 저장되어 있는데 4를 찾음양 끝점이 답인 경우. ex) 배열에 (3,5,7,9)가 저장되어 있는데 3을 찾음배열에 숫자가 중복되는 경우. ex) 배열에 (3,3,4,4,5,5,5,7,7,9,9)가 저장되어 있는데 가장 오른쪽에 있는 5를 찾음특정 수 미만, 초과, 이하, 이상인 수 찾기. ex) 배열에 (3,5,7,9)가 저장되어 있는데 5 이상인 수 중 최솟값.. 2025. 3. 21.
이분탐색 기초적인 개념 이해하기 오늘은 알고리즘의 세계에서 가장 기본이면서도 강력한 무기 중 하나인 '이분탐색(Binary Search)'에 대해 알아보려고 합니다. 프로그래밍 문제를 해결하거나 실제 애플리케이션을 개발할 때 검색 알고리즘의 선택은 성능에 큰 영향을 미칩니다. 이번 글에서는 이분탐색의 기본 개념부터 차근차근 살펴보겠습니다. 이분탐색이란? (목적과 개요)이분탐색은 정렬된 범위 내에서 특정 값을 효율적으로 찾기 위한 알고리즘입니다. 이를 쉽게 이해하기 위해 '업다운 게임'을 떠올려 보세요. 컴퓨터가 1부터 1,000,000 사이의 숫자를 하나 생각하고, 여러분이 숫자를 말하면 컴퓨터는 "업"(더 큰 수를 말하세요) 또는 "다운"(더 작은 수를 말하세요)이라고 알려줍니다. 여러분은 최소 횟수로 컴퓨터가 생각한 수를 맞추면 되.. 2025. 3. 19.
코딩테스트, 도대체 왜 하는 것일까? "코딩테스트에 쓰이는 것들은 실무에서 안 쓰지 않아?""이거 공부해서 어디에 써?" 제가 학원 강사와 과외 수업을 진행하면서 가장 많이 들었던 질문들입니다. 여기에 대한 답을 정리해 두었습니다. 기업이 코딩테스트를 실시하는 이유코딩테스트는 현대판 수능이다저는 이런 질문을 받을 때마다 코딩테스트를 수능에 비유합니다.서울대에서 수능 성적이 좋은 학생을 선호하는 이유는 무엇일까요? 수능 성적이 좋다는 것은 그만큼 학생의 종합적인 사고력이 뛰어나다는 의미입니다. 이런 사람은 어떤 분야에 투입되어도 성과를 낼 가능성이 높습니다. 국어국문학과를 가도, 수학자가 되어도, 음악을 해도, 심지어 농사를 지어도 말입니다."나는 국어국문학과에 갈 건데 왜 수학 공부를 해야 하지?"라고 의문을 품을 수 있습니다. 하지만 수능.. 2025. 3. 17.

티스토리툴바