[JAVA]

https://www.acmicpc.net/problem/2568전깃줄이 교차? 전깃줄이 교차한다는 것은 무엇일까?두 개의 전깃줄이 교차하려면 A의 위치와 B의 위치가 꼬여있어야한다. 예를 들어 임의의 두 전깃줄 a, b가 있다고 할때, a의 전봇대 A에서의 위치를 a1, B에서의 위치를 a2 라고 하고,마찬가지로 b1, b2 라고 했을 때, a1 > b1 이면 a2 a1 b2 일때,전깃줄이 꼬인다고 할 수 있다. 그렇다면 한 전봇대에 대해 오름차순으로 정렬한 다음,반대편 전봇대에 연결되어있는 위치가 "꼬여있는"지를 확인하면 된다. 예를 들어,주어진 예제 입력의 경우에서,전봇대 B의 위치에 대해서 오름차순으로 정렬을 한 후 전봇대 A의 위치를 살펴보자. index01234567B124678910A426..

https://www.acmicpc.net/problem/28872024.06.09 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application1. an Application Union-Find 를 알아보기 전에 이것을 언제 사용하는지를 먼저 파악하는 것이 좋아보입니다. MST(* Minimum Spanning Tree), 최소신장트리는 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최hw-hk.tistory.com문제를 처음 보자마자 최소 신장 트리 문제임을 알았다.하지만 기존의 최소 신장 트리..

https://www.acmicpc.net/problem/16566문제는 단순해 보였다.처음 문제를 읽자 마자 생각한 것은 다음과 같다.리스트에 민수가 뽑은 숫자들을 담는다.리스트를 정렬하고 철수가 보여주는 카드보다 큰 수의 숫자를 뽑는다.뽑은 숫자는 삭제하고 2번으로 돌아간다. 왜 리스트를 정렬하는가? 리스트를 정렬하지 않으면 철수가 보여주는 카드보다 큰 수들 중 가장 작은 수를 찾기 위해서는 선형탐색밖에 답이 없기 때문이다. 선형탐색의 시간 복잡도는 O(N) 이므로, 최대 4,000,000 x 10,000 = 40,000,000,000 의 연산이 필요하다. 대충 100,000,000 에 1초 이므로, 이는 반드시 시간초과가 발생한다. 하지만 정렬을 한다면 다르다. 정렬이 되어있는 자료구조에 대해서는 ..

https://www.acmicpc.net/problem/16236BFS 를 통해 최단거리를 구하는 문제인 것 같다.다만 같은 거리일 경우의 우선순위(* row index 가 작은게 먼저, col index 가 작은게 먼저) 가 추가적으로 붙어있다.그 외의 것들은 크게 다르지 않다. 이런식으로 쭉 풀어봤는데... 메모리 초과가 떴다. 처음이었다. Point 클래스를 너무 남발하면 그럴 수 있다더라...앞으로는 메모리도 좀 신경쓰면서 구현해야겠다. 처음에는 모든 가능한 노드에 대해 Point 객체를 생성해서 비교했었다. 이런 불필요한 인스턴스들은 메모리를 많이 잡아먹을 수 있다. 그래서 이동 가능할 수 있는 노드들을 Point 객체가 아닌, 그냥 row index 와 col index 를 이용했다. 또한 ..

https://www.acmicpc.net/problem/1167아.. 어렵다 처음 생각으로는 DFS 를 여러번 수행해서 각 노드에 대한 최대 길이를 구하려고 했지만N = 100,000 이고 DFS 를 각 노드에 대해 수행하면 빨라야 O(N^2) 이기 때문에 당연히 시간초과가 발생하는거였다.(* 10,000,000,000 번의 계산이 필요한데 일반적인 CPU 는 1억번의 연산 당 1초가 걸리기 때문에 100초가 걸린다.) 어쩔 수 없이 구글링을 해봤는데단 두 번의 DFS 만으로 트리의 지름을 알 수 있는 방법이 존재했다. 트리의 성질을 이용하면 가능한데, 자세한 증명은 아래 접은 글에 첨부해놓았다.더보기https://velog.io/@besyia0k0/Algorithm-diameter-of-tree [알..

0. 들어가기 전 Heap은 '우선순위 큐'에 사용되기 위해 필수적으로 알아야 하는 자료구조입니다. 추가적으로 흔히 동적으로 변수를 만들 때 해당 변수가 저장되는 공간인 Heap 과는 다른 의미입니다. 1. Heap Heap 은 최소값 또는 최대값을 빠르게 찾아내기 위해 완전이진트리의 형태로 만들어진 자료구조입니다. 이진 트리는 아는데 완전 이진트리는 무엇일까? 1.1 Complete Binary Tree 트리(Tree)는 계층 구조를 갖는 자료구조로서, 서로 연결되어 있는 노드들의 집합입니다. 트리에는 자식들과 가지의 형태로 연결되어있는 루트 노드가 있습니다. 이때 이진 트리(Binary Tree)는 자식 노드의 개수를 최대 2개로 정한 트리입니다.  사실 이진 트리는 우리가 일전에 살펴본적이 있습니다..

KeyWord :호스트, 도메인, IP, HTTP 상태코드, Statefull, Stateless, 세션, 쿠키  0. 클라이언트 - 서버 웹 서비스를 예로 들어 설명하자면, 흔히 컴퓨터, 즉 데스크탑이나 노트북으로 자주 사용하는 사이트들이 웹 사이트입니다. 이때 클라이언트란 서버의 서비스를 받아 사용하는 장치 혹은 프로그램을 의미합니다. 그렇다면 서버는 무엇일까? 서버는 데이터를 포함하거나 네트워크의 다른 컴퓨터에서 엑세스하는 기능을 제공하는 컴퓨터입니다.   일반 서버의 유형으로는파일을 저장하는 파일 서버이름과 주소를 저장하는 이름 서버프로그램과 애플리케이션을 저장하는 애플리케이션 서버인쇄 작업을 해당 대상으로 스케줄하고 지시하는 인쇄 서버가 있습니다. 만약 www.naver.com  이라는 URL ..

들어가기 전. 스택에 관해서는 이전 자료구조 수업 정리에서 충분히 설명했다고 생각하기 때문에 자세한 설명은 생략하겠습니다.2024.04.11 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 5 - Queue and Stack Stack 은 ArrayList 와 비슷하게 실제 JAVA 에서는 vector 를 기반으로 구현합니다. 이는 자료의 크기가 동적으로 변할 수 있음을 의미하고, 이에 관한 기능은 ArrayList 와 매우 유사합니다.2024.04.26 - [자바[JAVA]/자바[JAVA] 자료구조 구현] - 자바[JAVA] 자료구조 구현 2 - ArrayList Stack 코드 import Interfaces.Istack;import java.lang.reflect.Array;import jav..