알고리즘/문제 풀이

문제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..

아무래도 백트래킹 문제가 약한거 같아서 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) 과 자주 함께 소개된다. 말로하면 잘 이해가 안되지만 그림으로 보면 이해가 잘되더라   이 문제에서는 인접 숫..