본문 바로가기

분류 전체보기

 (119)
[Leetcode] 49번 - 그룹 애나그램(Anagrams) 문제 링크: https://leetcode.com/problems/group-anagrams/description/ 1. 문제 파악 애나그램(Anagram): 동일한 문자의 조합으로 이루어진 문자열이면 동일한 값으로 치부문제를 나눠서 정의: 주어진 문자열 배열에서 애나그램인 문자열 끼리 리스트로 묶어서 반환해라.문자열끼리 애나그램 판별애나그램인 문자열끼리 리스트에 추가시간복잡도 파악:1 -> 문자열 배열의 길이: 10000 -> O(nlogn)0 -> 문자열의 길이: 100 -> O(n)시간 복잡도 총합: O(n x nlogn) 2. 핵심 문제 풀이 도출 문제를 나눈것에 대해 풀이를 도출해본다.애나그램 판별은 어떻게 할까? -> 문자열에서 문자의 개수가 동일한지 확인 -> 너무 복잡 -> 정렬을 하면..
[Leetcode] 5번 - 최대길이 palindromic 부분 문자열 문제 링크: https://leetcode.com/problems/longest-palindromic-substring/description/1. 문제 파악문제를 나눠서 정의: 주어진 문자열의 substring 중에서 대칭되는 것중에서 가장 긴것 찾기주어진 문자열에서 좌우 대칭되는 substring 찾기좌우 대칭되는 substring 중에서 제일 긴 것 찾기시간복잡도 파악: 1 범위로 보아 시간복잡도는 O(N^2) 일것으로 예상2. 핵심 문제 풀이 도출문제를 나눈것에 대해 풀이를 도출해본다.좌우 대칭되는 문자열의 중앙값 부터 시작해서 양쪽으로 이동하면서 문자가 일치/불일치를 판단 -> 불일치될때까지 반복하면 대칭되는 문자열을 찾을수 있다. -> O(N)모든 substring에서 가장 긴 좌우 대칭 문..
[LeetCode] 424번 - 가장 긴 반복 문자 교체 (Java, 슬라이딩 윈도우 풀이) 문제 링크: 424. Longest Repeating Character Replacement문제 풀이1단계: 문제 이해목표: 주어진 문자열 s에서 k번 이하의 문자 변경을 통해, 같은 문자로만 이루어진 가장 긴 부분 문자열의 길이를 구하라.제한: 문자열 길이 최대 10⁵ → 선형 알고리즘이 필요.2단계: 어떤 알고리즘을 써야할까?문자 배열에 저장된 연속된 문자에 대해서 탐색이 필요 -> 탐색 범위를 지정해서 결과값을 도출해야한다. -> 슬라이딩 윈도우 필요왼쪽 포인터를 이동: 조건이 불일치해서 다음 범위를 지정하기 위해서이다.오른쪽 포인터를 이동: 조건이 일치해서 탐색 범위를 확장하기 위해서이다.조건 만족: 최대값 혹은 최소값을 계산하여 결과값을 업데이트한다.3단계: 핵심 아이디어 도출조건을 위반하는 경..
[LeetCode] 3번 – 중복 없는 가장 긴 부분 문자열 (Java, 슬라이딩 윈도우 풀이) 1. 문제 파악해당 문제 유형은 단순히 구현이나 자료구조와 알고리즘을 아는 것보다 동작을 추상화해서 수식 또는 알고리즘으로 모델링하는 것이 핵심이다.문제 링크: https://leetcode.com/problems/longest-substring-without-repeating-characters문제 정의:주어진 문자열의 substring에서 알파벳이 중복되지 않는 문자열 찾기중복되지 않는 substring 중에서 제일 긴거를 찾기문제의 제약 파악 (입력값 크기, 상수 조건)0 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출중복 문자가 없는 substring을 찾을려면, 중첩 반복문으로 하나의 문자를 지정하고 나머지 문자들을 확인해야한다. 그러면 n + n-1 + n-2 + ... = n(n+1)/2 ..
[Java] WAS의 Keep-Alive 구현 - TCP 연결과 해제 비용 줄이기 문제 발생 시나리오 이제까지 내가 구현한 초기 웹서버 모델은 하나의 TCP 연결에 대해서 하나의 요청을 처리하는 구조이다. 일단 나는 WAS의 초기 모델을 구현했을때, HTTP Keep-Alive에 대해서는 이론적으로만 어느정도 알고 있었다. 실제로는 어떻게 동작하는지는 몰랐었다. 내가 개발한 WAS를 크롬 브라우저로 테스트하기위해서 index.html파일을 GET 요청해보았다. 해당 index.html파일은 8개의 이미지 페이지 로딩이 필요했다. Hello Client! 서버의 요청 처리 결과크롬 브라우저로 요청을 날려보니, WAS에게 요청하기 위해서 병렬로 최대 6개의 연결을 맺는것을 로그로 확인하였다.아래는 클라이언트와 연결된 소켓 6개에 대한 로..
[Java] WAS의 HTTP 버전에 따른 확장성 구현 (2): 요청 메세지 파싱 객체 설계 내가 직접 구현중인 WAS의 HTTP 버전을 공통으로 처리하는 구조에서 요청 메세지의 파싱하는 객체를 설계하고 적용할려고한다. 이때 해당 객체를 설계하고 적용할려는 과정에서 겪게되는 문제를 해결하는 과정을 쓴 글이다. 공통의 구조로 여러 HTTP 버전을 처리할수 있다면, 재사용성과 확장성이 확보되어 유지보수하기 좋을것이다. 여기서 각 객체의 역할은 공통적이어야 한다. 이때 인터페이스를 정의하고 구현체를 외부에서 주입(Dependency Injection)하여, 객체 간의 결합도를 낮추고 코드의 유연성 및 재사용성을 높일수 있다.1. HTTP 버전에 따른 파싱 로직 파악하기WAS의 HTTP 버전에 따른 확장성 구현 (1) - HTTP1.1과 HTTP2.0의 메세지 전송 포맷과 방식 차이 이해에서 HTTP/..
WAS의 HTTP 버전에 따른 확장성 구현(1) - HTTP1.1과 HTTP2.0의 메세지 전송 포맷과 방식의 차이 이해 1. HTTP/1.1과 HTTP/2.0의 메세지 전송 포맷의 차이HTTP/1.1과 HTTP/2.0은 메세지의 전송 포맷과 방식이 다르다. 텍스트 기반의 HTTP/1.1 메시지 포맷HTTP/1.1에서 메세지는 텍스트 기반 메세지이며, header와 body를 CRLF(\r\n)으로 구별한다. 따라서 HTTP/1.1 메세지를 전달 받은 웹 서버는 텍스트 단위로 파싱을 수행해야한다. 바이너리 프레임 기반의 HTTP/2.0 메시지 전송 포맷과 헤더 압축반면, HTTP/2.0에서는 메세지가 바이너리 프레임 단위로 나뉘어 전송되며, header frame와 data frame으로 구분된다. 따라서 바이너리 형식으로 인코딩된 프레임을 전달받은 웹서버는 바이너리 디코딩을 해서 파싱을 해야한다. 그리고 HTTP/1...
[Java] WAS 구현- HTTP/1.1 Keep-Alive 구현 후 서버가 응답을 보내기 전에 연결이 끊기는 이슈 사건의 발단내가 구현한 HTTP 웹서버의 성능을 간단하게 테스트하고자 했다. 그중에서 HTTP Persistent Connection 기능을 구현한 것에 대해서 테스트를 해볼려했다. 처음에는 Apache Bench(ab)를 사용해서 테스트를 해보았지만, 소켓 연결을 유지한채로 여러 요청을 보내는 기능은 제공하지않았다. 그래서 HTTP Persistent Connection 성능 테스트를 지원하는 WRK을 사용하였다. WRK란?wrk is a modern HTTP benchmarking tool capable of generating significant load when run on a single multi-core CPU. It combines a multithreaded design with sca..

티스토리툴바