한글판 체인 크로니클의 한 페이지를 새로 쓰다

명예의 전당



7월 19일 도전자의 동굴 노힐러 노힐스킬 클리어



7월 20일 강자들의 동굴 노힐러 노힐스킬 클리어

설령 조기 섭종이 되더라도 후회없이 접을 수 있게 되어 뿌듯하다

by 아발컨 | 2015/07/20 17:48 | 그 외 | 트랙백

유전 알고리즘(Genetic Algorithm)

이번 학기에 들었던 과목 중에서 가장 재미있었던 듯 싶다.
대학원 과목이라 처음에는 많이 쫄았는데 생각보다는 많이 털리지는 않고 마쳐서 다행이다.

진화의 원리를 이용해서 시간에 따라 좋은 답을 찾아가는 알고리즘으로,
고전적인 알고리즘으로는 '주어진 시간'(*) 안에 답을 내놓지 못하는 NP-Hard 문제에 대해서
주어진 시간 안에 반드시 최적해는 찾지 못하더라도 그에 준하는 좋은 답을 내놓을 수 있는 방법이다.

이번에 했던 과제의 주제는 max-cut problem으로
그래프를 두개로 나누었을 때 잘라지는 간선(edge)의 weight의 합이 최대인 경우를 찾는 문제이다.

아래는 최종적으로 제출한 소스 코드와 검증에 사용했던 테스트 셋입니다.
혹시 알고리즘 관련으로 관심이 있으신 분들은 도전해보세요.
테스트 셋의 형식은 첫 줄에 vertex의 개수와 edge의 개수가 있고
나머지 줄에는 두 개의 vertex와 edge의 weight가 표시되어있습니다.
(수정)소스 코드의 실행방법은 리눅스 기준으로 (실행파일) (테스트파일) (출력파일)입니다.


(*) : 다항 시간(Polynomial-time), 조금 일상적으로 말하자면 보통 몇 분, 길어야 1~2시간 정도의 느낌.

by 아발컨 | 2013/06/13 23:48 | 잡담-학술 | 트랙백

희망고문


풀콤은 예전에 쳐놓기는 했는데, 판정이 좋을 때는 항상 풀콤과 인연이 없다 ㅠㅠ
이 판정으로 풀콤이 되면 잠깐이겠지만 전일 먹을 수 있었음.

by 아발컨 | 2013/06/13 23:23 | 리듬 게임 | 트랙백

◀ 이전 페이지          다음 페이지 ▶