어흥

문제 링크: www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1≤N≤1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점이 주어진다. 선택한 지점은 -1,000,000,000 이상 1,000,000,000 이하의 정수이다. www.acmicpc.net 1. 주의할 점 - 왼쪽에 대한 오름차순으로 정렬 이후, 오른쪽에 대한 오름차순 정렬을 진행한다 - 입력 받을때, 처음 받는 수가 항상 왼쪽에 위치한다고 보장할 수 없다 2. 구현 - S(Start)에 대해서 오름차순으로 정렬 -> E(End)에 대해서 오름차순 정렬을 진행하는 우선순위큐를 생성한다 - 각 점에 대해서 입력받을 때, 작은 값을 S, 큰 값을 E에 할당한 이후 ..

문제 링크: www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 1. 주의할 점 - 정렬을 한다 - 해당 크레인이 자신이 들 수 있는 무게보다 적고, 해당 크레인만 들 수 있는 박스 수를 통해 해결한다 - 가장 무거운 박스의 무게가 크레인이 들 수 있는 가장 무거운 무게를 넘어서면 -1을 출력한다 2. 구현 - 입력받은 크레인이 들 수 있는 무게(Crane), 박스의 무게(Box)를 오름차순으로 정렬한다 - Avail[i] 배열에는 i-1번 크레..

문제 링크: www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 1. 주의할 점 - 딱히 없다... 배열을 이용하여 A + B = X를 만족하는 B(=X-A)를 찾아도 된다 2. 구현 - 정렬을 통해 수를 오름차순 정렬시킨다 - 양끝에서 시작하는 투포인터로 접근한다 - While문이 끝나는 경우로는 l이 r과 같거나 크면! (같다고만 하면 런타임 에러 발생할 수도 있다. 아래에 예시가 존재!) 더보기 2 1..

문제 링크: www.acmicpc.net/problem/2886 2886번: 자리 전쟁 R x C의 형태를 지닌 전차 안에는 의자와 사람들의 정보들이 주어진다. 사람들은 다리가 아픈 것을 매우 싫어하기 때문에 빈 의자가 보이면 무조건 앉으려고 한다. 하지만 나보다 의자에 가까이 www.acmicpc.net 1. 주의할 점 - 우선순위큐를 사용하여 정렬을 한다(거리의 오름차순으로) 2. 구현 - 입력받을 때, 사람과 의자의 정보를 기억해놓는다 - 사람들과 의자사이의 거리를 구하여 구조체 형식(사람 번호, 의자 번호, 거리)으로 저장한 값을 우선순위큐에 담는다 - 우선순위큐에서 거리가 같으며, 아직 해당 사람이 의자에 앉지 않았고, 의자 또한 비어있다면 V 벡터에 의자 번호를 담는다. 동시에 사람이 의자를 ..

문제 링크: programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 [23:59,23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59] 18:00 programmers.co.kr 1. 주의할 점 - 문자열 처리를 통해 각 시간을 어떻게 저장할 것인지 정한다 2. 구현 - Arr[10] 벡터를 생성하여 셔틀의 수용인원만큼 수를 각 셔틀에 저장한다(최대 셔틀이 10개라고 적혀있다) - 각 시간을 분으로 환산하여 V 벡터에 저장한 이후, 오름차순으로 정렬한 이후, Queue에 수를 순차적으로 넣..

문제 링크: https://www.acmicpc.net/problem/14588 14588번: Line Friends (Small) Q개의 줄에 걸쳐 두 선분이 가까운 정도를 출력한다. 만약, 두 선분 사이의 친구 관계가 단절되었다면 -1을 출력한다. www.acmicpc.net 1. 주의할 점 - 2개의 선분이 겹치는 조건을 잘 생각한다 - 플로이드 와샬 알고리즘에 대하여 알고 있어야한다 - 양방향 그래프이므로 플로이드 와샬을 사용할 경우, 배열의 원소를 잘 초기화 해야한다(내 코드의 경우 한번에 2개의 원소를 초기화 해야 한다) 2. 구현 - Arr[][]배열을 전부 987654321로 초기화하며, i==j인 경우에만 0으로 초기화한다 - 각 선분에 대한 정보를 입력받은 후, 2개의 선분(I,J)을 ..

문제 링크: https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작� www.acmicpc.net 1. 주의할 점 - 문자열을 V벡터에 입력받고, Next_Permutation을 하기 전에 Sort를 수행한다 2. 구현 - Next_Permutation을 수행하기 전에 반드시 Sort를 수행한다. 입력받는 문자열이 순서대로 들어오지 않기 때문이다(이해가 되지 않는다면 1234와 4321을 출력해보면 안다. 이때의 정답은 24가 올바르다) - Next_Permutation을 수행하면서 ..

문제 링크: https://www.acmicpc.net/problem/11085 11085번: 군사 이동 문제 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재�� www.acmicpc.net 1. 주의할 점 - 가중치가 큰 간선들부터 연결을 한다 - 크루스칼 알고리즘을 사용한다. 단, 종료조건이 다르다 2. 구현 - 입력 받는 간선에 대한 정보를 우선순위큐에 저장하며, 가중치의 내림차순으로 정렬한다 - 우선순위큐에서 간선에 대한 정보를 1개씩 빼면서 만약 2개의 도시가 이어져 있지 않다면 연결하고, Result에 해..