BOJ

https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 1. Logic CCW알고리즘을 활용하여 풀이 가능하다. CCW 알고리즘이란 임의의 선분을 기준으로 다른 한 점이 시계방향으로 위치하는지 반시계방향에 위치하는지 판별할 수 있는 알고리즘이다. 이 알고리즘은 수학시간에 했던 신발끈 공식, 외적을 생각하면 쉽게 이해할 수 있다. 한 선분(선분을 이루는 두 점 A, B)과 다른 한 점(C)을 외적한 값을 CCW(A, B, C)=outer라고 했을 때 outer > 0 : ..

https://www.acmicpc.net/problem/17503 17503번: 맥주 축제 첫 번째 줄에 축제가 열리는 기간 N (1 ≤ N ≤ 200,000) 과, 채워야 하는 선호도의 합 M (1 ≤ M 도수기준 오름차순 정렬 2. 선호도를 sum에다 누적해주고 우선순위 큐에 도수가 낮은거부터 순서대로 선호도에 -를 붙혀서 오름차순으로 정렬해준다. 3. 우선순위 큐pq의 사이즈 pq.size()값이 n이랑 같아지면 sum이 m 이상인지 확인 후 이상이면 현재 beer의 도수를 출력한다. 이유는 beer 벡터를 알콜 도수가 높은 순서대로 알콜도수 기준 오름차순 정리를 했기 때문에 지금 조건의 알콜 도수가 최소 도수이다. 4. 만약 3번에서 안걸러지고 우선순위 큐의 갯수가 n을 넘었다면 pq.top()..

https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 1. Logic for문을 0부터 돌기때문에 내 앞에 나오는 애들은 전부 나보다 키가 작다. 그래서 내 앞에 키 큰 사람이 몇명올지 그 사람들의 자리를 남겨 놓는게 목적이다. 2. Code #include using namespace std; int seat[10]; int main() { int n; cin >> n; for(int i = 0; i < n; i++) { //입력 받는 횟수..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. Logic 외판원 순회란 도시들(노드)이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌도 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제이다. 아래 그래프를 보자. 이 5개의 노드가 있을 때 순회를 할 수 있는 방법은 총 5가지이다. 1 > 2 > 3 > 4 > 5 2 > 3 > 4 ..

https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 1. Logic 일단 문제를 이해하는데 너무 시간이 오래걸렸다.. ㅋㅋㅋㅋ 이해가 안가서 알고리즘 분류를 봤는데 유니온파인드여서 대충 풀이는 어떻게 할지 떠올랐지만 확실히 이해가 안가서 다른 블로그들을 참고했다. 일단 우리는 1번부터 g번까지 게이트가 있고 여기에 도킹을 시켜야한다. 배열은 0부터 시작하기 때문에 만약 1번 게이트에 도킹을 하면 0번 배열에 비행기..