My Tech Blog (Algorithm/알고리즘)

스택(Stack)개요"스택"은 데이터를 쌓아서 사용하는 자료구조로, "후입선출(LIFO, Last In First Out)" 방식으로 작동한다. 즉, 나중에 들어간 데이터가 먼저 나오는 구조이다. 스택은 주로 함수 호출, 계산기 프로그램에서 수식 계산, 또는 브라우저의 뒤로 가기 기능 등에서 사용된다.* 이와 반대의 "선입선출(FIFO, First In First Out)" 구조의 자료구조를 '큐'라고 한다.   스택을 활용한 코딩테스트 문제는 유형이 정해져 있다. 문제를 잘 읽어보고 데이터를 쌓아 올린다든지, 나중에 쌓은 데이터를 먼저 처리하는 방식이면 스택을 활용하면 된다.  스택을 사용하는 문제 유형 ✅ 괄호 유효성 검사주어진 문자열에서 괄호의 짝이 맞는지 확인하는 문제스택을 사용해 여는 괄호는 스..

코테 문제 풀 때 알고리즘이나 자료구조도 공부해야 하지만, 코드를 작성하는 방법도 중요하다.클린 코드를 작성하기 위해서는 아래 세 가지 습관을 들여야 한다.하루 아침에 코드 쓰는 습관이 바뀌지는 않겠지만 매번 코드를 작성할 때마다 이러한 습관을 염두에 두고 작성하다 보면 점차 클린 코드 작성 능력이 향상될 것이라고 기대한다.  1. 조기반환 (early return)조기 리턴(early return)은 조건이 충족되면 함수나 메서드에서 바로 결과를 반환하는 프로그래밍 기법이다. 이렇게 하면 불필요한 계산을 피하고 코드의 가독성을 높일 수 있다.예를 들어, totalPrice 함수에서 가격이 100을 초과하는 경우 바로 할인을 적용하고 결과를 반환하는 코드를 짤 때, 조기 리턴을 하지 않으면 할인 로직을 ..

정렬(Sort)개요데이터를 오름차순 또는 내림차순으로 배열하거나 리스트의 요소를 정렬하는 과정이다.  정렬을 활용한 코딩테스트 문제는 매우 다양하다. 정렬 문제는 문제를 풀 때는 정렬 기준을 정확히 파악하고, 그에 맞는 알고리즘을 선택하는 것이 중요하다. 정렬 알고리즘, 이진 탐색, 투 포인터, 빈도수 계산 등 다양한 기술을 조합해 해결해야 하는 문제들이 많다.  주어진 조건을 Arrays.sort() 를 이용해서 정렬해야 하는 문제도 있고, 정렬 기준을 사용자 정의 객체에 맞게 지정해야 하는 경우, Comparator 인터페이스를 구현한 객체를 Collections.sort() 또는 Arrays.sort()에 전달하여 정렬하면 되고, 이 때 Java 8 이상에서는 Comparator를 람다 표현식으로 ..

그리디 알고리즘(Greedy Algorithm)개요greedy형용사 - 1. 탐욕스러운 2.욕심 많은  그리디 알고리즘(Greedy Algorithm)은 매 순간 가장 최적이라고 판단되는 선택을 반복하여 최종 해답을 구하는 알고리즘이다. 즉, 현재 단계에서의 최선의 선택이 최종적으로도 최적해(Optimal Solution)가 된다고 가정하고 문제를 해결한다. 코딩테스트에서 만날 경우 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형지역 최적해(Local Optimum) → 전역 최적해(Global Optimum) 보장 가능해야 함탐욕적 선택(Greedy Choice)과 최적 부분 구조(Optimal Substructure) 만족✅ 동적 프로그래밍(Dynamic Programming)과 차이..