전체 글
-
너비 우선 탐색을 통한 최단거리 구해보기알고리즘 이론/알고리즘 구현 2019. 9. 3. 02:47
너비 우선 탐색(BFS) 은 그래프에서의 최단 경로 문제를 푸는 용도로 사용 된다. 최단 경로 문제는 두 정점을 연결하는 경로 중 가장 길이가 짧은 경로를 찾 는문제 이다. 코드 ( C ++ ) #include #include #include #include using namespace std;vector adj; // start에서 시작해 그래프를 너비 우선 탐색하고 시작점부터 각 정점까지// 최단 거리와 너비 우선 탐색 스패닝 트리 계산// distance[i] = start부터 i까지의 최단 거리// parnet[i] = 너비 우선 탐색 스패닝 트리에서 i 의 부모의 번호, 루트일 경우 자신의 번호void bfs2(int start, vector& distance, vector& parent){di..
-
그래프의 너비 우선 탐색알고리즘 이론/알고리즘 구현 2019. 9. 3. 02:31
너비 우선 탐색(BFS)는 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이다. 너비 우선 탐색은 깊이 우선 탐색과는 달리 발견과 방문이 같지 않다. 1. 아직 발견되지 않은 상태 ( 큐에 넣기 전) 2. 발견되었지만 아직 방문되지 않은 상태 ( 큐에서 대기 중) 3. 방문된 상태 ( 큐에서 꺼낸다 ) 너비 우선 탐색이 시작점인 0 을 방문하면 정점 1 3 4 8이 목록에 추가 된다. 이들은 모두 0에서 간선 하나로 연결되기에 어느 정점을 먼저 꺼내도 상관 없다. 이 중 1을 꺼내 방문했다고 하면 2가 목록에 추가 된다. 이때 2는 자신보다 먼저 목록에 추가된 남은 정점 3 4 8이 방문되기 전까지는 결코 방문되어서는 안된다. 이를 구현하는 방법은 목록에 먼저 넣은 정점을 항상 먼저 꺼내야 하..
-
2. 운영체제 커널(kernel)과 shell(쉘)이란?운영체제/운영체제 정리 2019. 9. 3. 00:33
OS는 크게 2가지로 나눌 수가 있는데 컴퓨터에 제일 내부에는 하드웨어가 있다고 했고 그 하드웨어를 관리 해주는 것이 OS ( 운영체제 ) 라고 하였다. 실제로 하드웨어를 관리하는 OS부분을 kernel 커널이라고 부른다. Os에서 제일 중요한 부분은 이 관리 해주는 커널 부분이다. OS에 다른 한가지는 쉘 ( 명령어 해석기 )이다. 즉 shell 껍질인데 os에 바깥부분에 위치하여 사용자로부터 명령을 받아들이고 그 명령을 해석하고 해당되 는 명령을 실행해 주는 것을 쉘이라고 한다. ex ) 바탕화면에 여러개의 아이콘이 모여져 있고 더블클릭하면 실행되는 방식인데 이 프로그램을 실행하라는 명령을 내린다. or 리눅스 명령어 등 커널 : 실제 cpu와 메모리와 디스크 등을 관리한다 쉘 : 사용자가 명령을 내..
-
백준(BOJ) 4307번 개미알고리즘 풀이/백준(Boj) 2019. 9. 2. 15:43
문제 : https://www.acmicpc.net/problem/4307 문제개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는 지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오. 풀이 : 개미가 만나게 되면 방향을 반대로 바꾸는 것과는 상관없이 모든 개미가 떨어질때 가장 빠른 시간은 출발선 or 도착선으로 가장 빠르게 떨어지는 개미 중..
-
백준(BOJ) 1904 01타일알고리즘 풀이/백준(Boj) 2019. 9. 2. 00:40
문제 : https://www.acmicpc.net/problem/1904 문제지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는..
-
백준(BOJ) 14891번 톱니바퀴알고리즘 풀이/백준(Boj) 2019. 9. 1. 23:52
문제 : https://www.acmicpc.net/problem/14891 문제총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. ..
-
1. 운영체제란?운영체제/운영체제 정리 2019. 9. 1. 20:10
PC를 구입하면 그 안에 운영체제가 설치되있다. 예를들면 리눅스 , Windos XP, Windos 7, 10 MS- DOS 등이 있겠다. OS가 없다면? 컴퓨터 구조를 보자. ( introduction - 명령어, introduction의 집합 - Program ) 컴퓨터는 전원을 키면 프로세서가 명령을 하나 들고와서 실행하고 그다음 명령 들고와서 실행하는 방식이다. 하지만 운영체제가 없다면 메모리에 있는 값은 휘발성이기에 임의의 값이 들어있고 프로세서가 할수있는 일은 없게 된다. 프로그램을 실행하려면 하드 디스크에 있는 프로그램을 메모리로 들고 와야 하는데 그 일을 운영체제가 해준다. 또 메모리에는 여러 개의 프로세스가 동시에 실행되어야 하는데 그 일 역시 운영체제가 해주게 된다. ( 프로세스 : 메..
-
백준(BOJ) 14503번 로봇 청소기알고리즘 풀이/백준(Boj) 2019. 8. 30. 15:25
문제 : https://www.acmicpc.net/problem/14503 문제로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.로봇 청소기는 다음과 같이 작동한다.현재 위치를 청소한다.현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 ..