IT86 너비 우선 탐색과 최단 거리 너비 우선 탐색과 최단 거리 깊이 우선 탐색과 달리 너비 우선 탐색은 대개 그래프에서의 최단 경로 문제를 풀 때의 용도로 사용된다. 그래서 깊이 우선 탐색에서는 모든 정점을 검사하면서 탐색을 수행하는 작업을 하지만, 너비 우선 탐색에서는 시작점으로부터 다른 정점들까지의 거리만 구하면 된다. ●최단 경로 문제 두 정점을 연결하는 경로 중 가장 길이가 짧은 경로를 찾는 문제 경로의 길이 = 경로에 포함된 간선의 개수 너비 우선 탐색 스패닝 트리를 보면, 각 정점으로부터 트리의 루트인 시작점으로 가는 경로가 그래프에서의 최단 경로임을 볼 수 있다. 그래서 함수 두개가 필요하다. 1. 각 정점까지의 최단 거리와 너비 우선 탐색 스패닝 트리를 계산하는 함수 2. 너비 우선 탐색 스패닝 트리를 입력받아 실제 최단 .. 2020. 8. 30. 그래프 - (백준 1260, 2606, 2667) DFS와 BFS, 바이러스, 단지번호붙이기 그래프 - (백준 1260, 2606, 2667) DFS와 BFS, 바이러스, 단지번호붙이기 문제 출저 - 백준 https://www.acmicpc.net/problem/1260 my code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include #include #include #include using namespace std; vector adj; vector visited; void df.. 2020. 8. 28. 그래프 (DFS, BFS) 그래프 (DFS, BFS) 그래프의 표현 방법 1. 인접 리스트 - vector adjacent; - vector adjacent; adjacent[i]는 정점 i와 인접한 정점들의 번호를 저장하는 연결리스트(혹은 동적배열)임 여기서 추가적 속성을 갖는 그래프를 표현하려면? → pair 사용 2. 인접 행렬 - vector adjacent; adjacent[i,j]는 정점 i에서 j로 가는 간선이 있는지를 나타내는 bool값 변수임 가중치 그래프를 인접 행렬로 표현하려면? → bool이 아닌, int나 float으로 두면 됨 → 두 정점 사이에 간선이 없는 경우에는 이 값을 -1 혹은 아주 큰 값으로 설정 그래프는 트리보다 구조가 훨씬 복잡할 수 있기 때문에 탐색 과정에서 얻어지는 정보가 아주 중요하다 .. 2020. 8. 28. 우선순위 큐와 힙 - 변화하는 중간 값 우선순위 큐와 힙 - 변화하는 중간 값 문제출저 - 알고스팟 https://algospot.com/judge/problem/read/RUNNINGMEDIAN answer code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 #include #include #include using namespace std; int MOD = 20090711; int n; struct RNG { int seed, a, b; RNG(int .. 2020. 8. 24. 이진 검색 트리 이진 검색 트리 검색트리 자료들을 일정한 순서에 따라 정렬한 상태로 저장해둠 원소의 추가와 삭제 + 특정 원소의 존재 여부 확인 등 다양한 연산을 빠르게 수행할 수 있음 검색트리가 사용될 수 있는 곳 예시 - 이미 가입한 사용자들의 주민등록번호를 저장해두고, 특정 사용자가 이미 가입되었나 찾기 - 사용자의 ID를 사용자 정보로 대응시키는 사전 객체 만들기 - 모든 학생들의 시험 점수를 저장해놓고, 나보다 1등 위인 사람과 1등 아래인 사람 찾기 검색트리 중 가장 흔하게 사용되는 것이 바로 이진 검색 트리이다. 이진 검색 트리 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리 왼쪽에는 root보다 작은 값, 오른쪽에는 root보다 큰 값이 들어감 원하는 값을 찾아가는 과정은 배열에.. 2020. 8. 23. 트리 - 트리 순회 순서 변경 트리 - 트리 순회 순서 변경 문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/TRAVERSAL 트리 계층적 구조를 갖는 자료들을 표현하기 위한 자료구조 ex) 대진표, 조직도, 상품 분류 등등 풀이 생각 (삽질) 1. 어떻게 전위랑 중위를 가지고 후위를 찾을까? 1) 전위와 중위를 보고 전체 트리를 만든 후, 후위 탐색을 할까? (트리를 만든 후 후위 탐색) 2) 전위와 중위를 살펴보면서 후위 탐색 (하나씩 살펴보면서 후위 탐색 출력) 2. 왼쪽 오른쪽 어떻게 구분할까? - preorder의 첫번째가 root이고, inorder에서 root가 나오기 전까지 왼쪽인 것을 발견. - inorder에서 왼쪽을 따로 넘겨주고, 오른쪽을 따로 넘겨주고, 계속 반복... 2020. 8. 22. 스택 - 짝이 맞지 않는 괄호 스택 - 짝이 맞지 않는 괄호 문제출저 - 알고스팟 https://algospot.com/judge/problem/read/BRACKETS2 풀이생각 1. 닫힌 괄호일 때 스택검사 => 일치하면 pop, 다르면 바로 return false 2. 열린 괄호일 때 push 3. 함수 마지막에서 스택이 비어있다면 잘 끝난것 (true), 남아있다면 잘못된것 (false) 내 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include #include using n.. 2020. 8. 20. 선형 자료구조 - 조세푸스 문제 선형 자료구조 - 조세푸스 문제 문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/JOSEPHUS 풀이생각 1. 하나의 리스트에서 2명이 남을 때까지 자살한 병사를 삭제 => 특정 위치의 삭제가 용이한 연결리스트를 사용하자 => remove를 사용하려 했으나, 이것은 원소를 탐색하여 제거하는 것. 연결리스트를 선택한 이유가 없어짐 => iterator를 지우는 erase를 사용하자 2. 마지막 원소에서 어떻게 iterator를 처음으로 옮겨줄까? => Linked list 마지막 원소의 다음 iterator에 접근했을 때, Linked list의 begin으로 iterator를 옮겨주기 => 마지막 원소의 다음 주소를 가리키는 end를 사용하자 3. 그럼 어떤.. 2020. 8. 18. 선형 자료 구조 (동적 배열, 연결 리스트) 선형 자료 구조 (동적 배열, 연결 리스트) 1. 동적 배열 ● 배열의 문제점 1. 처음 배열을 선언할 때 크기를 지정해주어야 한다. 2. 그 크기 이상의 자료를 집어넣을 수 없다. => 이 문제를 해결하기 위한 것이 동적배열이다. ● 동적배열의 특징 동적배열의 내부는 배열로 이루어져있기 때문에 배열의 특징을 이어받는다. 배열의 특징 이어받은 것 - 원소들은 메모리의 연속된 위치에 저장 => 캐시의 효율성과 직결되기 때문에 아주 중요하다. - 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있음 동적배열이 가지는 다른 추가 특성 - 배열의 크기를 변경하는 resize() 연산이 가능 => 배열의 크기 N에 비례하는 시간이 걸림 - 배열의 맨 끝에 원소를 추가할 수 있는 append() .. 2020. 8. 17. 탐욕법 - 도시락 데우기 탐욕법 - 도시락 데우기 문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/LUNCHBOX 탐욕법 여러 개의 조각으로 쪼개는 방법. 이는 완전탐색, 동적 계획법이랑 같음. 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 지금 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려하지 않는다. 가장 중요한 건 정당성 증명 (최적 부분 구조) 만약 제일 안 좋은 것이 있다면 그것을 최적해로 가정하자. 그리고 더 좋은 것을 찾으면 그것이 최적해라고 한다. 이렇게 결국 제일 좋은 것을 찾아가 최적해를 찾는다. 귀류법같은 느낌이 난다. 풀이생각 i번째 도시락 데우기 + 먹기. 어느번째 도시락이 오래 걸릴까 체크 i번째 시간 = 데우기시간 + 먹기시작한시간 + 먹기시.. 2020. 8. 17. 분할 정복 - 쿼드 트리 뒤집기 문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/QUADTREE 이것에 중점을 둬보자. - 분할하고, 정복한다. - 재귀 던져준 후에는 생각말자. 절차 - 트리를 입력 받는다. (string) - 입력을 분석 (분할) - 트리를 상하로 뒤집어서 출력 일단 입력을 받고 분할해보자. 아직 분할정복이 감이 안잡혔다. 문제를 보고 분할정복해야지 라는 생각을 못함. 일단 공부하는 부분이 분할정복이라서 어떻게 분할할지 생각해보자. string tree를 입력받는다. w나 b이면 return w, b; -> 기저사례 x이면 4개로 분할 -> 4개의 재귀로 들어감. 분할했으면 정복?병합?해결?도 하자. 순서는 왼쪽위 - 오른쪽위 - 왼쪽아래 - 오른쪽아래 뒤집으면 왼쪽아래.. 2020. 8. 5. [ 네트워크 ] LTE LTE LTE LTE의 구성은 대략 이렇다. 단말과 기지국을 E-UTRAN이라고 부른다. network 이름이다. 맨 밑에 Physical layer가 있고, 그 위에 MAC이 있다. 그리고 그 위에 RLC, PDCP, RRC가 있는데 이것은 LTE에 특화해서 만든 계층이다. Physical이 L1이고, 그 위에 세 개가 L2이다. 이동통신이다보니 L2가 무겁다. RLC : 재전송에 대한 부분 PDCP : 헤더를 압축하는 역할 RRC : Layer3인데, 크기가 절반으로 그려져 있다. RRC는 control 목적으로만 사용한다. control이 아닌 일반 전송용 목적이면 따로 사용하는 것이 없다. 우리가 앞서 배웠던 TCP/IP를 사용하겠다는 뜻이다. L3, L4 … 윗부분에서는 인터넷 프로토콜을 그대로.. 2020. 7. 10. [ 네크워크 ] Wireless Network (무선 네트워크) Wireless Network (무선 네트워크) wireless hosts 유선이 무선이 된 것이기 때문에 접속하는 지점들, Access Point(AP)라고 불리는데, 기지국이 될 수 있다. 이런 무선 송수신기 하나가 network infrastructure에 붙어있다. 이건 유선으로 연결되어 있다. end link 딴에서 노트북이나 스마트폰이 무선으로 AP에 연결되어 있는 것이다. wireless host들은 랩탑, 스마트폰이다. 노트북은 stationary인데, 대부분 한 곳에 앉아서 사용하기 때문에 안 움직인다고 말한다. 스마트폰은 mobile인데, 움직인다고 말한다. 그러므로 무선이라고 반드시 이동성을 의미하는 것은 아니다. mobility는 그림의 아래부분과 같이 이동하여 네트워크를 이동해 가.. 2020. 7. 10. [ 네트워크 ] Data center networks Data center networks 이 그림은 마이크로스프트웨어의 data center이다. 하나나가 server이다. cloud center라고 생각하면 된다. Amazon, Youtube, Akamai, Apple 등에서 data center를 운영한다. 각각 하나의 server가 최대 수용할 수 있는 동시 최대 클라이언트 수가 있을 것이다. 이것의 해결책으로 수많은 server로 load를 분산시키는 것이다. Data center networks data center network의 구성이다. 우리가 아는 네트워크와 비슷하게 생겼다. load balancer에서 각각 server를 분기시켜서 보내게 된다. 스위치가 Tier별로 있다. 이 load balance는 L3가 아닌 애플리케이션 딴에서 라.. 2020. 7. 3. [ 네트워크 ] MPLS : Multiprotocol label switching MPLS : Multiprotocol label switching MPLS : Multiprotocol label switching 지금까지는 IP주소를 가지고 경로를 찾아왔다. IP주소 대신에 고정된 하나의 label을 가지고 forwarding을 해주는 것이다. 특정 source IP주소에서 destination IP주소까지 데이터가 날아가기 위해선 라우터 입장에서 매번 데이터가 지나갈 때마다 같은 주소임에도 불구하고 매번 찾아가야 한다. 특정 src 주소에서 특정 des 주소까지 날아가는 flow가 주어져 있다면 그 flow에다가 하나의 label을 붙이겠다는 것이다. IP주소 대신에 fixed length identifier label이라는 하나의 번호를 부여해서 그 번호면 빠르게 찾을 수 있게 .. 2020. 7. 3. 이전 1 2 3 4 5 6 다음
