본문 바로가기

전체 글

 (119)
[Leetcode] 19번 - Remove Nth Node From End of List 1. 문제 파악문제 링크: https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/문제: 마지막 노드로부터 n번째 노드를 삭제하고 head를 반환해라.시간복잡도 파악: 연결리스트의 입력 크기가 30이라서 O(N) 이내어야한다. 2. 입출력 케이스 도출일반 케이스: head = [1,2,3,4,5], n = 2 -> [1,2,3,5], head = [1,2], n = 1 -> [1]엣지 케이스: head = [1], n = 1 -> [], head = [1,2], n = 2 -> [2] 3. 핵심 문제 풀이 도출연결리스트의 끝에서 n번째 노드를 삭제하는 것이다. 그래서 나는 스택 자료구조가 떠올랐다. 스택에 연결리스트 노드를..
[Leetcode] 143번 - Reorder List 1. 문제 파악문제 링크: https://leetcode.com/problems/reorder-list/문제: L0 → L1 → … → Ln - 1 → Ln 수열인 연결 리스트를 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …로 재정렬해라.시간복잡도 파악: 입력크기가 50000이라서 O(nlogn) 이내어야한다. 2. 입출력 케이스 도출짝수: [1 2 3 4]홀수: [1], [1 2 3 4 5 6 7] 3. 핵심 문제 풀이 도출 양쪽 끝 투 포인터(left, right) 사용해서 연결 리스트를 재정렬할수있다. 여기서 left와 right는 기존 리스트의 노드 순서를 가리킨다.EX1) [1, 2, 3, 4][1, 2, 3, 4]: left = L1, right = L4Logic: ..
[Leetcode] 128번 - 가장 긴 연속하는 수의 개수 1. 문제 파악문제 링크: https://leetcode.com/problems/longest-consecutive-sequence문제 요구사항: 주어진 배열에서 연속된 요소의 개수를 세서 반환해라시간복잡도: O(N) 내에 풀라고 명시 -> 정렬 알고리즘은 못쓴다. 2. 핵심 문제 풀이 도출 일단, O(N) 내에 풀라고 명시했기 때문에, O(NlogN)인 정렬 알고리즘은 못쓴다. 배열을 한 번 순회하면서 연속된 수 체크해야한다. 그렇다면 정렬 없이 빠르게 값의 포함 여부를 확인하는 자료구조가 필요하다. HashTable 자료구조를 기반으로 하는 HashSet이나 HashMap 자료구조는 평균 O(1) 내에 가능하다. 따라서 해당 자료구조로 문제 풀이를 접근해본다. 배열을 순회해서 저장한 HashTable..
[JVM] Garbage Collection 개념과 동작원리 개요GC(Garbage Collection)는 왜 필요할까?C나 C++로 작성하는 프로그램은 개발자가 직접 동적으로 할당된 메모리 영역에 대한 해제를 해줘야했다. 이렇게 런타임중에 할당한 메모리 영역을 사용하고 필요없어졌을때 정상해제가 안된다면, 메모리 누수가 발생해서 프로세스가 OS로부터 할당받은 메모리 영역이 고갈된다. Java에서는 필요없게된 Heap 영역의 객체를 자동을 해제해주고 개발자는 로직 작성에만 신경쓸수 있도록 개발하였다. 이러한 작업을 수행하는 주체는 Garbage Collector라하며, 사용이 끝나 필요없는 쓰레기(garbage) 객체를 회수(collection)하는 작업이라서 GC(Garbage Collection)라고 부른다. GC의 장점개발자의 실수로인한 메모리 누수를 방지할..
[Leetcode] 347번 - Top K Frequent Elements (using Array) 1. 문제 파악문제 링크: https://leetcode.com/problems/top-k-frequent-elements/문제: 주어진 배열의 요소값중에서 빈도수가 가장 높은 요소를 k개 저장한 배열을 반환해라.시간복잡도 파악: 입력크기가 100000이라서 O(N\logN) 이내어야한다.문제 나눠서 정의배열을 순차적으로 조회하면서 요소별로 빈도수 연산 -> 가장 빈도수가 큰 요소들을 반환해야하므로 동적으로 빈도수 연산을 하지못한다. 따라서 각 요소별로 모든 빈도수를 계산하고 key, value를 상요하는 자료구조에 저장해야한다.자료구조를 빈도수 크기로 정렬한다. (단, 빈도수가 중복되는 요소값이 존재한다.)정렬된 자료구조에서 k개 만큼 값을 가져와서 반환 배열에 저장 2. 핵심 문제 풀이 도출배열을 순..
[Leetcode] 238번 - Product of Array Except Self 1. 문제 파악문제 링크: https://leetcode.com/problems/product-of-array-except-self/description/문제: 자기 자신을 제외한 주어진 배열의 모든 요소의 곱셈을 저장한 배열 반환시간복잡도 파악: 입력 크기가 10000개 이내라서 O(N log N)이하면 되지만, 문제에서 O(N)이내로 해결하라고 명시되어 있다.2. 문제 풀이1. 브루트 포스로 문제 풀이 도출배열을 순차적으로 조회한다.현재 조회하는 요소가 아닌 모든 요소의 곱을 반환할 배열에 저장한다.위의 로직대로라면 O(N^2)시간이 걸린다. 2. 핵심 문제 풀이 도출시간복잡도가 O(N) 내에 해결해야하므로, 배열 조회할때 반환할 배열의 연산(계산과 저장) 끝나야한다. 배열 조회 시간이 O(N)이기 ..
[Leetcode] 647번 - palindromic substring 문제 링크: https://leetcode.com/problems/palindromic-substrings/1. 문제 파악문제를 나눠서 정의: 주어진 문자열의 substring 중에서 좌우 대칭되는 개수 구하기주어진 문자열에서 좌우 대칭되는 substring 찾기좌우 대칭되는 substring을 카운트 하기시간잡도 파악: 1 범위로 보아 시간복잡도는 O(N^2) 일것으로 예상 2. 핵심 문제 풀이 도출문제를 나눈것에 대해 풀이를 도출해본다.좌우 대칭되는 문자열의 중앙값부터 시작해서 양쪽으로 이동하면서 문자가 일치/불일치를 판단 -> 불일치될때까지 반복하면 대칭되는 문자열을 찾을수 있다. -> O(N)모든 substring중에서 좌우 대칭되는 것을 카운팅해야되기 때문에, 모든 문자를 중앙값으로 두고 좌..
[Java] WAS의 Keep-Alive 구현 후 적용/미적용 성능 테스트 비교 Keep-Alive 구현 개요사전 질문: 왜 Keep-Alive를 구현했나?WAS의 Keep-Alive 구현 - TCP 연결과 해제 비용 줄이기에서 내가 개발한 WAS에 Keep-Alive(persistent connection) 기능을 추가해서 구현하였다. 일단 나는 WAS의 초기 모델을 구현했을때, HTTP Keep-Alive에 대해서는 이론적으로만 어느정도만 알고 있었다. 실제로는 어떻게 동작하는지는 몰랐었다. 내가 개발한 WAS를 크롬 브라우저로 테스트하기위해서 index.html파일을 GET 요청해보았다. 해당 index.html파일은 8개의 이미지 페이지 로딩이 필요했다. Hello Client! 크롬 브라우저로 요청을 날려보니, WAS에게 ..

티스토리툴바