푸으름

✏️ 세그먼트 트리 기본 개념 https://pooreumjung.tistory.com/305 Algorithm 공부 #21 - 세그먼트 트리 Algorithm 공부 #21 - 세그먼트 트리 세그먼트 트리(Segmant Tree) ● 주어진 제이터의 구간 합과 데이트 업데이트를 빠르게 수행하기 위한 알고리즘 ● 트리 초기화 / 질의값 구하기(구간 합 구하기, 최 pooreumjung.tistory.com 문제 풀기 전에 보시면 도움이 됩니다! ✏️ 문제 링크 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 ..

Algorithm 공부 #25 - 기하학 기하학 ● CCW(counter-clockwise) : 코딩 테스트에서 기하 알고리즘을 다룰 때 이용하는 알고리즘 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘 CCW = (x1y2+x2y3+x3y1) - (y1x2+y2x3+y3x1) CCW가 > 0일때 세 점은 반시계 방향, CCW가 < 0일때 세점은 시계 방향, 0이면 일직선 백준 11758번 CCW https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌..

Algorithm 공부 #18 - 그래프(최소 신장 트리) 최소 신장 트리(minimum spanning tree) ● 그래프에서 모든 노드를 연결할 때 사용한 에지들의 가중치의 합을 최소로 하는 트리 ● 사이클이 포함되면 최소 가중치를 계산할 수 없으므로 사이클을 포함시키지 않는다 ● N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 N-1개 ● 최소 신장 트리 구현 방법 1. 에지 중심으로 저장하므로 에지 리스트로 그래프 표현, 사이클 표현을 위해 유니온 파인드도 함께 사용 2. 그래프를 가중치를 기준으로 오름차순 정렬 3. 가중치가 낮은 에지부터 연결하기(이때 바로 연결하지 않고 두 노드의 사이클 여부를 판단해야 함) 4. 사이클이 생성되지 않는다면 두 노드를 연결, 사이클이 생기면 연..

✏️ 문제 링크 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 입력 받은 배열을 정렬한 후 투 포인터로 탐색하는 문제이고 몇 가지 경우의 수로 나눠서 접근해야 합니다. 1. 입력받은 용액값이 모두 음수일 때 => 0에서 가장 가까운 최댓값 2개 출력 2. 입력받은 용액값이 모두 양수일 때 => 0에서 가장 가까운 최솟값 2개 출력 3. 그 이외의 경우 => 투 포인터로 탐색하기..