PS (81) 썸네일형 리스트형 [Java] CCW (Counter Clock Wise) - 세 점의 방향성 파악 https://travelbeeee.tistory.com/45 [알고리즘] 세 점의 방향성 파악하기 'CCW 알고리즘' 안녕하세요. 여행벌입니다. 오늘은 세 점이 주어졌을 때, 방향성을 파악할 수 있는 CCW 알고리즘에 대해 다뤄보겠습니다. 다음과 같이 세 점 A, B, C 가 있을 때, 세 점의 방향성을 시계방향 / 반시 travelbeeee.tistory.com 반시계 방향 : 1 시계 방향 : -1 일직선 : 0 static int ccw(Node n1, Node n2, Node n3){ long s = (n1.x * n2.y + n2.x * n3.y + n3.x * n1.y) - (n1.y * n2.x + n2.y * n3.x + n3.y * n1.x); if (s > 0) return 1; el.. [Java] 백준 17387번 선분 교차 2 - CCW https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 한 문제 푸느라 반나절이 날아갔다... 처음에는 수학적으로 접근하려 했는데 double을 쓰다보니 범위를 감당할 수 없어져서 CCW 알고리즘임을 알았다. case work에 실수가 많아서 시간이 많이 들었다. import java.util.*; import java.io.*; public class g2_17387 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWr.. [Java] 백준 12094번 2048 (Hard) - 빡구현 https://www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 12100번 2048(Easy)와 유사하지만 수행이 5번인 easy와 다르게 10번이나 되어서 빡센 가지치기가 필요했다. 3시간 걸림; import java.util.*; import java.io.*; public class p4_12094 { static FastScanner fs = new FastScanner(); static PrintWriter pw = ne.. [Java] Topological Sort(위상 정렬) - 방향성 있으며 사이클 없는 그래프 https://bcp0109.tistory.com/21 위상정렬 Topological Sort (Java) 위상정렬 연습 문제 1 연습 문제 2 위상 정렬은 그래프 정렬을 말합니다. 그래프의 순서를 정렬하기 때문에 조건이 있습니다. 위상 정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사 bcp0109.tistory.com 필요한 정보 1) 각 노드가 가리키는 노드 번호에 대한 정보 2) 각 노드를 수행하기 전에 탐색되어야 하는 노드의 개수 (inDegree) 3) 탐색 시작 시점에 inDegree == 0인 노드 (출발 노드의 위치, 개수) 사이클 유무 확인 방법 탐색한 노드들을 Answer Queue에 넣어놓았을 때 크기가 n보다 작다면 => 사이클이 존재! [Java] 백준 2623번 음악프로그램 - 위상 정렬 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net import java.util.*; import java.io.*; public class g2_2623 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(System.out); static int n, m; static List list = new ArrayList(); st.. [Java] BitMask https://loosie.tistory.com/238 [알고리즘] 비트(Bit)와 비트마스크(BitMask) 정리 (Java) 비트(bit) 비트(binary digit)는 데이터를 나타내는 최소 단위로 이진수의 한자라인 0 또는 1의 값을 가진다. 부호 없는 N비트 정수형 변수는 N자리의 이진수로 나타낼 수 있다. 이때 비트가 표현하는 loosie.tistory.com 삽입 str |= (1 [Java] 백준 1062번 가르침 - 비트마스킹 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net a~z의 26개 문자의 포함 여부를 32비트뿐인 int에 비트마스크로 저장가능하다. 가르쳤는지 여부도 check에 비트마스킹 때렸다 import java.util.*; import java.io.*; public class g4_1062 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(S.. [Java] 백준 9466번 텀 프로젝트 - DP, case work https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 처음에는 사이클에 구성되지 않는 노드의 개수를 찾는 문제라고 생각했으나 시간복잡도가 n^2가 되어 불가능했기에, 어느 노드에서 출발하더라도 마지막에는 항상 사이클로 연결된다는 점을 이용했다. import java.util.*; import java.io.*; public class g3_9466 { static FastScanner fs = new FastScanner(); static PrintWri.. 이전 1 2 3 4 5 6 7 ··· 11 다음