본문 바로가기

분류 전체보기239

[백준 *Java] - 트리순회(1991) 트리순회 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEG.. 2022. 4. 22.
트리 순회(Tree Traversal)란? 트리 순회 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말합니다. 하나도 빠뜨리지 않고, 정확히 한 번만 중복없이 방문해야 하는데, 노드를 방문하는 순서에 따라 세 가지로 나뉩니다. 전위순회(preorder) 중위순회(inorder) 후위순회(postorder) 전위 순회 [Preorder] 루트 노드에서 시작해서 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 순회하는 방식입니다. 깊이 우선 순회(depth-first-traversal) 이라고도 합니다. 위 예시 트리에 전위 순회 방식을 적용하면, 1 - 2 - 4 - 5 - 3 이 됩니다. 중위 순회 [Inorder] 루트 노드에서 시작해서 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순으로 순회하는 방식입니다. 대칭 순회(symmet.. 2022. 4. 22.
우선순위 큐 (Priority Queue) 란? 우선순위 큐란? 각 요소가 우선순위를 갖고 있는 자료구조를 말합니다. 일반적인 큐와는 다르게, 입력된 순서와 상관없이 우선순위가 가장 높은 데이터를 가장 먼저 출력하게 됩니다. 우선순위 큐는 Heap을 이용하여, 구현된 자료구조입니다. 우선순위는 배열과 연결리스트로도 구현할 수도 있지만, 최악의 경우에 우선순위 찾기 위해 인덱스의 끝까지 탐색할 수 있기 때문입니다. Heap을 사용한다면, 새 데이터 삽입 시, O(log2N) 그리고 데이터 삭제 시, O(log2N) 입니다. 👇 배열, 연결리스트, 힙 시간 복잡도 비교 더보기 배열 : 우선순위가 높은 순서대로 배열의 가장 앞 부분부터 넣는다면, 우선순위가 높은 데이터를 반환하는 것(삭제)은 맨 앞의 인덱스를 바로 이용하면 되므로 어렵지는 않습니다. 시간 .. 2022. 4. 22.
[백준 *Java] - 서울 지하철 2호선 서울 지하철 2호선 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 서울 지하철 2호선은 다음과 같이 생겼다. 지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다. 두.. 2022. 4. 19.
HashMap & HashTable Hash Algorithm 데이터를 다루는 기법 중에 하나로, 검색과 저장이 아주 빠르게 진행되는 자료구조입니다. 해쉬는 데이터를 검색할 때, 사용할 key 와 value(실제 데이터)가 한 쌍으로 존재하고, key 값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도는 O(1)에 수렴하게 됩니다. 해시가 왜 생겼을까요? 가장 기본적인 자료구조인 배열의 경우, 내부 인덱스를 이용하여 자료의 검색이 한 번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면 데이터의 삽입, 삭제 시 많은 데이터가 밀리거나 빈 자리를 채우기 위해 이동해야 하므로 많은 시간이 소요됩니다. 또한, 연결리스트는 삽입, 삭제 시 인근 노드들의 참조 값만 수정해줌으로 써 빠른 처리가 가능했지만? 처음노드와 마지막 노.. 2022. 4. 18.
HTTP1 vs HTTP2 (두 프로토콜의 차이) HTTP는 1989년에 만들어진 웹의 통신 표준입니다. 97년도에 HTTP/1.1 이 릴리즈 되면서 프로토콜이 거의 수정된 적이 없었습니다. 그러나, 2015년에는 HTTP2 가 나오면서 사용되기 시작했습니다. HTTP2 는 모바일 플랫폼, 서버 집약적인 그래픽과 비디오를 다룰 때, 레이턴시를 줄일 수 있는 여러가지 방법을 제공 했습니다. 또한 그 이후에 점점 더 인기가 많아지면서 현재에는 모든 웹사이트의 1/3 정도 이상이 HTTP2를 지원하는 것으로 알려져 있습니다. 이 설명에선 HTTP 설명을 하기보단, ver1 과 ver2 의 차이점을 위주로 설명할 예정입니다. HTTP 가 무엇인 지를 보고 싶다면, 아래 제가 정리해놓은 글을 한 번 읽고 오시며 좋습니다. https://devnuts.tistor.. 2022. 4. 18.
HTTP 란? HTTP(HyperText Transfer Protocol)는 인터넷에서 데이터를 주고 받을 수 있는 프로토콜입니다. 이번 주제를 알아보기 전에, 프로토콜에 대해서 먼저 설명하도록 하겠습니다. 프로토콜 공통 데이터 교환 방법(의사소통) 및 순서에 대해 정의한 형식, 약속, 규역, 규칙 체계 혹은 프로그램을 일컫는다. 통신 프로토콜은 컴퓨터나 원거리 통신 장비 사이에서 메시지를 주고 받는 양식과규칙의 체계를 말합니다. 즉, 통신 규약 및 약속입니다. 컴퓨터 네트워크 규모가 증가되고, 네트워크를 이용한 정보 전송 수요가 다양화되면서 소프트웨어와 하드웨어 장비가 계속 증가되는 최근의 환경에서 효율적인 정보 전달을 하기 위해서 프로토콜의 기능이 분화되고, 복잡해질 수 밖에 없어졌습니다. 이러한 환경적인 요구를 .. 2022. 4. 17.
이분 그래프(Bipartite Graph)란? 이분 그래프 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프입니다. 다시 말해서, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는 그래프를 이분 그래프라고 합니다. 위 그림을 보면 빨간색, 파란색의 정점이 서로 인접하고 있으며, 같은 색끼리는 인접하지 않습니다. 그리고, 간선이 아예 없고 정점만 있는 경우도 이분 그래프가 됩니다. 이분 그래프는 현실에서도 굉장히 많이 사용하게 됩니다. 몇 가지 예시를 들자면, 학생 - 수업 : 학생들이 어떤 수업을 듣고 있는 지를 관계로 나타낼 수 있습니다. 영화 예약 사이트 회원 - 좋아하는 장르 : 각각의 회원들이 어떤 장르의 영화를 선호하는 지를 나타낼 수 있습니다. 구직자 -.. 2022. 4. 15.

티스토리툴바