HwangHub

문제 링크 해석 숫자 리스트 중 매번 가장 최소의 숫자 두 개를 골라서 합치는 비용을 더해주면 되는 문제이다. ArrayList를 이용해서 매번 정렬을 수행하며 숫자를 관리해도 되지만, 이 문제에 한해서는 힙을 사용하는 게 더 효율적이라 봐서 PriorityQueue를 적용해 풀었다. 코드 public class Main { /* * 수행시간 : 678 ms * * 메모리 : 27 MB * * 시간복잡도 : O(N * logN) * */ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw..

문제 문제 링크 해석 이 문제는 fractional knapsack 유형을 학습하기 위한 연습문제여서 로직 구성을 고민하진 않았다. 딱 한 가지 레슨런이 있다면, 단위 가치 순으로 정렬을 하기 위해 나는 최초 로직에서 트리맵을 사용하려고 했다. 를 트리맵에 넣어서 정렬을 내가 별도로 처리하지 않고 자료구조로 퉁치려고 했는데, key는 중복을 허용하지 않는단 사실을 뒤늦게 알고 아차 했었다... 실전에서는 이런 사소한 디버깅을 하기 어려울 거고, 시간도 부족하니 그냥 정렬 하기 귀찮다고 트리 구조를 이용하는 로직 구성은 하지 않기로 결심했다...(나름의 레슨런) 만약 자료구조를 이용해서 정렬 로직을 대신하고 싶다면 웬만해선 데이터 그룹을 클래스로 묶어서 우선순위큐를 활용하는 게 이롭다. 단, 주의할 점은,..

문제 문제 링크 해석 최대최소값과 같은 최적화를 요구하는 게 아니라 그냥 단순한 계산값을 요하는 문제라서, 입력이 주어질 때 규칙에 맞게 배치해주면 된다. 점수계산은 모두 자리에 앉은 이후에 해야 정확하므로 나중에 다시 N^2만큼 순회해야 한다. 말 그대로 주어진 조건을 코드로 구현할 수 있는지 묻는 문제로 보였다. N도 20까지라서 편하게 구현하면 되는 걸로 봤다. 한 가지 고민을 잠깐 했던 게 있는데, 3번째 조건의 경우 뭔가 정렬을 해야 할 것처럼 겁을 주는(?) 느낌이 들었는데, 애초에 로직이 행렬 순으로 순회하면서 입력을 하므로 별도로 정렬할 필요는 없는 것으로 판단할 수 있었다. 코드 package 알고리즘연습.boj; import java.io.*; import java.util.ArrayL..

문제 문제 링크 해석 누적합이 음수로 변환되는 부분은 계속 더하는 것보다, 다시 구간을 설정하는게 누적합 입장에서 "반드시" 더 좋은 결과가 나올 수 밖에 없다. 따라서 이 문제를 그리디로 풀면 전체 배열을 단 한번만 선형 순회하여 답을 구할 수 있으므로 O(N)으로 도출된다. 코드 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] arr = Stream.of(br.readLine().split(" ..

보호되어 있는 글입니다.

JUNGOL code_blocks 코드 보기 jungol.co.kr 풀이 stack을 사용하면 "stack을 한번 거친 소는 다신 들어올 수 없으므로" 넣는거 N번, 빼는거 N-1번 해서 O(N + N - 1번)의 연산만으로 해결이 가능하다. 코드 package algorithm.jol; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Deque; /** * 수행 시간 : 209ms * 메모리 : 43.4 MB */ public class JOL_1141_불쾌한날 { public static void mai..

자바 서블릿 자바 서블릿은 웹 통신 간 요청에 따른 응답을 동적으로 생성하는 자바 기반의 웹 어플리케이션 기술로, 흔히 "서블릿"이라 줄여 부릅니다. 여기서 말하는 웹 통신 간의 응답은 동적인 웹 페이지가 될 수도 있고, HTTP 응답 메시지일 수도 있죠. 서블릿이 하는 일을 좀 더 열거하여 말해보자면, 서블릿은 비즈니스 로직 실행을 제외하고 TCP/IP 대기 및 소켓 연결부터 HTTP 요청 메시지 헤더/바디 파싱, 그리고 HTTP 응답 메시지를 생성하여 소켓으로 전송해주는 것 까지 전부 수행하는 녀석입니다. (굉장히 많은 일을 하고 있네요) @WebServlet(name = "helloServlet", urlPatterns = "/hello") public class HelloServlet extend..

우리는 보통 TCP와 견주어 UDP를 많이 학습합니다. UDP의 대표적 특징으로는 아래 항목들이 있습니다. 비연결형 프로토콜이다. TCP와 달리 handshake를 하지 않아 속도'는' 빠르다. 하지만 패킷의 유실 관리나 순서 보장을 하지 않아 신뢰성 있는 통신이 불가능하다. 주로 DNS에 IP 주소 요청할 때, DHCP에 사용된다. 개인적으로는 오늘날에는 인터넷 속도도 빠르다보니 신뢰성 있는 통신의 가치가 더 높다고 생각하여 현대 사회에서 대부분의 통신은 TCP 기반으로 이루어질 것이라 생각하였습니다. 실제로 웹 통신에서는 HTTP 통신이 가장 많이 쓰이는데 이게 기본적으로 TCP 기반으로 알려져 있죠. 근데 다시 네트워크를 공부하다가 신기한 사실을 알아냈습니다. 충격적이게도 모든 HTTP가 TCP로 ..

문제 문제 링크 접근 세 가지 풀이로 접근했습니다. DFS 판단 근거 : 그냥 행렬 보자마자 무지성으로 떠오른 풀이입니다. 시간복잡도 : O(NM); 인접행렬로 전체탐색 실행시간 : 344 ms 중복조합 판단 근거 : 격자상 이동 방식에 따라 visited를 검사할 이유가 없으니 이동 방향들의 조합으로 풀 수 있을 것으로 봤습니다. 시간복잡도 : O(NM); 중복조합 nHr == (n + r - 1) C (r) 이므로 (n + r - 1)! / (n - 1)! * (r)! 입니다. 실행 시간 : 160 ms DP 판단 근거 : 점화식이 간단할 것 같았고, 경로가 매 회마다 누적되는 느낌이니 DP로 가능할 것으로 봤습니다. 시간복잡도 : O(NM); 2차원 loop 돌면서 dp matrix tabulati..

✨ 문제 코드트리 문제 링크 📈 해석 구간을 구분하는 유형은 +1 / -1 테크닉을 이용하여 풀 수 있다. 이 문제에서는 구간별 크기의 합을 묻고 있으므로, 모여있는 구간들을 하나의 연속된 구간으로 구분하여 그 크기를 계산하면 된다. +1 / -1 테크닉을 사용하기 위해 입력되는 x의 값을 기준으로 정렬한다. 이 때, x좌표의 범위가 1 이상 10억 이하이므로 +1 / -1 값을저장하는건 모든 x에 대하여 배열 크기를 잡기보다는 좌표 개수만큼만 저장할 수 있도록 자료구조를 사용하면 된다. 나는 어차피 정렬+선입선출로 x를 사용해야 할 것으로 보여서 바로 우선순위큐를 이용하여 관리해 주었다. 이후 +1 / -1 값을 이용하여 0이 되는 지점을 체크하여 연속 구간을 구분하고, 구간이 시작되는 지점의 값을 i..