My Tech Blog (알고리즘)

출처: 시나공, 꿈꾸는 라이언

📑 1. 문제설명💡 2. 풀이 과정 문제를 요약하면 토너먼트 게임에서 특정한 번호의 두 참가자가 만날 때 까지 몇 번의 경기를 진행해야 하는지 횟수를 구하는 문제이다.  처음에 참가자들은 1부터 N까지 번호를 받는다.그리고 다음 라운드에 진출한 참가자들은 다시 1부터 N/2 까지의 번호를 받는다. 입출력 예N=8, A=4, B=7 이 경우 8명의 참가자들이 경기를 할 때 4번 선수와 7번 선수가 만날 때까지의 경기 횟수를 아래 그림으로 그려 보았다.각 라운드에서 4번과 7번은 항상 이겨서 다음 라운드로 진출한다고 가정하고 풀어야 하는 문제이다.4번과 7번은 계속 이겨서 다음 라운드로 진출한다4번은 3번을 이기고, 1 또는 2번을 이겨서 총 2번 이긴다7번은 8번을 이기고, 5 또는 6번을 이겨서 총 ..

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

📑 1. 문제설명10진수를 입력받아 2진수로 변환해 반환하는 solution() 함수를 구현하세요 제약조건decimal은 1이상 10억 미만의 자연수입출력 예decimalreturn10101027110111234511000000111001 💡 2. 풀이 과정10진수를 2진수로 표현하는 과정은 이미 수학적으로 증명된 것이기 때문에 간단하게 적는다.10진수 N을 2로 나눈 나머지, 즉 %2 연산을 한 값을 저장하고, N은 다시 2로 나눈다.몫이 0이 아니라면 나머지를 버리고 다시 1을 수행한다모든 과정이 끝나고 1에서 저장한 수를 뒤부터 순서대로 가져와 붙인다.  예를 들어 십진수 13을 위 과정대로 2진수로 변환하는 모습은 위 그림과 같다. 13을 2로 나누어가면서 나눈 나머지를 순서대로 저장한 후, ..

정렬(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)과 차이..

📑 1. 문제설명💡 2. 접근방식자료 만들 생각에 벌써부터 피곤하다. 하하하 문제 풀이에 앞서, 명색이 그래프 문제인 만큼 그래프에 대해 간략히 설명하고자 한다.2-1. 그래프의 구조노드: 원(circle)으로 표시하고, 숫자로 번호를 적는다.간선: 노드를 연결하는 선(segment)으로, 모든 간선이 양방향임을 보여주기 위해 화살표 없이 직선으로 그린다.return 하고자 하는 값은 1번 노드에서 가장 멀리 떨어진 노드의 수 이다.즉 1번 노드에서 다른 노드들로 이동하는 최단 거리를 계산해서 최단 거리가 가장 먼 노드들이 몇 개인지를 구해야 한다. 2-2. 해결 방법(1) 인접 리스트로 그래프 만들기 List> graph = new ArrayList(); 예를 들어 문제에서 제시된 vertex ..

📑 1. 문제설명💡 2. 접근방식동적계획법(Dynamic Programming)이란?동적 계획법을 아주 쉽게 설명하자면, '이미 계산한 건 기억해 두었다가, 다시 하지 말자'는 전략이다.동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 동일한 하위 문제를 다시 계산하지 않도록 하는 알고리즘 설계 기법이다. 주로 최적화 문제나 조합 문제를 효율적으로 해결할 때 사용된다. 동적 계획법에는 Top-Down 방식인 메모이제이션과 Bottom-Up 방식인 테이블링이 있다.  Top-Down (메모이제이션)재귀를 사용하여 문제를 해결. 하위 문제의 결과를 저장하여 중복 계산 방지Bottom-Up (테이블링)작은 문제부터 차례대로 해결..