알고리즘

문제N(1 ≤ N ≤ 100,000) 개의 회의일정 (시작시간, 종료시간) 에 대해서 하나의 회의실에서 가장 많은 회의를 한 개수를 구하려고 한다.시작시간, 종료시간이 겹쳐서는 안되고 종료시간 이후(+1)에 바로 시작시간이 올 수 있다. 접근정렬만 제대로 되어있다면, 종료시간 이후에 시작시간이 올 수 있는 경우를 세면 자연스럽게 하나의 회의실에서 가장 많이 회의를 하는 경우를 구하게 된다. 따라서 핵심 고려사항은 정렬방식이며, 이때 정렬방식은 "종료시간 기준 오름차순" &"종료시간이 동일할 경우 시작시간 기준 오름차순" 이다.  풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import ..

문제동전 N 개가 금액을 기준으로 오름차순으로 주어질때, K 금액을 만들 수 이있는 최소한의 동전 개수를 구한다. 동전은 중복될 수 있다.제약사항: (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000), 동전 금액은 (1 ≤ N_i ≤ 1,000,000)출처: https://www.acmicpc.net/problem/11047접근전형적인 그리디 알고리즘 문제이다. 핵심 아이디어는 동전이 동전의 금액 (N_i) 에 따라 오름차순으로 주어지므로 가장 큰 동전부터 K 에 몇개 들어가지는지 세는 것이다. 두가지 접근 방법이 있을것이다.(1) 덧셈을 이용하여 계산한다.(2) 나눗셈을 이용하여 계산한다. 덧셈을 이용하는 경우 최악의 경우 (N_i = 1, k = 100,000,000) 일때 총 연산횟수 10..

문제9x9 스도쿠 판이 입력으로 주어지면 이 이 스도쿠 판을 다음의 규칙에 따라 완성해서 출력하는 문제이다. *(반드시 완성이 가능한 스도쿠만 입력으로 주어진다.)(1) 각각의 가로줄과 세로줄에 1부터 9까지의 숫자가 한번씩 나타나야한다.(2) 3x3 정사각형 안에도 1부터 9까지의 숫자가 한번씩 나타나야한다.접근이렇게 풀면 되지 않을까?(1) 판을 순회하면서 1 ~ 9 까지의 숫자가 해당 판에 가로조건, 세로조건, 3x3 조건을 충족하면 놓는다.(2) 그 다음으로 이동한다.(3) 만약 모든 숫자에 대해서 가로조건, 세로조건, 3x3 조건을 충족하지 못한다면 가능한 최소한의 경우의 수로 롤백한다. 그리고 이러한 문제 풀이는 백트래킹의 일종인 깊이우선 탐색을 통해 풀 수 있다. 풀이import java.i..

이분탐색은 아이디어는 쉬운데 구현에서 헷갈려서 글을 남겨놓는다.이분탐색 이란 이분 탐색(Binary Search)은 정렬된 배열이나 리스트에서 특정 값을 효율적으로 찾기 위한 알고리즘이다. 탐색 범위를 절반씩 줄여가며 원하는 값을 찾기 때문에, 시간 복잡도가 O(log n)으로 매우 효율적입니다.이분 탐색의 원리이분 탐색은 다음과 같은 절차로 진행된다.탐색 범위 설정: 시작점(left)과 끝점(right)을 지정하여 탐색 범위를 정한다.중간 값 계산: left와 right의 중간 인덱스(mid)를 계산한다.중간 값 비교:중간 값이 찾고자 하는 값(target)과 같으면 탐색을 종료한다.중간 값이 target보다 작으면 left = mid + 1로 탐색 범위를 중간 이후로 좁힌다.중간 값이 target보다..

아무래도 백트래킹 문제가 약한거 같아서 GTP 에게 문제를 좀 내달라고 했다.  쉬운 문제 2개는 부분 수열의합 문제와 모든 순열 출력하기를 내줬고, 이는 백준에서 풀었던 문제와 비슷해서 복습하는 개념으로 풀었다. 그리고 중간 나이도 문제로 N Queen 문제를 내줬다. 문제  해결하기 재귀 호출 설계재귀를 잘못 설계하면 Stackoverflow 에 빠질 수 있다. NQueen 경우의 수를 구하는 문제일 때 재귀 횟수를 줄이려면 다음과 같이 해야한다. (1) 하나의 기준을 정하고 순회한다.'각 퀸이 서로 공격할 수 없다.' 라는 조건에 따라 Row, Col 을 기준으로 하나의 queen 을 넣을 수 있나? 만 고려하면 되고 그렇게 되면 순회 횟수가 N*N 에서 N 으로 줄어든다. (2) 기준 에 따라 놓..

문제문제 링크: https://www.acmicpc.net/problem/15649 백준 알고리즘 단계별로 풀어보기를 하는 중이다.DP 및 백트래킹에서 다소 약한 모습을 보이는 중이므로 이러한 문제들 위주로 풀이를 기록하고자 한다. 접근문제를 다 풀고 다른 사람들의 풀이를 보니 깊이우선탐색을 통해 이 문제를 많이 푸는 것 같다.깊이 우선 탐색 (DFS)(1) 백트래킹의 일종으로(2) '각 node 를 순회할때 하나의 node 에 도달하면 간선을 통해 인접 노드를 계속 파고들고, 끝까지 간 뒤에 다시 첫 노드로 돌아와 같은 레벨의 노드로 옮겨가는 탐색 방법이다.' (3) 넓이 우선 탐색 (BFS) 과 자주 함께 소개된다. 말로하면 잘 이해가 안되지만 그림으로 보면 이해가 잘되더라   이 문제에서는 인접 숫..