전체 글
[Algorithm] 외판원 순회 문제(Traveling Salesman Problem)
[Algorithm] 외판원 순회 문제(Traveling Salesman Problem)
2023.04.06외판원 순회 문제(TSP) 외판원 순회 문제(TSP)는 조합 최적화 문제 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다. 즉, 아직까지 다항 시간에 해결할 수 있는 해결책을 못찾았으며 해결하지 못한다는 것도 증명하지 못했다. 외판원 문제의 내용은 다음과 같다. 예를 들어, 어떤 외판원이 n개의 도시를 방문할 계획을 갖고 있다고 하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위해 외판원이 출발하는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 경로를 찾고자 할 때, 어떻게 찾을 수 있을까? 만약 20개의 도시가 있을 때 정답을 찾기 위해 다녀야 하는 총 경로 수는..
[Java] HttpServlet
[Java] HttpServlet
2023.04.06HttpServlet HttpServlet은 GenericServlet을 상속하고 있고 GeneralServlet은 Servlet을 구현한 클래스이다. 그럼 차례대로 알아보자. Servlet Servlet은 서블릿 생명주기와 정보에 관련된 메서드들이 선언되어 있다. init() servlet이 처음 로딩될 때 한 번 호출되는 메서드 예외가 생겼을 경우 UnavailableException이나 ServletException 발생 service() client로부터 servlet에 대한 요청이 있을 때 호출되는 메서드 성공적으로 Init() 메서드가 호출되면 수행된다. client의 요청 방식에 따라 get일 경우 doGet(), post일 경우 doPost() 메서드를 호출한다 destroy() servl..
[Java] 스트림(Stream)
[Java] 스트림(Stream)
2023.04.06스트림(Stream)? 스트림(Stream)은 Java 8 API에 새로 추가된 기능이다. 스트림을 이용하면 선언형으로 컬렉션 데이터를 처리할 수 있다. 여기서 선언형이란 데이터를 처리하는 구현 코드 대신, 질의로 표현하는 것을 말한다. 또 스트림을 이용하면 멀티스레드 코드를 구현하지 않아도 데이터를 투명하게 병렬로 처리할 수 있다. 그럼 다음 예시 코드를 한번 보자. List highRatingMovies = new ArrayList(); for (Movie movie: movies) { if (movie.getRating() > 7) { highRatingMovies.add(movie); } } Collections.sort(highRatingMovies, new Comparator() { publi..
[Network] 스위치
[Network] 스위치
2023.04.05스위치? 이전에 스위치에 대해 잠깐 살펴본 적이 있다. 스위치는 Collision Domain을 나누어, 허브가 모든 영역에 영향을 미치는 문제점을 보완할 수 있다고 했다. 잠시 뒤 설명할 브리지도 이와 같은 역할을 한다. 브리지 보통 사용되는 스위치 이외에도 브리지라는 장비가 있다. 브리지도 스위치와 같이 콜리전 도메인을 나누는 역할을 한다. 이렇게 보면 스위치와 많은 차이가 없어보이지만, 여러가지 차이가 있다. 먼저 브리지와 스위치의 공통된 대표적인 기능은 다음과 같다. 브리지 & 스위치 기능 Learning 한 PC가 데이터를 보내면 브리지가 다리를 건너 보낼 것인지 판단하는데, 이때 데이터를 보낸 PC의 맥 어드레스를 자신의 브리지테이블이라는 곳에 저장한다. 이는 다음에 누가 테이블에 저장한 PC..
[Java] 메서드 참조
[Java] 메서드 참조
2023.04.04메서드 참조? 메서드 참조는 람다 표현식을 축약한 형태이다. 메서드 참조를 사용하면 람다 표현식을 더 줄일 수 있는데, 상황에 따라 가독성이 더 좋아보일 수 있다. 다음은 람다 표현식을 메서드 참조로 바꾼 예시이다 inventory.sort((Apple a1, Apple a2) -> a1.getWeight().compareTo(a2.getWeight())); inventory.sort(comparing(Apple::getWeight)); 메서드 참조는 실제로 메서드를 호출하는 것이 아니기 때문에 괄호는 적지 않는다. 메서드 참조 형태 메서드 참조는 크게 3가지 형태가 있는데, 한 번 살펴보자. 정적 메서드 참조 예를 들어 Integer의 parseInt 정적 메서드를 다음과 같이 메서드 참조 형태로 바꿀..
[Java] 람다 타입 검사/추론/제약
[Java] 람다 타입 검사/추론/제약
2023.04.04타입 검사 람다가 사용되는 context를 이용해서 람다의 형식(type)을 추론할 수 있다. 어떤 context에서 기대되는 람다 표현식의 형식을 대상 형식(target type)이라고 부른다. 타입 검사 과정 다음 예시를 통해 타입 검사 과정을 확인해보자. filter(inventory, (Apple apple) -> apple.getWeight() > 150); filter 메서드의 선언을 확인한다. filter 메서드는 두 번째 파라미터로 Predicate 형식(target type)을 기대한다. Predicate은 test라는 한 개의 추상 메서드를 정의하는 함수형 인터페이스이다. test 메서드는 Apple을 받아 boolean을 반환하는 함수 디스크립터를 묘사한다. filter 메서드로 전달..
[Algorithm] 보이어-무어 알고리즘(Boyer-Moore Algorithm)
[Algorithm] 보이어-무어 알고리즘(Boyer-Moore Algorithm)
2023.04.04보이어-무어 알고리즘(Boyer-Moore Algorithm) 보이어-무어 알고리즘은 문자열 검색에 사용되는 알고리즘이다. 보이어-무어 알고리즘은 일반적인 상황에서 문자열은 앞부분보다 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용한다. 때문에 오른쪽 끝부터 비교하게 된다. 보이어 무어 알고리즘은 다음과 같이 이동할 칸의 개수를 저장해 놓은 테이블을 미리 만들어 저장해 놓는다. 오른쪽 끝과 일치하지 않는 경우 오른쪽 끝 문자가 일치하지 않는다면, 패턴에 해당 문자가 존재하는지 검사한다. 만약 패턴에 존재하지 않는다면, 패턴의 길이만큼 패턴을 이동시킨다. 만약 패턴에 존재한다면, 패턴의 오른쪽 끝에서부터 그 문자까지의 칸 수를 세서, 해당 칸수만큼 이동시킨다. 오른쪽 끝과 일치하는 경우 오른쪽 끝 문..
[Network] IP 주소
[Network] IP 주소
2023.04.04IP? IP는 인터넷 프로토콜(Internet Protocol)의 약자로, 인터넷이 통하는 네트워크에서 어떤 정보를 수신하고 송신하는 통신에 대한 규약을 의미한다. IP는 OSI 7 Layer에서 3계층에 해당하는 프로토콜이다. 즉, 호스트에서 호스트까지의 통신을 책임진다. IP 주소 IP 주소는 IP 통신에 필요한 고유 주소를 말한다. 현재 IPv4와 IPv6 두 가지 체계가 있으며, 우리가 흔히 쓰고 있는 IP 주소는 대부분 IPv4이다. IPv4 32비트의 값을 가지며, 보통 8비트씩 끊어 이를 0과 255 사이의 10진수 숫자로 표현한다. 각 비트 사이에는 점(.)을 찍어 구분한다. 총 32비트의 정보를 가지므로 최대 2^32개, 약 43억개의 고유한 주소를 부여할 수 있다. Class IPv4 ..
[JPA] N+1 문제
[JPA] N+1 문제
2023.04.03N+1 문제? N+1 문제란 연관 관계가 설정된 엔티티를 조회할 경우에 조회된 데이터 개수(n) 만큼 연관관계의 조회 쿼리가 추가로 발생하는 현상을 말한다. 예를 들어, Member와 여러 Member를 가지는 MemberGroup의 관계가 있다고 하자. Member와 MemberGroup Entity는 다음과 같이 구성되어 있다. @Getter @Entity @NoArgsConstructor(access = AccessLevel.PROTECTED) public class Member { @Id @GeneratedValue(strategy = GenerationType.IDENTITY) private Long id; private String name; @ManyToOne @JoinColumn(name ..
[Java] 함수형 인터페이스
[Java] 함수형 인터페이스
2023.04.03함수형 인터페이스? 함수형 인터페이스는 오직 하나의 추상 메서드를 가지고 있는 인터페이스이다. 함수 디스크립터 함수형 인터페이스의 추상 메서드는 람다 표현식의 시그니처를 묘사한다. 함수형 인터페이스의 추상 메서드 시그니처를 함수 디스크립터라고 한다. 다양한 람다 표현식을 사용하려면 공통의 함수 디스크립터를 기술하는 함수형 인터페이스 집합이 필요하다. 자바 API는 Comparable, Runnable, Callable 등의 다양한 함수형 인터페이스를 포함하고 있다. 여기서 Java 8 라이브러리는 java.util.function 패키지에서 새로운 함수형 인터페이스를 제공하는데, 그 중에서 Predicate, Consumer, Function 인터페이스를 살펴보자. Predicate java.util.f..
[Java] 람다 표현식 소개
[Java] 람다 표현식 소개
2023.03.31람다 표현식? 람다 표현식은 메서드로 전달할 수 있는 익명 함수를 단순화한 것이다. 람다 표현식에는 이름은 없지만, 파라미터 리스트, 바디, 반환 형식, 발생할 수 있는 예외 리스트는 가질 수 있다. 특징 익명: 보통의 메서드와 달리 이름이 없으므로 익명이라 표현한다. 함수: 람다는 메서드처럼 특정 클래스에 종속되지 않으므로 함수라고 부른다. 전달: 람다 표현식을메서드 인수로 전달하거나 변수로 저장할 수 있다. 간결성: 익명 클래스처럼 많은 자질구레한 코드를 구현할 필요가 없다. 람다 표현식을 이용하면 동적 파라미터 형식의 코드를 더 쉽게 구현할 수 있다. 예를 들어, Comparator 객체를 기존보다 간단하게 구현할 수 있다. [기존] Comparator byWeight = new Comparator..
[Baekjoon] 11401: 이항 계수 3
[Baekjoon] 11401: 이항 계수 3
2023.03.30문제 간단히 이항계수 (n k)를 구하는 문제이다. 풀이 대표 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Q11401 { public static final int MOD = 1000000007; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nk = br.readLine().split(" "); int n = Integer.parseInt(nk[0..