목록Study/닥치는 대로 주워 담기 (87)
일단 씻고 나가자
2023. 08. 01 화요일 - 최소 신장 트리란? 관련 두 알고리즘 설명, 구현? : MST(Minimum Spanning Tree). 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법. 크루스칼과 프림 알고리즘이 있다. 크루스칼 알고리즘은 간선을 기준으로 최소 그래프를 연결하는 방법. 간선이 작은 순서대로 연결하며, 사이클이 생길 시에 취소하고 다음 최소 간선을 택한다. 간선이 적을 때 사용된다. 최소 신장 트리의 성격상 사이클을 만들 필요가 없으므로(사이클이 생겼다면 이미 이전에서 최솟값들로 이루어진 간선을 택하는 것이 유리) 사이클을 포기하는 것이다. 사이클 확인의 구현 방법은 Union-find라는 배열을 사용한다. 배열은 특정 인덱스 노드의 부모 노드를 탐색하기 위한 기능으로, 두 노드..
2023. 07. 27 목요일 - [Effective Java] 가변인자? 사용법, 주의사항? 힙 오염이란? : 가변인자란 메서드의 매개변수 개수를 사용자의 임의대로 받을 수 있게 작성한 메서드다. void function(String...str) 와 같이 ... 으로 사용하며, 받은 매개변수는 배열 형태로 전달된다. (빈 매개변수를 전달해도 가능) function(String s, String...str) 와 같이 매개변수의 순서를 컴파일러는 인지하지 못하기 때문에 가변인자를 선언할 때는 꼭 매개변수의 마지막에 선언하여야 한다. 또한 가변인자를 활용한 메서드는 오버로딩을 하지 않는 것이 좋다. https://sleepyeyes.tistory.com/29 힙 오염(heap pollution)이란 컴파일러..
2023. 07. 26 수요일 - TCP의 구성 요소? : 기본적으로 헤더와 data 부로 구성되어 있다. data는 이전 계층에서 전달받은 부이며, 헤더에 실제로 TCP 계층에서 붙일 내용이 들어간다. TCP header에 들어갈 내용은 다음과 같다. * source/destination port : 출발/목적지 포트번호. IP 정보는 후 계층(internet)에서 전달. * sequence number : 송신된 데이터의 순서 번호. 데이터가 다른 순서로 올 때 저장했다가 순서대로 정렬한다. (전달받지 못한 데이터 요청도 한다.) * ack number : 수신된 데이터 순서 번호 +1 요청. 잘 받았다는 의미. * code bits : 데이터의 속성에 대한 1비트 정보. - 3 way handsha..
2023. 07. 20 목요일 - [Effective Java] UnaryOperator란? : 단항 연산자라는 뜻으로, 자바에서 지원하는 함수형 인터페이스이다. 매개변수와 동일한 타입의 return을 반환하며, 함수형으로 선언한다. (ex. UnaryOperator uo = I -> I*2; ) stream의 iterator에 사용되며, 따라서 stream의 map 같은 함수의 매개변수로 전달할 수 있다. 따라서 재사용성이 증가한다. + 형변환한 메서드보다 제너릭 메서드로 만들어서 쓰자!! - OSI 7 Layer의 5~7 계층 설명, TCP/IP? 5. 세션 계층(Session Layer) : 세션별로 데이터 송수신이 가능하도록 관리. 세션 또는 대화(dialogue)를 연결, 관리. 이때 세션이란 ..
2023. 07. 19 수요일 - 플로이드-워셜 알고리즘? 조건, 구현 방법? : Floyd-Warshall 알고리즘. 시작 노드가 아닌 모든 노드 간 최단 경로를 구하는 알고리즘이며, 음의 간선이 포함돼 있어도 사용 가능하고 음수 사이클이 있다면 정상 동작하지 않는다. 음수 사이클의 판별 기준은 자기 자신으로 향하는 값이 0이 아니라 음수값이 나온다면 음수 사이클이 존재한다는 의미. 모든 노드 간의 최단 경로가 나오기에 v*v의 메모리가 필요하다. 1. 우선 v*v 배열에서 자기 자신은 0, 제외한 모든 노드는 INF로 초기화 후 시작한다. 2. 인접 노드의 값을 갱신한다. 3. 이후 인접 노드를 ‘거쳐서’ 가는 노드들에 작은 값으로 갱신한다. - OSI 7 layer에서 데이터 전송의 데이터 단위 기..
2023. 07. 18 화요일 - 벨만 포드 알고리즘이란? 조건, 구현? 음수 사이클, 판별법? : 최단 간선을 구하는 알고리즘. 음수 간선이 포함되어 있어도 가능하다. 알고리즘은 노드의 수를 간선을 중심으로 이중 for문을 돌며, 출발 지점만 가중치를 0으로 두고 나머지는 INF으로 초기화, 이후 값이 INF라면 값을 더해도 오버플로우가 나므로 continue 하며 v번만큼 원래 있던 값과 현재 가중치+간선 값이 더 작은지 판별하고 작은 값으로 수정한다. (v만큼 반복하기에 visited 방문 배열이 필요 없다.) 단 음수 사이클이 있으면 정상 동작하지 않으며, 매번 모든 간선을 확인하기에 다익스트라에 비해 느리다. 즉, 노드의 개수 v만큼 반복한다. 음수 사이클이란 사이클에서 음수 값이 더 큰 경우로..
2023. 07. 17 월요일 - [Java] concurrentmodificationexception이란 무엇이며 해결 방법? : 컬렉션의 순회 중 특정 원소를 삭제나 수정할 때 일어난다. 해결 방법은 Interator의 remove()를 쓰거나, 삭제할 원소를 다른 컬렉션에 모아두고 한 번에 removeAll()로 처리하는 방법이 있다. - [Effective Java] 컴파일러의 warning이란? 문제점과 해결책? : 컴파일러의 경고 표시로, 실행하여 치명적인 결과를 낳진 않기에 진행하여도 상관없으나 경고를 주는 표시. ‘비 검사 경고’라 한다. ‘기술 부채’처럼 이전에 하나씩의 경고가 쌓여 큰 에러로 돌아올 수 있으며, 많은 warning을 무시하고 진행했을 때 에러가 터지면 정작 어떤 부분이 ..
2023. 07. 14 금요일 - 하노이탑 논리 및 구현 방법? : start 막대에 n개의 모든 원반이 처음에 세팅돼있고, mid의 빈 두 번째 막대와 to의 보내고자 하는 막대 3개가 있다고 하자. 하노이탑을 옮기는 방법은 우선 마지막 원반을 제외한 모든 원반을 mid로 옮기고, 마지막 원반을 start에서 to로 보낸 후, mid에 있는 n-1개의 원반을 마지막으로 to로 보내는 알고리즘을 갖는다. 맨 처음 if(n==1) 의 의미는 아직 잘 모르겠다. - 정수의 한 자리만 바꿨을 때 최댓값이 되는 값을 구하는 방법? : 각 자릿수를 역순으로 하나씩 탐색하면서 그 순간까지의 max 값을 계속 반영하는 배열을 하나 만든다. 이후 원래의 배열과 같은 자리일 때 다른 숫자라면 해당 자릿수를 바꿔주면 된다..
2023. 07. 13 목요일 - [Effective Java] Nested class란 무엇이며 종류? 추천? : 둥지 클래스란 의미로, 클래스 내부에 클래스가 존재하는 형태의 클래스. 1. Member class 클래스 내부에 클래스를 생성하여, 내부 클래스는 외부 클래스의 필드에 접근할 수 있다. 2. static member class 클래스 내부에 static으로 클래스를 생성. 상위 클래스가 무조건 참조되어야 하는 1번과 달리 독립적으로 존재 가능. 3. anonymous class 인터페이스 혹은 abstract 클래스를 객체 생성 당시에 구현 및 상속하여 구현해야 할 메서드들을 선언하는 방법. 4. local class 메서드 내부에서 사용하는 클래스. 멤버 클래스는 되도록 static으로..
2023. 07. 12 수요일 - 그리디 알고리즘? 장단점? 그리디 알고리즘 적용 조건? 예시 문제? : Greedy Algorithm. 매 순간 최선의 해를 선택함. 빠르게 근사치를 계산할 수 있지만, 결과적으론 최적해(정답)가 아닐 수 있음. 그리디 알고리즘을 적용할 수 있는 조건 2가지는 다음과 같다. 1. 탐욕적 선택 특성(Greedy choice property) // 지금의 선택이 다음 선택에 영향을 주지 않음 2. 최적 부분 구조(Optimal substructure) // 전체 문제의 최적해는 부분 문제의 최적해로 이루어짐 예를 들면 거스름돈 최소 동전 개수 문제가 있는데, 500, 100원 단위만 있다면 500이 100으로 이루어질 수 있으므로 조건에 부합하지만, 400원 단위가 추가되면..