분류 전체보기117 외부단편화와 내부단편화 외부단편화 (External fragmentation) 프로그램을 할당하고 난 다음 아주 작은 크기로 남은 조각들이 생겨 사용할 수 없는 작은 공간들이 많이 생길 수 있습니다. 이 공간들을 합치면 요구되는 공간을 할달할 수 있음에도 불구하고 연속적인 공간이 아니라서 할당하지 못하는 상황을 외부 단편화라고 합니다. 아래 그림을 통해 살펴보겠습니다. 프로세스 A,B,C사이의 총 8K의 공간이 남아있습니다. 프로세스 D는 7K의 공간을 필요로 하므로, 남은 공간은 충분합니다. 그러나 분할하여 할당할 수 없으므로 프로세스D를 할당할 수 없는 문제가 발생합니다. 내부단편화 (Internal fragmentation) 메모리를 할당하는 최소 블록 크기를 10K라고 가정합시다. 만약 7K만큼의 공간을 사용하더라도 1.. 2017. 10. 7. BOJ 1753 최단경로 BOJ 1753 최단경로[https://www.acmicpc.net/problem/1753] 다익스트라를 적용할 수 있는 기본문제입니다. 아래 주소에 다익스트라에 관한 설명과 본 문제의 테스트케이스를 이용한 예제를 확인할 수 있습니다.[http://sycho-lego.tistory.com/7] 우선순위 큐를 이용하여 다익스트라를 구현하였습니다. 정답코드는 아래 주소에서 확인할 수 있습니다.[https://github.com/choseungyoon/Algorithm/blob/master/BOJ/1753_%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C.cpp] 2017. 10. 6. 다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘(Dijkstra Algorithm) 그래프 내에서 최단경로를 정하는 알고리즘은 여러가지가 있습니다. 그 중 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구할 때 사용됩니다.또한 모든 간선의 가중치가 양의 가중치를 가지고 있을 때 사용할 수 있습니다. 다익스트라의 기본적인 원리는 한 정점에서 갈 수 있는 다른 정점 중, 작은 가중치 간선을 우선적으로 탐색하는 방법입니다. 현재 정점을 A라 하고, A와 연결된 가선이 B라고 가정해 봅시다. A까지 이동하는 비용을 a , B까지 이동하는 비용을 b , A에서 B로 이동할 때 발생하는 비용 x 라 할 때a+x < b 라면B까지 가는 비용을 a+x로 갱신할 수 있습니다. 아래 예제를 통해 더 자세히 알아보겠습니다. 위와 같은 .. 2017. 10. 6. 스트래티지 패턴(Strategy Pattern) 스트래티지 패턴(Strategy Pattern) 여러 알고리즘을 하나의 추상적인 접근점(인터페이스)을 만들어이 접근점에서 서로 교환가능하도록 하는 패턴 또한 알고리즘을 정의하고 각각을 캡슐화하여 교환해서 사용가능 하도록 하는 패턴 이와 같이, 각 알고리즘은 캡슐로 정의되어 있고 필요할 때 서로 교환만 하기 때문에알고리즘의 추가 및 수정에 편리합니다. 아래는 기본적인 Strategy 패턴을 나타냅니다. Client는 Strategy를 가지고 있습니다. Strategy는 한개를 가질 수도 있고 여러개를 가질 수 있습니다.Strategy 인터페이스를 통해 세 개의 Strategy(A,B,C)가 캡슐화되어 있음을 알 수 있습니다. 이와 같이 각 알고리즘은 캡슐화되어 분리되어 있고 만약 StrategyA에 수정이.. 2017. 10. 5. BOJ 11811 데스스타 BOJ 11811 데스스타 [https://www.acmicpc.net/problem/11811] 비트연산을 이용하는 문제입니다. 모든 행렬의 값은 각 행 , 열의 and연산으로 이루어져 있기 때문에 각 행의 모든 값을 or연산하면 답을 유추할 수 있음을 쉽게 알 수 있습니다. 모든 j에 대해서ans[i] = ans[i] | arr[i][j] 아래 주소에서 정답코드를 확인할 수 있습니다.[https://github.com/choseungyoon/Algorithm/blob/master/BOJ/11811_%EB%8D%B0%EC%8A%A4%EC%8A%A4%ED%83%80.cpp] 2017. 10. 4. 프로세스(Process)와 쓰레드(Thread) 프로세스와 쓰레드가 각각 무엇인지, 어떤 차이점이 있는지 알아보겠습니다. 한 문장으로 설명하면 다음과 같습니다. 프로세스는 운영체제로부터 자원을 할당받는 작업의 단위, 스레드는 프로세스가 할당받은 자원을 이용하는 실행의 단위 그림으로 나타내면 아래와 같습니다. [Process]프로세스는 운영체제로부터 주소공간, 파일, 메모리 등을 할당 받습니다.그러므로 각 프로세스는 독립적이며 자신만의 고유 메모리를 할당받아 사용합니다. 그리고 프로세스는 실행중인 프로그램을 의미합니다. 그러므로 프로세스는 프로그램이 될 수 있지만, 프로그램은 프로세스가 될 수 없습니다. 실행중이지 않은 프로그램도 존재하기 때문입니다. [Thread]그러나 쓰레드는 프로세스 안에 존재하며, 여러 쓰레드가 자원을 공유할 수 있습니다. 쓰레.. 2017. 10. 4. BOJ 1525 퍼즐 BOJ 1525 퍼즐[https://www.acmicpc.net/problem/1525] BFS를 이용한 완전탐색 문제입니다. 빈칸을 옮겨가며 모든 경우의 수를 확인해보면 되는데문제는 방문체크를 하는 것입니다. 3x3 행렬을 다음과 같이 정수를 변환시켜 보겠습니다. 1 2 3 0 4 5 6 7 8 위 행렬은 123045678 와 같은 정수로 변환할 수 있습니다. STL의 set을 이용하여 변환된 정수를 Key값으로 사용하면 방문체크를 할 수 있습니다. 방문체크를 제외하고는 BFS 알고리즘을 그대로 구현하시면 됩니다. 아래 주소에서 정답코드 확인가능합니다.[https://github.com/choseungyoon/Algorithm/blob/master/1525.cpp] 설명이 잘못 되었거나 이해가 안되시는.. 2017. 9. 25. BOJ 2533 사회망 서비스(SNS) 2533 사회망 서비스(SNS) [https://www.acmicpc.net/problem/2533] 문제를 읽어보시면 친구와의 관계는 Tree로 표현될 수 있다는 것을 알 수 있습니다. 이 문제는 트리 탐색과 메모리제이션을 동시에 하면서 해결 할 수 있습니다. 아래와 같은 친구관계를 가지고 있는 트리를 이용해 설명하겠습니다. 메모리제이션을 이용할 dp테이블은 다음과 같습니다 dp[i][state] : i번째 정점을 root로 가지고 있는 Subtree 에서의 최소 얼리어답터 수 : state == 0 -> 정점 i가 얼리어답터가 아닌 경우 : state == 1 -> 정점 i가 얼리어답터인 경우 우선 루트노드(1번 노드)부터 Leaf 노드까지 탐색합니다. 제일 첫번째 방문하는 Leaf 노드는 5번 노드.. 2017. 9. 24. 블로그 시작 HELLO WORLD :) 오늘부터 블로그 운영을 시작하려고 합니다. 컴퓨터공학 전공인 학생인지라 전공과목 정리 겸 알고리즘 문제풀이 정리 공부를 위해 이 블로그를 시작하게 되었습니다. 알고리즘은 이론을 정리하고 관련 문제에 대한 풀이를 진행할 예정입니다.문제풀이 관련된 소스는 github에 올리도록 하겠습니다 제가 또 여행을 좋아해서 여행 다녀왔던 곳 후기도 차차 올리려구 합니다!간혹 일상 애기도 적을게용! 감사합니다 2017. 8. 28. 이전 1 ··· 10 11 12 13 다음 반응형
