전체 글 (225) 썸네일형 리스트형 PDU, SDU PDU PDU(Protocol Data Unit)는 동일 레이어 간에서 운반되는 데이터를 부르는 이름이다. OSI 7 계층에서 각 계층은 상위 계층으로부터 전달받은 데이터에 헤더 정보를 추가하는데, 이때 각 계층에서 부르는 데이터 단위의 이름이다. 4계층에서는 세그먼트, 3계층에서는 패킷, 2계층에서는 프레임이라고 부른다. 그리고 1계층에서는 2계층으로부터 전달받은 프레임을 비트로 다룬다. SDU SDU(Service Data Unit)는 상향/하향 레이어 간에 전달되는 정보를 말한다. 즉 PDU는 SDU와 헤더 정보인 PCI(Protocol Control Unit)로 이뤄진다. PDU = SDU + PCI Reference http://www.ktword.co.kr/test/view/view.php?m.. [백준] 18808. 스티커 https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 어려운 문제는 아니고 그냥 구현 문제이다. 그런데 스티커 회전이라든지, map에 붙일 수 있는지 없는지 이차원 배열의 범위를 탐색한다든지 짜잘하게 신경써야 할 것이 많다. 그리고 그만큼 실수하기 쉬운 문제이다. 다행히 몇 번 디버깅하면서 맞출 수 있었는데, 그래도 다음에 다시 풀면서 꼼꼼히 생각하자는 의미로 기록한다. import java.io.BufferedReader; import java.io.. HashSet, LinkedHashSet, TreeSet Set Set은 ADT로 다음과 같은 특징을 갖는다. 중복을 허용하지 않는다. 저장 순서를 유지하지 않는다. HashSet 자바에서는 Set 자료구조의 구현체로 HashSet을 제공한다. HashSet은 다음과 같이 Set 인터페이스를 구현하고 내부적으로 HashMap을 사용한다. public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable { private transient HashMap map; private static final Object PRESENT = new Object(); public HashSet() { map = new HashMap(); } } HashSet이 중복된 데이터를 허용하지.. 해시 분포와 해시 충돌, HashMap, LinkedHashMap Map Map은 ADT로 다음과 같은 특징을 갖는다. key-value 형태로 값을 저장한다. key는 중복을 허용하지 않고 value는 중복을 허용한다. 즉, 하나의 key에는 하나의 value만 가진다. 저장 순서를 유지하지 않는다. 해시 충돌 자바의 HashMap은 버킷의 위치를 정할 때 객체의 해시 값을 사용한다. 이때 해시 값은 int형으로 32비트이다. 따라서 어떤 데이터에 대해 나올 수 있는 해시 값은 2^32개이며 그 이상의 데이터들을 HashMap에 저장하려고 하면 몇 개의 데이터들은 해시 값이 같을 수밖에 없다. 그리고 2^32개의 해시 값에 따른 각각 다른 버킷을 메모리 공간에 할당한다면 이는 매우 비효율적이다. 따라서 HashMap에서는 메모리를 절약하기 위해 배열의 capacity.. 우선순위 큐(Priority Queue), 힙(Heap) 우선순위 큐 우선순위 큐는 큐와 비슷하지만 먼저 들어온 데이터가 먼저 나가는 것이 아니라, 우선순위가 높은 데이터가 먼저 나간다. 큐: 먼저 들어온 데이터가 먼저 나간다. (FIFO) 우선순위 큐: 우선순위가 높은 데이터가 먼저 나간다. 우선순위 큐는 추상적인 개념이고, 주로 힙을 통해 구현된다. 힙 힙은 우선순위 큐의 구현 방식 중 하나로 주로 이진 트리 기반으로 구현된다. (이진 트리: 자녀가 최대 두 개인 트리) 최대 힙(Max Heap): 부모 노드의 키가 자식 노드의 키보다 크거나 같은 이진 트리이다. 최소 힙(Min Heap): 부모 노드의 키가 자식 노드의 키보다 작거나 같은 이진 트리이다. 힙의 주요 동작은 다음과 같다. insert: 힙에 데이터를 넣어주는데 이때 데이터의 키 값도 함께 .. 스택(Stack), 큐(Queue) 스택 스택은 가장 나중에 들어간 원소가 가장 먼저 나오는 구조이다. (LIFO) 사용 사례 스택 메모리 예를 들어 StackOverFlowError는 스택 메모리 공간을 다 썼을 때 발생하는 에러로, 주로 재귀 함수에서 탈출하지 못하면 발생한다. 자바에서의 스택 구현 자바는 Stack 클래스를 제공한다. Stack 클래스 외에도 LinkedList와 ArrayList를 통해 구현할 수 있다. 데이터 조회: Top에 있는 원소를 조회할 때는 O(1)의 시간 복잡도를 갖는다. 하지만 Top이 아닌 원소를 조회할 때는 해당 데이터를 찾을 때까지 수행해야 하므로 O(N)의 시간 복잡도를 갖는다. 데이터 삽입: LinkedList를 통한 구현에서는, 단순히 새로운 원소가 Top에 있는 원소를 가리키도록 참조를 변.. [백준] 1744. 수 묶기 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 그리디 문제로, 어떻게 하면 제일 큰 결과 값을 구할 수 있을지 아이디어만 잘 생각하면 된다. 음수의 경우 음수끼리 묶어서 곱해주어야 양수가 되어 결과 값이 커진다. 그리고 이때 절댓값이 큰 음수끼리 우선적으로 묶어주어야 결과가 더 크다. 따라서 음수를 minus 리스트에 모아서 minus 리스트를 오름차순하고 순차적으로 묶어준다. 만약 두개의 음수를 묶고 묶이지 않은 음수가 1개 남는다면, 이.. [백준] 11501. 주식 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 처음에는 입력 값을 배열에 넣은 뒤 배열의 앞에서부터 순차적으로 순회하니 조금 복잡해졌다. 그런데 배열의 뒤에서부터 순회하면 훨씬 깔끔하다. 배열의 뒤에서부터 순회해서 max와 arr[j]를 비교한다. max = arr[j]인 경우, answer에 max-arr[j] 값을 더해준다. (arr[j]를 max 값에 팔.. 이전 1 ··· 24 25 26 27 28 29 다음
