이진탐색(Binary Search) 알고리즘 개념 및 구현

이진탐색은 정말 많은 알고리즘 문제에서 중요하게 활용된다.이진탐색을 알아보기 전, 순차탐색이 뭔지 이해해보자(순차탐색을 알고 있다면 바로 이진탐색으로 넘어가면 된다.) 순차탐색순차탐색이란 N개의 데이터가 있을 때, 차례대로 하나씩 확인하여 어떠한 처리를 해주는 것을 의미한다.대부분의 문제에서 사용되는데, 주로 그리디 문제에서 순차탐색이 사용된다. 예를 들어서 거스름돈 동전 개수 문제가 있다.거스름돈 동전을 최소한으로 거슬러주는 문제를 해결할 때, 가장 큰 단위의 화폐부터 차례대로 거슬러준다.이 때, 화폐의 단위를 큰 것부터 작은 것의 순서로 거슬러줄 때 순차 탐색을 사용한다. 이처럼 순차탐색은 자주 사용되는 데, 개념을 한 줄로 정리하는 아래와 같다. 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부..

• format_list_bulleted CodingTest/algorithm
• · 2024. 10. 1.
• textsms

자료구조 - 스택(Stack), 큐(Queue) 개념 정리

배경설명자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다.자료구조에 따라서 해결할 수 있는 문제와, 더욱 시간을 단축할 수 있는 알고리즘들이 존재ㅎ나다.그 중, 오늘 설명할 스택과 큐는 Push와 Pop이라는 두가지 함수를 중심으로 작동한다. 두 연산의 경우 Overflow와 Underflow 문제를 야기할 수 있기 때문에 함께 고민해야 한다. 삽입(PUSH)자료구조에 데이터를 삽입한다.삭제(POP)자료구조에 있는 데이터를 삭제한다.Overflow 특정한 자료구조가 수용할 수 있는 데이터의 크기를 넘어선 상태에서 데이터를 삽입하는 연산을 수행할 때 발생한다.(수용 가능 용량이 초과한 상태에서 PUSH 연산을 하는 경우)Underflow특정 자료구조에 데이터가 전혀 들어 있지 않은 상태에..

• format_list_bulleted CodingTest/algorithm
• · 2024. 9. 25.
• textsms

구현 (implementation) 정복하기

유형 설명코딩테스트에서 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.추상적인 설명과 같이, 모든 범위의 코딩 테스트 문제 유형을 포함한다.대부분의 구현 문제는 풀이를 떠올리기는 쉽지만, 소스코드로 옮기는 과정이 어려운 문제를 의미한다.(문제의 알고리즘의 설계를 했음에도, 구현은 먼저 풀 수 있는 문제가 없을 때 마지막으로 푸는 것이 좋다.) 구현 문제의 경우, 사소한 조건이 많을수록 어려운 문제로 평가된다.(간단한 알고리즘에 비해 코드가 길어지는 경우, 특정 소수점 자리까지 출력해야되는 경우, 문자열을 문자 단위로 파싱해야되는 경우 등...) 대부분 구현 문제는 언어의 문법을 잘 이해하고, 다양한 활용 경험이 동반되어야 비로소 체감 난이도가 내려간다.따라서, 많이 경험하고 이해하고 있어..

• format_list_bulleted CodingTest/algorithm
• · 2024. 9. 23.
• textsms

그리디 알고리즘 (Greedy) 완전 정복하기 (백준 11914 거스름돈)

그리디 알고리즘 : 현 상황에서 가장 좋은 것들만 고르는 방법 (탐욕 알고리즘이라고도 불린다.) 그리디 알고리즘의 특징매 순간 가장 좋은 (점수가 높은) 것만을 선택하며 현재 선택이 미래에 미칠 영향은 고려하지 않는다. (근시안적 선택)사전에 알고리즘을 숙지하지 않아도 해결할 수 있는 문제 유형이다.기준에 따라 좋은 것을 선택하는 알고리즘이기에, 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준이 함께 포함되며, 따라서 그리디 알고리즘 문제는 자주 정렬 알고리즘과 함께 출제되는 경향이 있다.최적의 해를 찾는 것에 기반하여 최적화 문제를 해결하기 위한 알고리즘으로 불린다. 주로 그리디 알고리즘 유형의 문제는 창의력, 즉, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한..

• format_list_bulleted CodingTest/algorithm
• · 2024. 9. 22.
• textsms