https://www.acmicpc.net/problem/2146 [ 나의 문제 풀이 ]1. 각 섬에 번호 부여 : 이중for문으로 map돌면서 섬 만날 때마다 BFS하면, 각 섬에 번호가 부여됨.2. 거리 측정 후보 선택 : BFS돌면서, 바다와 인접해 있는 지역 좌표를 candidate라는 vector에 저장. 3. 거리 측정 : candidate에 있는 좌표들 끼리 거리측정함. 단, 당연히 다른 섬번호끼리만 좌표를 측정. 거리측정은 ABS(y2-y1) + ABS(x2-x1)으로 구하면 됨. 이 때, 거리 측정할 섬들 사이에, 다른 섬이 있을지 모름. 하지만 괜찮음. 생각해보면, 이 경우는 어차피 최단거리가 될리가 없기 때문임. [ 나의 코드 ]1234567891011121314151617181920..
https://www.acmicpc.net/problem/11403 [ 나의 해결법 ]노드 1을 시작점으로 깊이우선탐색을 한다. 이 때 방문한 노드는 노드1에서 갈 수 있는 노드이므로 인접행렬(배열 adj)에 표시해둔다.시작점을 노드1부터 노드 N까지 반복한다. 그럼 모든 정점에 대해서 경로의 존재여부를 구할 수 있다.문제는 깊이우선탐색(DFS)를 이용했다. DFS를 재귀로 많이 구현하는데, 재귀로 구현했다가 시간 초과가 나서 스택(Stack)으로 구현했다. 어차피 재귀도 스택이므로 방법이 크게 다른건 아니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859..
https://www.acmicpc.net/problem/1389 [ 나의 해결법 ]다익스트라 알고리즘을 이용해서 문제를 풀었다. 사람1을 시작해서 다익스트라 알고리즘을 진행하면, 사람1과 다른 사람들과의 최단거리를 배열 dist에 구할 수 있다. 배열 dist의 모든 원소를 더하면 사람1의 케빈 베이컨의 값이 나온다.이런 식으로 사람1부터 N명까지 진행하면서 케빈 베이컨 값이 최소의 유저를 찾으면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include #include #include #..
https://www.acmicpc.net/problem/1707 [ 그림1. 이분 그래프 설명 ][ 나의 해결법 ]그림1처럼 각 집합(파랑색과 빨강색)안에 노드들끼리 간선이 없으면 이분그래프가 된다. 그럼 어떻게 이분그래프인지 알 수 있을까? 주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭짓점 하나를 빨강으로 칠한 후 이웃 꼭짓점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어, 크기가 3인 순환 그래프는 이분 그래프가 아니다. [ 출처 : 위키백과 ] 이 문제에서 주의해야할 점은 다른 노드들과는 아예 분리된 노드가 존재할 수 있다는 것이다. 그림1과 같은 그래프 두 개가..
https://www.acmicpc.net/problem/1238 [ 나의 해결법 ]이 문제는 다익스트라 알고리즘을 이용해서 풀면 된다. 그런데 그냥 다익스트라 알고리즘으로 풀면 시간초과가 난다. 시간복잡도를 계산하면 10억이 훌쩍 넘는다. 3중 for문을 돌기 때문이다.다른 사람들의 질문들을 보니 플로이드 와샬 알고리즘을 이용한 사람도 있다. 그런데 나는 우선순위 큐를 이용한 알고리즘을 사용할 것이다. 코드는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #include #in..
Assembly로 작성된 EntryPoint.s에서 C로 작성된 kernel로 어떻게 넘어갈까? [ 그림1. C로 만들어진 kernel의 배치 ] Enty point의 코드는 0x10200 전까지만 채워져 있다. 그리고 Entry point의 마지막 명령어가 jmp $이기 때문에 무한 루프를 돌고 있다. C로 만들어진 kernel을 주소 0x10200에 올리고 Entry point의 마지막 명령어를 jmp dword 0x08: 0x10200으로 수정하면 kernel이 작동할 수 있을 것이다. 하지만 이러한 계획에는 3가지 제약조건이 있다.1) C라이브러리 호출 불가2) 0x10200 위치에 kernel코드 배치3) kernel 코드는 순수한 바이너리 파일 1)번의 제약조건은 컴파일할 때, gcc에 옵션으..
부트로더가 하는 일은 별거없다. OS 이미지를 1MB이하의 메모리로 복사하기만 하면된다.이러한 코드는 부팅디스크의 첫번째 섹터(512byte)에 기록된다. 이를 MBR(Master Boot Record)라고 부른다. 우선은 최소한의 역할을 하는 부트로더를 만들어보자. 하는 일은 1. BIOS에 의해 부트로더로 인식되서 메모리에 올라가고2. 무한 루프를 돈다.* 아직은 OS이미지 복사 기능이 없다 BIOS에 의해 부트로더로 인식되는 일은 아주 간단하다. 512바이트의 마지막 2바이트에 0x55, 0xAA를 써넣기만 하면된다.코드는 아래와 같다. 코드는 nasm 컴파일러를 사용했다. 1 [ORG 0x00]2 [BITS 16]34 SECTION .text56 jmp $78 ti..
운영체제 만들기를 공부하다보니 배울 것이 참 많았다. 그래서 블로그로 정리해본다.우선 참고한 책은 [ 64비트 멀티코어 OS원리와 구조 ]이다.이 책의 개발환경은 윈도우에서 cygwin을 이용했다. 그리고 64bit환경을 지원하기 위해 x86-64 크로스 컴파일러를 만들어서 쓰고 있다.나도 시도해봤는데, 크로스 컴파일러 만들기에 실패했다. 나중에 알게된 사실인데 이미 gcc가 32, 64bit를 지원한다.굳이 cygwin을 쓸 필요가 없을 것 같아서, 나는 virtual box를 이용해서 개발할 예정이다.ubuntu 16.04 LTS, 64bit 운영체제를 깔아서 썼다. 그리고 nasm과 qemu도 깔아썻다. 설치는 아주 쉽다. 예) sudo apt-get install nasm, sudo apt-get..
다익스트라 알고리즘에 대해 자세히 설명된 곳을 추천한다.http://www.playsw.or.kr/repo/cast/105 우선 위 주소로 가서 다익스트라 알고리즘이 어떻게 동작하는지 한번 살펴보길 추천한다. 단계별로 설명되어 있기 때문이 차근 차근 읽어보면 쉽게 이해할 수 있다. 내가 이해한 다익스트라 알고리즘은 출발지로부터 갈 수 있는 노드의 최단 거리를 모든 노드를 방문할 때까지 계속 갱하는 방법이다. 1. 먼저, 집에서 갈 수 있는 곳을 그림의 표에서 거리 칸에 써 넣는다. 2. 그리고 집에서 갈 수 있는 곳은 미용실, 슈퍼마켓, 영어학원 중에서 최단거리인 미용실로 간다. 3.다시 미용실에서 갈 수 있는 곳은 슈퍼마켓, 은행이다.(집은 이미 방문했으니 패스~)여기서 슈퍼마켓으로 가는 경로는 집에서..
[ Install OpenCV on Raspberry Pi ]OpenCV를 Raspberry pi에 설치하는 것은 많은 시간이 소요된다. 그리고 설치하기 전에 파일 스스템을 확장해 놓아야 한다. OpenCV의 크기가 크기 때문에 파일 시스템을 확장해 두지 않으면 용량 부족으로 아까운 시간을 낭비하게 될 것이다. 설치과정은 단순히 명령어들은 순서대로 나열하겠다. [ sudo apt-get update ] [ sudo apt-get upgrade ] [ sudo apt-get -y install build-essential cmake cmake-curses-gui pkg-config libpng12-0 libpng12-dev libpng++-dev libpng3 libpnglite-dev zlib1g-dbg..