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. CPU 스케줄링1-1. CPU 스케줄러Ready 상태의 프로세스 중에서 CPU에 어떤 프로세스를 할당할 것인지 결정하는 프로그램1-2. 프로세스 스케줄링 💡 프로세스 스케줄링(Process Scheduling) 운영체제(OS)에서 프로세스가 CPU 및 기타 시스템 자원을 효율적으로 사용할 수 있도록 할당하는 작업을 말한다. 다중 프로세스 환경에서 CPU 사용을 최적화하고 시스템 성능을 극대화하는 데 핵심 역할을 한다.1-3. 선점 VS 비선점 스케줄링✅ 선점(Preemptive) 스케줄링▶ 정의: - 현재 실행 중인 프로세스를 스케줄러가 강제로 중단하고, 다른 프로세스에 CPU를 할당하는 방식.▶ 특징: - 우선순위가 높은 프로세스가 도착하면 현재 작업 중인 프로세스를 중단. - 실시간..

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