분류 전체보기 (3) 썸네일형 리스트형 [동계 모각코 3주차] BFS 알고리즘 풀이 BFS 알고리즘너비우선탐색으로 가까운 곳부터 탐색하는 알고리즘이다. 이를 위해 FIFO 방식인 Queue 자료구조를 사용하여 방문할 순서를 정한다.이와 대비하여 DFS알고리즘도 존재하는데 이는 재귀함수 또는 Stack 자료구조를 사용하여 방문할 순서를 정하는 알고리즘이다. 이 문제는 L과 R을 입력 받고 각 나라 즉 각 배열 한 칸이 인접한 나라와 비교했을 때 L이상 R이하라면 인구 이동이 일어나는 상황이다. 이를 지속해서 이동하다가 인구 이동이 더 이상 일어나지 않을 때를 구하는 문제이다. 이를 보고 그래프 문제라고 생각을 했고 인접한 것을 계속해서 구해야하기에 BFS알고리즘을 사용해 문제풀이를 해나갔다. 문제를 풀다보니 반복문을 겹쳐서 많이 사용했는데, 입력의 크기가 작아서 그 부분은 깊이 생각하지 .. [동계 모각코 2주차 ] 투포인터 알고리즘 풀이 투포인터 알고리즘left, right를 두어 양쪽에서 조건에 따라 1씩 줄여가면서 정답을 찾는 것.이와 비슷한 알고리즘으로 이분 탐색이 있는데, 이는 left, right을 두고 중간 값을 이용하여 값의 범위를 반 씩 줄여가며 원하는 값을 찾아나가는 알고리즘이다.이 두 개의 차이점으로는 가장 크게 시간 복잡도가 있는데, 이분 탐색은 O(logN), 투포인터는 O(N)으로 차이가 있다. 주어진 수들 중에 어떤 두 수를 더한 값이 주어진 수들 중에 포함이 되었는지를 찾는 문제인데, 일단 입력을 보고 개수가 일차원 배열 밖에 안되는 것을 알 수 있었다. 하지만, 시간 제한을 봤을 때 정렬이 충분히 가능한 것이 보였고 O(N) * N - 각 값에 대해 투포인터 적용으로 이렇게 O(N^2)이 나오기 때문에 충분히.. Computer network - Routing IP 주소가 너무 많기에 이게 수십 억개 IP주소 테이블까지 확장 가능할 수 있다..이를 어떻게 해결할 것인가.현재까지의 가정모든 라우터는 동일하다. → 같은 역할, 같은 정보 공유네트워크는 납작하다. → 계층이 없는 하나의 거대한 네트워크현실에서는 아니다..현실:라우터마다 역할 다름ISP / 기업 / 백본 등 계층 존재모든 라우터가 모든 IP를 알 수 없음해결 방법수십억 개의 IP 주소 테이블 - 메모리 저장 불가, 트래픽 폭발, 계산량 과다→ Scalable Routing네트워크를 계층(level) 으로 나눔각 기관(AS) 내부에서는:내부 라우팅 프로토콜 사용 (OSPF, RIP 등)기관 간(계층 간)에서는:내부 구조를 숨기고 요약된 정보만 교환구체적인 방안으로는 여러개의 IP주소를 하나의 prefi.. 이전 1 다음