본문 바로가기

Algorithm

 (38)
[스택] - 뒤에 있는 큰 수 찾기 예제 1️⃣ 스택(Stack)이란?스택(Stack) 은 후입선출 (LIFO, Last In First Out) 방식으로 동작하는 자료구조입니다.즉, 가장 나중에 추가된 요소가 가장 먼저 제거되는 구조를 가집니다.📌 스택의 특징 ✅ LIFO (Last In First Out) 원칙 → 마지막에 들어온 데이터가 먼저 나감 ✅ Push (삽입), Pop (삭제) 연산을 사용 ✅ Top(최상단) 원소만 접근 가능 ✅ 중간에 있는 원소 접근 불가능✅ 재귀(Recursion), 괄호 검증, 백트래킹 등 다양한 알고리즘에 활용됨 2️⃣ 스택 주요 연산(메서드)자바에서는 `Stack`클래스 또는 `Deque` (LinkedList 활용) 을 사용하여 구현할 수 있습니다.자주 사용되는 메서드를 정리하면 다음과 같습니다. 연..
동적 프로그래밍(Dynamic Programming) 동적 프로그래밍(Dynamic Programming)이란?동적 프로그래밍(DP)은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 문제 해결 전략입니다. 부분 문제의 중복과 최적 부분 구조라는 두 가지 속성을 이용하여 효율적으로 계산을 수행합니다. 이를 통해, 동일한 부분 문제를 반복적으로 계산하는 대신 저장된 결과(메모이제이션)를 활용하여 실행 시간을 줄이는 방법입니다. 1. 동적 프로그래밍의 두 가지 핵심 속성최적 부분 구조 (Optimal Substructure) 문제를 여러 작은 문제로 나눌 수 있고, 작은 문제의 최적 결과를 조합하여 전체 문제의 최적 결과를 구할 수 있는 속성입니다.예: 피보나치 수열의 F(n) = F(n - 1) + F(n - 2)부분 문제 중복 (Overlapping Sub..
[구현] - N개의 최소공배수 이번에 다뤄볼 문제는 알고리즘에 자주 나오는 `구현` 유형 문제입니다. `구현` 유형의 문제에 대한 정리는 아래 블로깅에서 잘 정리해 두었으니 참고하시길 바랍니다. 알고리즘의 구현 이란? [구현] - 둘만의 암호구현(Implementation) 유형의 알고리즘 문제는 주어진 조건을 그대로 구현하고 해결하는 것을 주 목적으로 하는 문제 유형입니다. 구현 문제는 대체로 문제에서 요구하는 규칙이나 절차를 코드로 정wanglan.tistory.com 문제는 프로그래머스에서 참고하였습니다. [프로그래머스] - N개의 최소공배수 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 설명 두 수의 최소공배수(Least..
[완전탐색] - 카펫 완전탐색(Brute Force)은 가능한 모든 경우를 하나씩 시도해보며 정답을 찾는 알고리즘 기법입니다. 완전탐색은 효율성보다는 정확성을 우선시하며, 문제의 모든 가능한 해를 다 찾아보고 비교하기 때문에 답을 반드시 찾을 수 있는 보장된 방법입니다. 이 방법은 경우의 수가 작은 문제에 적합하며, 보통 다음과 같은 유형의 문제에 사용됩니다:순열과 조합 문제: 요소를 나열하거나 선택해 경우의 수를 모두 따져봄.부분집합 문제: 각 원소를 선택하거나 선택하지 않는 모든 경우의 수를 탐색.백트래킹 문제: 최적의 경로를 찾기 위해 트리를 구성해 가능한 모든 경로 탐색.장단점장점: 간단하게 구현 가능하고 모든 경우를 다 탐색하므로 정확한 결과를 보장.단점: 경우의 수가 많아지면 수행 시간이 기하급수적으로 증가해 비효..
[오버플로우] - 피보나치 수 알고리즘을 작성하다 보면, 수가 급격하게 커지면서 특정한 경우에 런타임에러가 발생하는 경우를 볼 수 있습니다. 이는 피보나치 수열과 같이 값이 급격하게 상승하는 특정한 수열들에서 에러가 발생하고 이런 경우를 `오버플로우`라고 합니다. `오버플로우(overflow)` 는 컴퓨터에서 정수나 실수를 표현할 수 있는 범위를 초과하는 상황을 말합니다.예를 들어, 자바의 int 자료형은 약 -21억부터 +21억까지의 범위를 갖는데, 계산 중 이 범위를 넘어서면 잘못된 값이 나옵니다. 예를 들어, 2147483647 + 1을 하면 가장 작은 값인 -2147483648로 돌아가죠. 피보나치 수를 계산하는 문제로 예를 들어 보겠습니다.[프로그래머스] - 피보나치 수 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 T..
[구현] - 바탕화면 정리 이번에 다뤄 볼 문제는, 코딩테스트에 자주 출제되는 메인 유형은 아니지만 여러가지 개념이 포함된 문제였습니다. 기본적으로 들어가는 개념은 `2차원 배열 탐색` 과 `최소 범위 찾기` 정도로 정리할 수 있습니다. 이 두 가지의 개념을 문제의 조건에 맞춰 `구현`하는 것이 핵심이라 생각하고 있습니다.  알고리즘을 구현하는 팁 등에 대해서는 이전에 포스팅에서 잘 정리해 두었으니 참고하시길 바랍니다. [구현] - 둘만의 암호구현(Implementation) 유형의 알고리즘 문제는 주어진 조건을 그대로 구현하고 해결하는 것을 주 목적으로 하는 문제 유형입니다. 구현 문제는 대체로 문제에서 요구하는 규칙이나 절차를 코드로 정wanglan.tistory.com[프로그래머스] - 바탕화면 정리 프로그래머스SW개발자를 ..
[해시 맵] - 달리기 경주 오늘은 자료구조의 해시 테이블 중 `HashMap` 을 사용한 문제를 풀어보려고 합니다. 자료구조 중 해시 테이블에 대한 내용은 앞선 게시물에 자세히 정리되어 있으니 참고하시면 좋을 것 같습니다. [해시 테이블] - 개인정보 수집 유효기간`해시 테이블`(혹은 해시 맵)은 자료 구조의 일종으로, 키-값 쌍을 저장하는 데 사용됩니다. 해시 테이블은 매우 빠른 데이터 조회, 삽입 및 삭제를 지원하며, 평균적으로 `O(1)`의 시간 복잡도로wanglan.tistory.com [프로그래머스] - 달리기 경주 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 설명 얀에서는 매년 달리기 경주가 열립니다. 해설진들..
[해시 테이블] - 개인정보 수집 유효기간 `해시 테이블`(혹은 해시 맵)은 자료 구조의 일종으로, 키-값 쌍을 저장하는 데 사용됩니다. 해시 테이블은 매우 빠른 데이터 조회, 삽입 및 삭제를 지원하며, 평균적으로 `O(1)`의 시간 복잡도로 작업을 수행할 수 있습니다. 아래에서 해시 테이블의 주요 개념, 작동 원리 및 장단점에 대해 자세히 설명하겠습니다.  1. 기본 개념키(Key): 데이터를 식별하는 데 사용되는 값. 키는 고유해야 하며, 중복이 없어야 합니다.값(Value): 키와 연관된 데이터. 하나의 키는 하나의 값과 연결됩니다.해시 함수(Hash Function): 키를 해시 값으로 변환하는 함수. 해시 값은 해시 테이블의 인덱스를 결정합니다.버킷(Bucket): 해시 테이블에서 키와 값이 저장되는 공간. 각 버킷은 여러 키-값 쌍을 ..

티스토리툴바