9 Log

1. 자바 솔루션에서 메모리 초과가 나는 이유 1.1. 메모리 누수? 먼저, 메모리 누수 는 아니다. 메모리 누수는 고려하지 않는다. 알고리즘 문제는 대게 메모리 요구사항이 있고 메모리 요구사항은 GC 가 돌아가는 조건에 한참 못미친다. 애초에 후술하겠지만 GC 가 수행도중에 돌아가서도 안된다. GC 가 돌아가지 않으니 해당 솔루션이 메모리 누수가 나는 설계를 하였다고 하여도 메모리 초과의 직접적인 원인이라 할 수 없다. 그러나 현업에서는 GC 가 비정상적인 상황이 아니며, 따라서 현업 앱 설계에는 메모리 누수에대한 고려가 필요하다. 1.2. 주요 2가지 원인 경험상 크게 2가지 이유가 있다. 문제에서 요구하는 공간 복잡도를 만족시키지 못한 경우. 이런 경우는 오히려 알고리즘의 재설계를 통해 쉽게 해결될 수 있다. 문제 해결이 쉽다. 공간 복잡도는 만족했지만 GC가 제때 되지 않아 메모리 초과가 나는경우 대게 자바는 2번 이유로 메모리 초과가 나는경우가 많다. 알고리즘의 공간 복잡도를 따져보면 조건을 만족하지만, 메모리 초과가 뜨는 경우이다. System.gc() 를 코드 중간에 삽입해서 강제로 gc를 돌려주면 메모리 요구사항을 만족하는 것을 확인할 수 있다. 2. GC 강제로 돌리기 System.gc() 는 강제로 GC 를 수행시켜주는 시스템 메소드이다. 이 메소드를 Unreachable Object 가 생기는 시점마다 강제로 호출시켜주면 C 언어의 malloc() 동적할당 변수에 free() 를 써준 것처럼, 즉시 모든 Unreachable Object 들의 메모리가 해제된다. 이렇게 강제로 GC 를 돌려주면 알고리즘이 자신이 가진 공간복잡도를 온전히 발휘하여 문제의 메모리 요구사항을 만족시킬 순 있다. 하지만, GC 는 기본적으로 시간이 오래 걸리는 연산이다. c 언어의 free() 와는 다르게 GC는 그 대상을 명시해서 사용하지 않는다. GC는 스스로 자신이 해제시켜야할 Unreachable Object 들을 찾아야하며...

1. 시스템 출력 스트림 객체에 직접 접근. 시스템 출력 스트림 객체에 System.out 을 통해 직접 접근해서 사용한다. 내가 필요한 기능만 사용 가능하므로, 다른 데코레이터 클래스를 사용해서 생기는 불필요한 작동으로 인해 소모되는 시간과 메모리를 절약할 수 있다. 2. 출력 버퍼를 쓰기 시스템의 출력 스트림에 데이터를 쓰는 작업은 언제나 시간이 소모되는 작업이다. 따라서 데이터를 하나하나 써가는 것 보다는 버퍼에 한번에 쓰고 출력 스트림에 버퍼를 한번에 쓰게하는 편이 훨신 빠르다. 3. 예제 코드 byte [] outBuf = new byte [ 1024 ]; //1024바이트의 버퍼 //outBuf에 직접 값을 입력 예제. for ( int i= 0 ;i< 1024 ; i++){ outBuf[i] = 'a' ; //전부 a로 채워 넣기 } System.out.write(outBuf);

이 포스팅은 가장 빠른 정수 입력 받기 포스팅의 연장이다. 1. 정수와 문자열 입력이 모두 존재할때 빠르게 입력받는 법 정수와 문자열이 입력으로 함께 존재하는 문제에서는 정수 입력용 커스텀 메소드를 쓰기가 까다롭다. 문자열 처리용으로 자바 입력 라이브러리를 함께 쓴다면 라이브러리와의 미묘한 처리방식 차이로 스트림에 특수문자(특히 \n나 \r)가 남아 원하지 않는 결과를 만들게 된다. 기왕 이렇게된거 문자열까지 커스텀 메소드로 작성하여 더욱 빠르게 처리하는게 좋다. 정수 입력 커스텀 메소드도 문자열 입력 커스텀 메소드가 혹시라도 남길 공백 및 개행문자를 처리하기위해 특별한 로직 필요하다. 2. 문자열 입력 커스텀 메소드 private static String readStr ( int bufSize) throws IOException{ byte [] bytes = new byte [bufSize]; int i= 0 ; while ( true ) { int input = System.in.read(); if (input != '\n' && input != '\r' && input != ' ' ) { bytes[i++] = ( byte )input; break ; //앞 공백 제거 후 시작. } } while ( true ) { int input = System.in.read(); if (input == '\n' || input == '\r' ) { return new String (bytes, 0 , i); } else bytes[i++] = ( byte )input; } } 문자열앞에 개행(운영체제별 개행방법 모두 고려)과 공백이 연속해서 존재할 경우도 고려. 운영체제 또는 입력 인코딩에 따라 메소드 종료 후에 I...

1. 빠른 정수 입력 스트림 읽기의 필요성 백준 알고리즘 문제를 풀다보면 정수로 구성된 일련의 데이터 를 받아서 처리해야할 때가 있다. 백준은 입력과 출력 시간도 알고리즘 수행시간에 포함되다 보니 입, 출력 시간 절약이 아주 중요하다. 사람들이 입력 스트림을 읽는 방법은 크게 4 가지 이다. Scanner 사용 BufferedReader 사용 사칙연산 을 사용하는 커스텀 메소드 사용 비트연산 을 사용하는 커스텀 메소드 사용 이중 가장 빠른 것은 사칙 연산 을 사용하는 커스텀 메소드 이다. 각 방법을 빠른 순으로 나열하면 사칙연산 사용 커스텀 메소드 비트연산 사용 커스텀 메소드 BufferedReader Scanner 커스텀 메소드 들의 성능은 거의 같다. BufferedReader 는 커스텀 메소드 의 두배정도 걸린다. Scanner 는 BufferedReader 의 두 배이상 걸린다. 테스트 수행 결과 2. 각 방법의 코드 및 사용법 2.1. Scanner 클래스 임포트 import java.util.Scanner; 객체 생성 및 정수 입력 스트림 읽기 Scanner sc = new Scanner (System.in); //생략 sc.nextInt() //생략 sc.close(); 2.2. BufferedReader 클래스 임포트 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; 객체 생성 및 정수 입력 스트림 읽기 BufferedReader br = new BufferedReader ( new InputStreamReader (System.in)); //생략 //한줄에 여러개의 입력 정수가 공백 하나를 기준으로 나뉘어서 들어올때 StringTokenizer st = new ...

헤밀턴 회로는 모든 정점을 꼭 한번씩 거쳐서 출발점으로 다시 돌아오는 경로이다. 책에서 헤밀턴 회로를 구하는 문제를 보았다. 이분은 헤밀턴회로를 DFS로 구현하였는데 각각의 노드에 도달할 때마다 이전에 방문한 정점을 방문하지 않으려고 방문한 정점과 방금 지나온 간선을 검색대상에서 제외하였다. for( i =0;i<n;i++){ if(a[vertex][i]&&!check[i]){ a[vertex][i]=a[i][vertex]=0; check[i]=true; hamiltonCircuit(i); a[vertex][i]=a[i][vertex]=0; check[i]=false; } } 이런 식이다. 그러나. 헤밀턴 회로의 정의를 보면 지나간 간선을 다시 사용할 수 없다는 말은 없다. 다만 사용할수 없는 건 이러한 관계가 성립하기 때문이다. 각각의 정점을 꼭 한번씩 지난다->각각의 간선을 한번씩만 지난다.(물론 오일러의 경우처럼 모든 간선을 꼭 사용한다는 뜻은 아니다. 간선이 남을 수도 있다) 각각의 정점을 한번씩만 지나는 경우를 생각해 보자, 정점C에서 3번간선을 지나 정점 A에 도달 했다고 하자, 그렇다면 다신 3번 간선을 사용할 수 가 없다. 왜냐하면 이미 정점 C를 거쳐왔기 때문이다. 반대로 각각의 간선을 한번씩만 지나는 경우를 생각해보자. 정점 B에서 5번간선를 지나 정점 G에 도달한 상황에서 G에서 또다른 간선들을 이용하여 충분히B에 도달할 수 있다. 이러한 논리를 일반화 시키면 위의 관계가 성립함을 알 수 있다. 그리고 이러한 이유로 굳이 지나간 간선을 검색에서 제외할 이유가 없다. 어짜피 지나온 정점들을 방문하지 않는다는 조건은 지나온 간선들을 다시 방문하지 않는다는 조건을 포함하고 있다. 따라서 나는 다음과 같이 사용하는게 더 합리적이라고 본다. for( i =0;i<n;i++){ if(a[vertex][i]&...

/* UVA302 존의 드라이빙 존은 친구들을 만나러 드라이빙을 계획중이다. 친구들은 마을에 있는 도로마다 한명씩 산다. 존은 드라이빙을 마친후 집으로 가장 최단 시간안에 돌아와야 한다. 가장 최단시간에 드라이빙을 마치려면 각각의 도로를 한번씩만 거쳐서 집으로 돌아와야한다. 마을에는 1<=n<1995 범위의 정수이름을 가지는 도로가 존재하며 각각의 도로의 이름은 겹치지 않는다. 도로는 딱 2개의 교차점과만 양끝으로 연결되어 있으며 교차점은 1<=m<44의 정수이름을 가진다. 만약 최적의 드라이브 코스가 여러개면 가장 번호가 낮은 도로를 출력한다. 존은 첫번째 도로에서 더 작은 숫자의 교차점에 산다. 이때 존의 드라이빙을 계획해보자. Input x y z// x: 도로 z의 한쪽 끝에 연결된 교차점의 이름, y: 도로 z의 반대쪽에 연결된 교차점 . . . 0 0//테스트 데이터의 끝. 또 다른 테스트 데이터 입력 가능 0 0 0 0//빈테스트 데이터로 입력 데이터의 끝  Output 1 2 4 5 3//방문하는 도로를 순서대로 출력. 테스트 데이터 1 결과 Round trip does not exist//테스트 데이터 2 결과. 적합한 코스 없음. <알고리즘 요약> 교차점을 정점으로 도로를 간선으로 하는 오일러 회로를 그리디 알고리즘을 통해 구한다. Greedy Euler Path 에서 했던것처럼 일단 어떤 경로로든 더이상 진행할 수 없는 끝점에 도달하고도 간선이 남아 있다면 중간에 지나지 않은 회로들이 존재하는 것이므로(남은 간선들이 모두 정점에 짝수개씩 연결되어 있으므로) 중간에 또다른 회로가 존재하는 정점으로 돌아가서 회로를 검색하고 그 회로를 경로에 중간에 추가해준다. 그러고도 남은 간선이 존재한다면 회로가 존재했던 정점을 다시 검색하고 계속 이전 정점으로 검색하면서 또다른 회로가 존재하면 또 추가해주고 검색하고를 반복하여 모든 간선을 소비할 때 까지 반복한다. 그러나 Greedy Euler Path...

/*finding an Euler path using Greedy Algorithm 그리디 알고리즘을 이용해 오일러 경로를 찾는 알고리즘   DFS와는 다르게 각각의 정점에서 아무 간선으로나 진행 *하여 최대한 빠르게 끝 정점 *에  도달하고 경로를 저장한다음 중간에 무시하고 지나간  회로* 들을 다시 탐색하여 경로 중간에  추가시켜주는 방법을 사용하여 훨신 빠르다.   * 어느 간선을 이용하던 끝정점에 도달하게끔 되어있다.  * 여기서 말하는   끝정점은 더이상 진행할 간선이 존재하지 않아 고립되게 되는 점이다. *지금 까지 남아있는 간선들만 보았을때 그 그래프는 차수가 짝수인 점들로 이루어진 그래프와 같아서 오일러 회로가 반드시 존재한다. 중간에 지나친 회로들을 찾는 방법 :  현재 저장된경로의 끝 정점부터 처음 정점까지* 하나하나 사용하지 않은 간선과 연결되있나 검사하면 된다. 그리고 중간에 회로가 추가되었을때 추가된 회로까지 포함하여 검사가 완료되지 않은 점들을 또 검사한다. *반대방향도 상관 없다. 그냥 경로내의 모든 정점에 사용하지 않는 간선이 존재하는지 여부만 확실히 하면 된다  이러한 과정을 통해 오일러 경로를 구할 수 있다. 여기서는 경로를 두개의 스택을 이용하여 추가를 하지만, 연결 리스트를 사용하건 뭘 사용하건 만든사람 마음이다. input: n m / n<=100: the number of vertex m<=1000: the number of line a b / a: one side of a line ,b: the other side of a line. repeat m-1 time. */ #include <iostream> #include <windows.h> #include <vector> usin...

그리디 알고리즘은 가장 트리에서 윗 레벨에서 아랫 레벨로 검색해갈때 각각의 레벨에서 모든 경우중 가장 최적이라고 생각되는 경우만 검색 하는 것이다. 따라서  결과적으로 구한 해가 최적의 해가 아닐 가능성이 존재 한다. 그리디 알고리즘으로 구한 해가 최적임을 보장하려면 각각의 레벨에서 최적의 경우를 구한것이 결과적으로도 최적의 해가 될수 있음을 수학적으로 증명하여야 한다. 예를 들어 보자 Greedy Euler Path 이란 예제가 있다. 그리디 알고리즘은 차수가 짝수인 정점들과 2개의 차수가 홀수인 정점들로 이루어진 그래프에서 오일러 경로를 다음과 같은 방식으로 찾는다. (모든 차수가 짝수여도 된다) 시작점은 가장 낮은 수를 가진 홀수 차수의 점이다. 0.현재 정점을 스택 1에 저장한다. 만약, (1).현재 정점과 연결된 정점중 가장 낮은 수를 가진 정점을 찾아간다.. (2).만약 도중에 간선을 다 소모하지 않고도 현재 정점과 연결된 정점이 없어서 진행하지 못하면 그점을 스택 1에서 제거하고 스택 2에 저장하고 전 정점으로 건너 뛴다. (3).모든 간선을 소모하여 더이상 진행할 수 없을때 종료된다. 종료한뒤 스택 2의 원소들을 나중에 들어온것 부터 스택1로 옮긴다. 각각의 레벨(현재 정점)에서 이러한 조건을 통해 특정 경우로 나아가는 것을 논리적으로 최적의 해를 보장하게 된다. 사실, 각각의 정점에서 가장 낮은 수를 찾아 가는 경우를 포함해서 사실 그냥 연결되있는 아무 정점을 찾아가도 보장이된다. 1번 규칙에 따라 꾸준히 축적되가던 경로가 어떤 특정한 점에서 간선을 전부 소모하지 않았음에도 더이상 진행할 수가 없다면, 모든 간선을 소모하기 전에 도착정점의 마지막 간선을 소모했다는 뜻이다. 따라서 이러한 정점들을 스택 2에다가 순서대로 저장해주면 도착정점에 도달할 최후의 정점이 채워지게 되는것이...