본문 바로가기

분류 전체보기

 (694)
SCC. [2150] [1. 문제 설명] 방향 그래프가 주어졌을 때, 그래프 내 SCC(=강결합 컴포넌트) 개수와 각 컴포넌트에 속한 정점 번호를 출력한다. [2. 풀이 접근] 강결합 컴포넌트 (이하 SCC) 란 방향 그래프에서 서로 다른 임의의 두 정점 u ~> v 와 v ~> u 로 가는 경로가 존재하는 컴포넌트를 말한다. 위 그림에서 (a, b) (b, e) (e, a) 는 모두 경로가 존재하므로, 같은 SCC 에 속하게 된다. 이러한 SCC 를 구하는 알고리즘 중 타잔 알고리즘을 적용하여 문제를 해결하도록 한다. 타잔 알고리즘 동작 원리는 아래 링크를 참조하도록 한다. [3. 코드]
Java. Arrays [1. 개요] Arrays 클래스를 이용하여 배열을 제어하는 방법을 정리한다. [2. 예제]
Java. ArrayList [1. 개요] List collection 중 ArrayList 사용법을 간단히 정리한다. [2. 예제]
자바 io 성능 [1. 개요] 알고리즘 문제 풀이 시 입출력 성능 차이로 인한 시간 초과 방지를 위한 내용 정리 [2. 기존] [3. 개선] [4. 장단점] 버퍼 방식에서는 한 줄의 문자열을 읽어오기 때문에 항상 문자열을 split 한 후, int, double 등으로 파싱해서 사용해야 한다. 또한, 출력 시에는 버퍼를 반드시 main() 메소드 종료 전 비워줘야 한다. 비워주지 않으면, 출력이 안될 수 있다. 혹은 main() 메소드 종료 전 Reader / Writer 스트림 자체를 소멸해도 된다.
manifest 지정 [1. 개요] maven build 후 jar 파일 실행 시 기본 Manifest 속성이 없는 경우 대처 한다. [2. 방법] pom.xml 내 main class 지정을 한다. 에 수행 할 main 메소드를 갖는 class 를 명시한다. 패키지가 있는 경우 패키지 까지 명시해야 한다.
dfs-위상정렬 - 예제1 [3. 코드]
DP/최단거리 역추적. [13913] [3. 코드]
Union-find - 예제1 [1. 문제 설명] 모순이 없는 경우, 한 파티에 올 수 있는 사람의 최대 수 (vim 파티, emacs 파티 중) [2. 풀이 접근] [3. 코드]
DP/최단거리 역추적. [9252] [1. 문제 설명] 두개의 문자열이 주어졌을 때, 두 문자열에서 공통되는 가장 긴 문자열을 출력한다. [2. 풀이 접근] LCS 의 길이를 찾는 방법은 아래를 참조한다. => 링크 LCS 길이를 찾고 난 다음 cache table 은 아래와 같은 초기화 되어있다. C A P C A K A 4 4 -1 -1 -1 -1 C 3 -1 3 3 -1 -1 A -1 2 2 2 2 -1 Y -1 -1 1 1 1 1 K -1 -1 1 1 1 1 P -1 -1 1 0 0 0 최초 cache[0][0] 이 어떻게 초기화 되었는지 추적해보면 str1[0] != str2[0] 이므로, LCS(1, 0) 과 LCS(0, 1) 중 최대 값에 의해 초기화 되어있음을 알 수 있다. 그래서 cache[0][1] 로 이동해야 한다. 여..
DP/최단거리 역추적. [14003] [1. 문제 설명] 수열의 길이가 최대 1백만이 주어 질 때, 이 수열의 최장 부분 수열의 길이와 최장 부분 수열을 출력한다. 수열의 각 원소는 x 는 아래와 같은 범위를 갖는다. [-10억, 10억] [2. 풀이 접근] 수열의 길이가 최대 1백만 이므로, N2 알고리즘으로는 LIS 의 길이조차 찾을 수 없다. LIS 의 길이는 nlogn 으로 찾을 수 있다. => 다음 풀이를 참조... 문제는 LIS 를 출력하는 것이다. LIS 의 길이를 찾기 위해 사용 한 배열이 항상 LIS 가 됨을 보장하지 않는다. 아래와 같은 입력을 생각하면, A = {1, 10, 100, 9} LIS 는 {1, 10, 100} 인데, 길이를 찾기 위해 사용 한 배열을 그대로 출력하면 {1, 9, 100} 이 출력된다. 정확한 ..

티스토리툴바