알고리즘::동빈나책

<모든 문제는 C++를 기반으로 풀이한다.>주어진 조건에서 가장 큰 수를 만드는 방법은 수열을 정렬하고, 가장 큰 수를 K번 더한 뒤 두번째로 큰 수를 한 번 더하는 과정을 반복하는 것이다.2 4 5 4 6을 예로들어보자. 정렬하면, 2 4 4 5 6이 되고, M

<모든 문제는 C++를 기반으로 풀이한다.>푸는 방법은 여러가지겠지만 여기서는 switch-case문을 사용한 직관적인 방법을 사용했다.맵을 구현할 필요가 전혀 없다. 출발지 좌표 (1, 1)을 기준으로 좌표값만 조작해주면 된다.이 문제에서 가장 까다로운건 입력받

<모든 코드는 C++를 기반으로 작성되었습니다.>DFS의 단골문제중 하나인 부분 그래프 개수 찾기 문제다.임의의 좌표에서부터 시작해서 인접한 칸의 값이 0일 때 진행한다. DFS가 1회 종료되서 나올 때마다 카운트 해준다. 왜냐하면 DFS가 한 번 종료됐다는 것은

<모든 코드는 C++를 기반으로 작성되었습니다.>매장에 부품은 최대 백만개 있을 수 있고 찾을 부품도 최대 백만개 있을 수 있기 때문에 생각없이 찾으려하면 100만 X 100만번 연산해야한다.당연히 그렇게 푸는게 아니고 $O(log(n))$ 시간복잡도를 가지는 이

<모든 코드는 C++를 기반으로 작성되었습니다.>반드시 a 연산을 수행하는 것이 최선은 아니라는 것을 깨닫는게 핵심이다.결국 4가지 연산을 모두 수행해봐야하는데, bruteforce로는 너무 오래걸리므로 dp를 사용하는 것이 유효하다.더 이상 분할할 수 없는 아주

<모든 코드는 C++를 기반으로 작성되었습니다.>다익스트라 알고리즘은 임의의 기준 정점으로부터 모든 정점까지의 최단 경로를 빠르게 찾는 방법이다.다익스트라 알고리즘의 시간 복잡도는 간선 개수 E, 정점 개수 V일 때, $O(E \\times log(V))$이다.

저자 자체 제작 문제는 저작권을 위해 문제를 작성하지 않았음을 알립니다. Q.01 모험가 길드 문제 문제접근 최대한 많은 그룹을 만들기 위해서는 어떻게 해야하는지 생각해야 한다. 모험가들의 공포도를 오름차순으로 정렬한 뒤 적은 공포도를 가지고 있는 사람부터 그룹을 만

저자 자체 제작 문제는 저작권을 위해 문제를 작성하지 않았음을 알립니다.와 진짜 어렵다...카카오 4문제는 어떻게든 풀었지만 30~50분은 커녕 몇 시간씩 걸렸다. 이걸 현장에서 어떻게 풀어...참 갈 길이 너무 멀다.https://www.acmicpc.net

저자 자체 제작 문제는 저작권을 위해 문제를 작성하지 않았음을 알립니다.https://www.acmicpc.net/problem/10825도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있을 때 수열에서 x가 등장하는 횟수를 계산하시오. 단, O(logN) 알고리즘으로 풀어야 한다.이번 챕터에서는 이진 탐색의 새로운 기능을 배우게 된다.이 문제의 제목이기도 한데, 이진 탐색을 이용하면 정렬된 배

고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미한다. 모든 원소가 오름차순으로 정렬된 수열에 고정점이 있다면 고정점을 출력하는 프로그램을 작성하시오. 단, O(logN)에 해결하시오.정렬된 수열과 O(logN)이라는 힌트를 기반으로 이진 탐색으로

n X m 크기의 금광에서 채굴자는 첫 번쨰 열부터 출발해서 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하시오.3가지 이동방법을 각각 수행한 뒤 그 결과를 메모이제이션

못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미한다. 1은 못생긴 수라고 가정한다. 이때 n번째 못생긴 수를 찾는 프로그램을 작성하시오.핵심은 못생긴 수에 어떤 수를 곱한 수는 못생긴 수라는 것이다.1부터 시작해서 2, 3, 5를 곱한 수를 못생긴 수 배

두 개의 문자열 A, B가 주어졌을 때, A를 편집하여 B로 만들려고 한다. 수행할 수 있는 연산은 다음 3가지다. 이때 최소 편집 횟수를 구하시오. 삽입(Insert): 특정한 위치에 문자 하나를 삽입합니다.삭제(Remove): 특정한 위치에 문자 하나를 삭제합니다.

학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇 명인지 계산하는 프로그램을 작성하세요.4번 학생은 1, 3, 5번 학생이 자신보다 순위가 낮고, 2, 6번 학생이 자신보다 순위가 높기 때문에 전체 3등이라는 것을 확실하게 알

화성 탐사 기계가 존재하는 공간은 N x N 2차원 공간이며 각각의 칸을 지나기 위한 비용이 존재한다. 가장 왼쪽 칸에서 가장 오른쪽 아래 칸인 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요.임의의 시작점이 주어지고 임의의 도착점까지의 최단 경로(최소 비용

동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간에 숨는다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 잣성하세요.동빈이는 항상 1번 헛간으로부터 시작하므로 시작점이 정해져있고 다른 모든 정점까지의 거리를 구한 뒤 문제 조건에 맞는 정답을 구하는 전형적인 다익

Chapter 10 Section1:: 서로소 집합(disjoint sets) 개념 서로소 집합은 중복되는 원소나 교집합이 없게끔 자료를 저장하는 자료구조를 의미한다. 그래프와 연관되는 개념이지만 서로소 집합은 트리 개념(Root-Parent-Child)을 따르는 것이

G개의 탑승구와 P개의 비행기가 차례대로 도착하는 공항이 있다. P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나온다면 공항의 운행을 중지한다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력하시오.까다로운 문제다. 서로소 집합 유

임의의 두 여행지 사이에는 양방향 도로가 있다. 여행계획은 여행지의 수 N과 여행 계획에 속한 도시의 수 M으로 이뤄진다. 한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판별하는 프로그램을 작성하시오. (1 ≤ N, M ≤ 500)최소 거리를

특정한 도로의 가로등을 하루동안 켜기 위한 비용은 해당 도로의 길이와 동일하다. 정부에서는 일부 가로등을 비활성화해서 절약할 수 있는 최대 금액을 구하고자 한다.전형적인 MST (최소 신장 트리) 문제다. 입력받은 간선을 cost에 대해 오름차순으로 정렬한 뒤 가장 적

문제링크기본적인 시뮬레이션 문제로 어렵지 않게 풀 수 있는 문제였습니다.문제에서 주어진 조건을 차근차근 살펴봅시다.1\. 아기 상어는 상, 하, 좌, 우 인접한 칸으로 이동합니다.2\. 아기 상어는 자신보다 작은 물고기만 먹습니다.아기 상어는 자신보다 큰 물고기가 있는

문제 링크조건이 복잡해서 꽤 까다로운 문제였습니다.푸는데 2시간 정도 소요됐습니다.문제에 주어진 조건이 복잡합니다. 차근차근 문제를 분해해봅시다.상어는 항상 (0, 0)에서 시작합니다.물고기는 작은 번호부터 움직입니다.이동할 수 없는 경우 반시계방향으로 45도 방향을