'전체 글'에 해당되는 글 103건

최근 AWS에 대해서 공부 중이며 내가 공부한 여러가지 디자인 패턴에 대해서 작성할려고 한다.

이번 글에서는 사용자 수가 많지 않고 짧은 기간만 서비스하는 이벤트 사이트 패턴에 대해서 써 보겠다.

이벤트 사이트는 일반 소비자를 대상으로 일시적으로 운용할 소규모 웹 서버를 설계하는 걸 목표로 한다.

이벤트 사이트(소규모 웹 서버) 개요 :

1. 1개월 한정으로 이용한다.
2. 사이트의 사용자는 개인 사용자로서 인터넷으로 접속한다.
3. 접속자 수는 많지 않아 고사양 서버는 필요 없다.
4. 웹 서버로 LAMP(Linux, Apache, PHP, MySQL) 환경을 사용한다. (다른 환경도 가능하다.)
5. 비용을 우선하며 다중화나 백업은 고려하지 않는다. (일회성)

인프라 핵심 :

1. 리전 선택 : 이벤트 사이트를 구동시킬 최적의 리전을 선택한다.
2. EC2 인스턴스 설정 : 소규모 웹서버에 맞는 EC2 인스턴스를 설정한다.
3. 도메인을 통한 접속 : 고정 IP 주소로 접속한다. (CNAME을 설정해 도메인 이름으로도 가능하게 한다.)
4. 네트워크 구성 : 인터넷 접속을 위한 간단한 네트워크 구성을 설정한다.
5. OS 환경 설정 :  아마존 리눅스에서 LAMP 환경을 설정한다.

이벤트 사이트 구성도

서버를 구성하는 가장 기본적인 서비스는 가상 서버인 EC2(Amazon Elastic Computer Cloud)와 가상 스토리지 볼륨인 EBS(Amazon Elastic Block Store)로 구성한다.

네트워크에 필요한 서비스는 VPC(Virtual Private Cloud)와 같은 기본 서비스에 포함되어 있다. 예시로 VPC의 내부에 가상 라우터를 설치할 수 있고, Route53(Amazon Route 53)을 사용하면 도메인(호스트명)으로 DNS 기능도 제공할 수 있다.

리전 선택 및 네트워크 구성

- 리전에 따른 응답 속도와 비용차이

서비스 구축 시 가장 먼저 해야 하는 것은 바로 서버가 위치할 리전을 선택하는 것이다.

응답 속도는 AWS 데이터 센터와 일반 사용자가 지리적으로 가까울수록 빠르며 멀수록 느려진다.

국내에 거주하는 사용자를 대상으로 하는 이벤트 사이트의 경우 응답 속도를 빠르게 하고 싶다면 서울 리전을 선택하면 된다.

비용은 리전에 따라 다르게 책정된다. 예시로 EC2 타입 중 하나인 t2.micro의 경우

서울 리전의 온디맨드 비용이 시간당 0.0162 달러, 미국 서부 리전은 0.0156 달러로 차이가 나며 데이터 전송 요금도 차이가 난다.

응답 속도보다 비용이 중요하다면 더욱 싼 리전을 찾아보면 된다.

서비스를 시작하고 나면 리전 변경에 손이 많이 가기 때문에 신중해야한다.

- 네트워크 구성 

리전을 정했으면 VPC와 서브넷을 구성하는 가상 네트워크를 작성한다.

VPC는 논리적으로 격리된 사용자 전용 네트워크 구역을 의미한다. 복수의 가용 영역(AZ, Availability Zones)에 걸친 형태로 VPC 하나를 작성할 수 있다.

하지만 복수의 리전에 걸쳐서 작성할 수 없으니 주의한다.

 서브넷은 VPC를 논리적으로 분리한 서브네트워크로 AWS 환경 내의 네트워크 최소 단위이다.

서브넷은 단일 AZ 안에서만 작성된다. 

서브넷을 나누는 방법은 온프레미스 환경과 다른게 거의 없다. 논리적인 네트워크를 설게해서 AWS의 서브넷 구성에 대입시키면 된다. 예를 들어 인터넷으로 HTTP 수신이 가능한 웹 서버와, 웹 서버로부터 데이터베이스 접속만 허가하는 데이터베이스 서버는 필터링 정책이 다르기 때문에 서브넷을 분리해야 한다.

EC2 인스턴스 작성하기

VPC와 서브넷 설정을 완료하고 나서 이벤트 사이트의 웹 서버가 되는 EC2 인스턴스를 작성해야한다.

LAMP로 구성하기로 했으니 EC2 이미지중 Amazon Linux  AMI를 사용한다. 가상화 타입으로는 완전가상화인 HVM과 반가상화인 PV가 있는데, 보통은 HVM을 선택한다. (HVM 성능이 더 좋다)

인스턴스 유형은 서버 규모에 해당하며, CPU, 메모리, 스토리지, 네트워크 성능의 조합을 할 수 있다. 

하지만 메모리만 늘린다든지 세세한 사용자 정의는 할 수 없다.

그러므로 목적에 가장 가까운 인스턴스 유형을 선택해야 하는데, 작은 LAMP 환경이라면 OS에 약 1GB, MySQL 등의 미들웨어에 1GB정도만 있으면 된다.

네트워크 및 셧다운 동작 설정 주의 사항

인스턴스 유형을 정했다면 다음은 EC2 인스턴스 설정을 해야한다.

주요 포인트만 몇가지 적겠다.

네트워크는 VPC를 선택한다. (기본으로 설정된다)

퍼블릭 IP 주소를 자동할당은 비활성화 해준다. 활성화하면 동적 퍼블릭 IP 주소가 부여되면 EC2 인스턴스가 다시 시작할 때마다 자동으로 변경됨으로 IP주소나 DNS를 다시 지정해주어야만 한다. 

EC2 인스턴스를 정지하는 경우의 종료동작 설정도 해줘야한다. 셧다운 동작에는 중지(Stop)와 종료(Terminate)가 있다.

중지를 선택하면, 셧다운 시에 OS가 정지되며 OS 이미지가 보존되고 재시작하면 같은 상태로 시작한다.

종료를 선택하면 OS 정지와 동시에 EC2 인스턴스가 삭제된다. 고급설정에 종료동작을 설정할 수 있으니 확인해 준다.

 보안그룹 설정

EC2 설정의 마지막 단계는 보안 그룹 설정이다.

보안 그룹은 OS레벨에서 네트워크 통신 필터링 룰을 정하는 것으로 허가할 프로토콜을 설정한다.

보안그룹 Source의 초기 설정 값이 Anywhere(0.0.0.0/0) 되어 있는데. 이는 모든 IP 주소로부터의 SSH 접속을 허가한다는 의미이다. SSH의 Source값을 집 또는 회사의 퍼블릭 IP 로 설정한다.

이벤트 사이트의 웹 서버는 사용자로부터 HTTP/HTTPS 접속을 허가할 필요가 있다.

이때는 어떤 IP에서든 접속 할 수 있게 0.0.0.0/0으로 설정한다. 

고정 IP와 호스트명 설정

EC2 인스턴스를 생성했지만, 아직은 인터넷으로 EC2에 접속할 수 없다.

인터넷으로 접속하려면 고정된 퍼블릭 IP주소와 FQDN(호스트명)이 있어야 한다.

고정 퍼블릭 IP 주소를 AWS에서는 EIP(Elastic IP)라고 부른다.

EIP를 포함한 서비스 설정 변경과 추가는 매니지먼트 콘솔에서 한다. EIP 설정은 콘솔을 통해 EC2 서비스로 들어가 '네트워크 및 보안 > 탄력적 IP > 탄력적 IP 주소 할당' 을 클릭하여 설정한다.

자세한건 아래의 블로그를 참조하면 되겠다.

https://any-ting.tistory.com/71

고정 IP를 할당 받았다면 도메인을 설정할 차례이다.

AWS는 Route53이라는 DNS 서비스를 제공한다. 

도메인 취득 방법은 아래의 블로그를 참조하면 된다.

https://any-ting.tistory.com/84

이후 Route53과 EC2 연결은 아래의 블로그 글을 참고하면 된다.

https://dogfoottech.tistory.com/257

VPC 설정으로 인터넷 접속 설정

인터넷에 접속하려면 한가지 더 설정을 해야한다. AWS에서는 VPC 이용이 필수이다.

VPC는 AWS 데이터 센터 내부에 마련된 가상의 폐쇄 네트워크이며 외부와 통신할 수 있도록 설정해야 한다.

이벤트 사이트는 기본 설정에서 두 군데만 수정하면 된다.

첫 번째는 VPC와 DNS 관련 설정이다. VPC 설정 화면에서 DNS 관련 설정을 켜준다.

두 번쨰는 라우팅 설정이다. 라우팅 테이블에 인터넷 게이트웨이가 설정되어 있지 않으면 인터넷 접속이 불가능하다. VPC 설정화면에서 라우팅 테이블에서 0.0.0.0/0과 igw로 시작하는 인터넷 게이트가 없다면 생성해준다.

이 블로그 글을 보면 도움이 될 것이다.

https://velog.io/@chchaeun/AWS-%ED%81%B4%EB%9D%BC%EC%9A%B0%EB%93%9C-%EA%B5%AC%EC%B6%95-2-VPC-%EA%B5%AC%EC%B6%95%EC%84%9C%EB%B8%8C%EB%84%B7-%EB%9D%BC%EC%9A%B0%ED%8C%85-%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9D%B8%ED%84%B0%EB%84%B7-%EA%B2%8C%EC%9D%B4%ED%8A%B8%EC%9B%A8%EC%9D%B4

OS 환경 설정

이 블로그 글을 참고하면 될거 같다.

https://strong-ming.tistory.com/3

마지막으로 이벤트 사이트의 사용기간이 끝났으면

EC2 인스턴스를 종료하여 삭제처리 해주어야 추가 비용이 청구되지 않는다.

EIP는 EC2와 연결되어 있을 때만 과금이 된다.

Route 53dms 존 단위로 월정액이 과금되니 사용하지 않는다면 삭제할 필요가 있다.

VPC는 유지 자체는 비용이 들지 않으니 제거할 필요 없다.

문제 : 

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:

Input: digits = ""
Output: []
Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints (제한조건) :
0 <= digits.length <= 4
digits [i] is a digit in the range ['2', '9'].

2-9까지 숫자의 조합이 주어졌을 때, 해당 숫자가 나타낼 수 있는 알파벳의 모든 조합을 구하는 문제이다.

처음부터 자료구조를 HashMap을 사용하기로 생각을 했으나, 어떻게 해야 주어진 문자열 digits.lentgh에 맞춰 반복문을 쓸까 고민을 했다.

그러다가 문득 모든 가능한 경우의 수를 탐색하면서 조건을 만족하는 해를 찾는  백트랙킹(backtracking) 알고리즘이 생각이 났다.

구현 방법이 내가 기억하는 게 맞다면 이런 식으로 구현이 되는데

for(선택지)
 상태 변경
 재귀호출(변경된 상태)
 상태 복귀

긴가민가하여 조금 헤맸다.

우선 내 풀이는 이렇다.

주어진 메인메서드의 리턴값이 List <String>이니 

결과를 리턴해줄 리스트 result를 선언해 준다.

그리고 digitis이 공백일 경우 result를 바로 리턴해 준다.

List<String> result = new ArrayList<>();

if(digits == null || digits.length()==0){
    return result;
}

이후 각 숫자들이 나타낼 수 있는 알파벳 조합을 저장하기 위해 Map <Character, String>을 생성해 주었다.

Map의 Key타입을 Character로 지정해 준 이유는 digits문자열을 문자 배열(char)로 전환하여 비교할 예정이기 때문이다. 

        Map<Character, String> map = new HashMap<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");

마지막으로 백트랙킹을 만들어 주겠다.

매개변수로는

1. 문자열 digits,

2. 몇 번째 조합인지 체크하는 인덱스 index,

3. 조합을 저장할 StringBuilder,

4. 최종 조합을 저장할 리스트 result,

5. 그리고 각 숫자의 알파벳을 가지고 있는 map이다.

주어진 문자열 digits이 "23"일 경우 나올 수 있는 알파벳 조합의  digits의 길이와 동일한 2이다.

예)

'2' = "abc"

'3' = "def"

2와 3의 모든 조합 :ad, ae, af, bd, be, bf, cd, ce, cf

백트래킹을 재귀적으로 호출하여 탐색할 때, 최대 탐색할 수 있는 깊이를 지정하지 않으면 StackOverFlow가 발생한다.

몇 번째 조합인지 체크(깊이 체크)하는 index가 digits의 길이와 같을 경우 return 하도록 해줬다.

그리고 return 할 때, Stringbuilder는 모든 조합을 탐색한 상태이기 때문에 result에 더 해주도록 한다.

digits가 "23"일 때 아래의 코드는 다음과 같이 작동한다.

    public void backTrack(String digits, int index, StringBuilder comb, 
                          List<String> result, Map<Character, String> map){

        if(index == digits.length()){ // 인덱스의 값이 digits의 길이와 같으면
            result.add(comb.toString()); // 끝까지 탐색한 것이므로 result에 더해주고
            return; // return한다.
        }

        String letters = map.get(digits.charAt(index)); // map에 저장된 각 숫자의 알파벳을 저장
		
        // letters에 있는 문자를 하나씩 꺼내온다.
        for(char letter : letters.toCharArray()){
            comb.append(letter); // 꺼내온 문자를 StringBuilder comb에 저장하고
            backTrack(digits, index+1, comb, result, map); // 재귀적으로 조합 탐색
            comb.deleteCharAt(comb.length()-1); // 재귀호출이 끝나면 stringBuilder를 비워준다.
        }
    }

1. backTrack  첫 호출

String letters = map.get(digits.charAt(index));

-> letters = map.get(digits.charAt(0));  

map에서 '2'의 값 "abc"를  가져와  letters에 저장한다.

for(char letter : letters.toCharArray()) { // 문자열 letters를 문자배열 {'a', 'b', 'c'}로 전환하여 하나씩 꺼내온다.

comb.append(letter); // 우선 a를 StringBuilder comb에 입력하고

backTrack(digits, index+1, comb, result, map);  // 재귀 호출 

-> backTrack("23", 0+1, comb, result, map);  // backTrack에 a 다음에 올 문자 조합을 찾는다.

2. backTrack 두 번째 호출

if(index == digits.length()) // index의 크기가 digits의 길이와 동일하지 않으니 넘어간다.

String letters = map.get(digits.charAt(index));

-> letters = map.get(digits.charAt(1));  

map에서 '3'의 값 "def"를  가져와  letters에 저장한다.

for(char letter : letters.toCharArray()) { // 문자열 letters를 문자배열 {'d', 'e', 'f'}로 전환하여 하나씩 꺼내온다.

comb.append(letter); // comb에 들어있던 a와  d를 더하여 ad를 만든다.

backTrack(digits, index+1, comb, result, map);  // 재귀 호출 

-> backTrack("23", 1+1, comb, result, map);  // backTrack에 ad 다음에 올 문자 조합을 찾는다.

3. backTrack 세 번째 호출

if(index == digits.length()) //  2==2로 index의 크기가 digits의 길이와 동일하니 

result.add(comb.toString()); // 끝까지 탐색한 것이므로 result에 comb에 저장된 문자열 ab를 넣어주고
 return;                                    // return 한다.

4. backTrack 두 번째 호출로 복귀

위와 같이 반복하여 a의 모든 결과를 탐색하여 첫 번째 backTrack으로 돌아오면 

comb에 들어가 있던 a를 comb.deleteCharAt(comb.length()-1)를 통해 최종적으로 제거해 주고 

b와 c의 조합도 탐색하고 종료한다.

전체 코드는 다음과 같다. 

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        if(digits == null || digits.length()==0){
            return result;
        }

        Map<Character, String> map = new HashMap<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");

        backTrack(digits, 0, new StringBuilder(), result, map);

        return result;
    }

    public void backTrack(String digits, int index, StringBuilder comb, List<String> result, Map<Character, String> map){

        if(index == digits.length()){
            result.add(comb.toString());
            return;
        }

        String letters = map.get(digits.charAt(index));

        for(char letter : letters.toCharArray()){
            comb.append(letter);
            backTrack(digits, index+1, comb, result, map);
            comb.deleteCharAt(comb.length()-1);
        }
    }
}

개인 공부겸 알고리즘들에 대허 정리를 하기로 했다.

먼저 이번편에서는 탐색 알고리즘 중 선형 탐색(Linear Search)과 이진 탐색(Binary Search) 대해 적어보겠다.

추가로 투포인터 탐색(Two pointer)에 대해서도 적어 보겠다.

1. 선형 탐색 (Linear Search)

✓  개념

• 정렬 여부와 상관없이 리스트(배열, 컬렉션 등)의 처음부터 끝까지 차례로 비교하여 원하는 값을 찾는 가장 기본적인 탐색 방법이다.
• 배열이나 리스트의 요소를 하나하나 순차적으로 확인하면서 조건에 맞는 값을 찾는다.

⏱️ 시간 복잡도 (Time Complexity)

• 최악의 경우 (Worst case): O(n) → 마지막 요소까지 전부 확인해야 할 때
• 최선의 경우 (Best case): O(1) → 첫 번째 요소가 정답일 때
• 평균적인 경우 (Average case): O(n) 
• 중첩하여 사용할 시: O(n^x)  →  x는 for문이나 while문의 중첩 개수

💾 공간 복잡도 (Space Complexity)

• O(1) → 추가 메모리를 거의 사용하지 않음

 장점

• 간단하고 구현이 쉬움
• 정렬이 필요 없음
• 모든 자료구조에 적용 가능 (배열, 리스트 등)

 단점

• 데이터가 많아질수록 속도가 느려짐
• 탐색 효율이 낮음 (특히 대규모 데이터에서 비효율적)

Java에서의 구현 방식

배열에서 선형 탐색

public class LinearSearchExample {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;  // target 찾으면 인덱스 반환
            }
        }
        return -1;  // 없으면 -1
    }

    public static void main(String[] args) {
        int[] numbers = {5, 3, 8, 4, 2};
        int target = 4;
        int result = linearSearch(numbers, target);
        System.out.println("Index: " + result);  // 출력: Index: 3
    }
}

리스트에서 선형 탐색

import java.util.List;
import java.util.Arrays;

public class LinearSearchList {
    public static int linearSearch(List<Integer> list, int target) {
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(10, 20, 30, 40);
        System.out.println("Index: " + linearSearch(list, 30));  // 출력: Index: 2
    }
}

2. 이진 탐색 (Binary Search)

✓ 개념

• 정렬된 데이터에서만 사용 가능.
• 중앙값을 기준으로 탐색 범위를 절반으로 계속 줄여가며 찾는 방식.
• 비교할 때마다 탐색 범위를 절반씩 줄이므로 매우 빠름.

⏱️ 시간 복잡도 (Time Complexity)

n개의 요소가 있다면 최대 log₂(n)번만 비교하면 됩니다.

💾 공간 복잡도 (Space Complexity)

• 반복문 구현: O(1)
• 재귀 구현: O(log n) → 재귀 호출이 스택에 쌓이기 때문

장점

• 탐색 속도가 빠름 → 큰 데이터에서도 효율적
• 시간 복잡도 O(log n)으로 성능 우수

단점

• 데이터가 정렬되어 있어야만 사용 가능
• 삽입/삭제가 잦은 경우 정렬 유지가 번거로움
• 구현이 선형 탐색보다 약간 복잡

Java에서의 구현

반복문(while) 

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;  // 오른쪽 절반으로 이동
            } else {
                right = mid - 1; // 왼쪽 절반으로 이동
            }
        }

        return -1;  // 찾지 못했을 때
    }

    public static void main(String[] args) {
        int[] nums = {2, 4, 7, 10, 23, 38, 45};
        int index = binarySearch(nums, 10);
        System.out.println("Index: " + index);  // 출력: Index: 3
    }
}

재귀 방식

public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
    if (left > right) return -1;

    int mid = (left + right) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target)
        return binarySearchRecursive(arr, target, mid + 1, right);
    else
        return binarySearchRecursive(arr, target, left, mid - 1);
}

자바에서 제공하는 기본 메서드 활용

Arrays.binarySearch()를 사용하면 손쉽게 이진 탐색을 할 수 있다.

import java.util.Arrays;

int[] arr = {3, 6, 8, 10, 15};
int idx = Arrays.binarySearch(arr, 10);  // 정렬된 상태여야 함!
System.out.println(idx);  // 출력: 3

이진 탐색과 투포인터 탐색의 차이점

구현된 모습을 보면 이진 탐색과 투포인터가 비슷해 보인다.

하지만 이 둘은 별개의 탐색 알고리즘이다.

3. 투 포인터 알고리즘 (Two Pointer)

✓  개념

• 배열이나 리스트에서 두 개의 포인터를 사용해 효율적으로 문제를 해결하는 방식.
• 주로 정렬된 배열에서 사용되며, 포인터를 양 끝이나 한쪽에서 시작해 조건에 맞게 이동한다.

⏱️ 시간 복잡도

• 시간 복잡도: O(n)
  두 포인터가 각각 한 번씩만 이동하므로 전체 배열을 한 번만 훑는다.
• 공간 복잡도: O(1)
  포인터 변수만 쓰기 때문에 추가 공간이 거의 필요 없다.

장점

• 속도가 빠름 (O(n))
• 코드가 간결함
• 정렬된 배열에서 문제를 더 효과적으로 해결 가능
• 다양한 문제에 응용 가능: 부분합, 두 수의 합, 슬라이딩 윈도우 등

단점

• 정렬된 배열/리스트에서만 유용한 경우가 많음
• 문제의 조건에 따라 포인터 이동 방향을 잘 설계해야 함
• 투 포인터 적용이 직관적이지 않은 경우도 있음

Java에서의 구현

예제 1️⃣: 두 수의 합 (Two Sum) – 정렬된 배열에서 O(n)

public boolean hasTwoSum(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return true;
        else if (sum < target) left++;
        else right--;
    }

    return false;
}

예제 2️⃣: 가장 긴 부분 배열의 합 ≤ target

public int maxSubarrayLength(int[] arr, int target) {
    int left = 0, sum = 0, maxLen = 0;

    for (int right = 0; right < arr.length; right++) {
        sum += arr[right];

        while (sum > target) {
            sum -= arr[left++];
        }

        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

예제 3️⃣: 중복 없는 최장 부분 문자열 (문자열 버전)

public int lengthOfLongestSubstring(String s) {
    int left = 0, maxLen = 0;
    Set<Character> set = new HashSet<>();

    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left++));
        }
        set.add(s.charAt(right));
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

투 포인터의 대표적인 활용 분야

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:

Input: s = "cbbd"
Output: "bb"
 

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

문제 : 

문자열 s 가 주어졌을때, 문자열 안에서 가장 긴 팰린드롬을 substring하여 리턴하는 문제이다.

이 문제를 해결하기 위해 브루트포스를 이용하여 푸는것도 가능하지만 이번에는 동적 프로그래밍(DP)를 이용해 보기로 헀다.

풀이 :

1. 우선 문자열 s의 길이가 0일 경우 팰린드롬이

아니고 1이면 자동적으로 팰린드롬이 완성이 된다. 

예) s = "a"; 

문자열이 한글자일 경우 좌에서 보나 우에서 보나 일치하기에 팰린드롬이다.  

    int n = s.length(); // s의 길이 저장
    if(n<=1){ // 0 혹은 1이면 s 반환
        return s;
    }

2. 가장 긴 팰린드롬을 s에서 추출(substring)해야 하기에 

최대 길이를 저장할 maxLen와 

substring을 위한 인덱스 start, end를 선언했다.

이미 문자열 길이가 1이하인 경우는 제외시켰기에 최대 길이는 1부터 시작하므로 maxLen=1로 초기화 하였다.

     int maxLen = 1; // 최대 길이 저장
     int start =0;   // s.substring(start,  시작 인덱스
     int end = 0;    // end);               끝 인덱스

이제 마지막으로 동적 프로그래밍에 사용할 배열을 선언한다.

boolean[][] dp = new boolean[n][n];

3. 배열을 boolean으로 선언한 이유는 문자열 s에서 발생할 수 있는 모든 경우의 수 중에서 팰린드롬인 경우를 표기하기 위함이다.

배열이 n * n (문자열 길이 * 문자열 길이)인 이유는 다음과 같다.

만약 주어진 문자열이 "babad"일 때 2차원 배열 dp에서 표기할 수 있는 문자열 s의 조합이다.

  j →   0   1   2   3   4
     ---------------------
i=0 |   b   a   b   a   d
i=1 |       a   b   a   d
i=2 |           b   a   d
i=3 |               a   d
i=4 |                   d

4. 이제 문자열 s의 모든 조합을 확인하기 위하여 for문을 사용해 문자열을 탐색하겠다.

     for(int i=0; i<n;i++){ // 첫번째 for 문
     	dp[i][i] = true; // 인덱스의 위치가 같은 곳을 true로
        for(int j=0;j<i;j++){ // 두번재 for 문
        }
     }

i==j 일때 팰린드롬이 형성됨으로 dp 배열에서 dp[i][i] 을 true로 만들어준다.

예) 

i =0, j =0    // 비교하는 두 인덱스의 요소의 위치가 같을 때

s[0] == s[0]   // badad의 0번 인덱스는 b==b 이다.

dp[0][0]       // 고로 i==j 는 i==i와 같고 dp[i][i]는 팰린드롬이므로 전부 true

  j →   0   1   2   3   4
     ---------------------
i=0 |   b  
i=1 |       a  
i=2 |           b   
i=3 |               a   
i=4 |                   d


  j →   0   1   2   3   4
     ---------------------
i=0 |   T  
i=1 |       T  
i=2 |           T   
i=3 |               T   
i=4 |                   T

밑준비는 끝났으니 이제 팰린드롬인지 판단하는 조건을 쓰겠다.

조건은 다음과 같다 :

 if(s.charAt(i)==s.charAt(j) && (i-j<=2 || dp[j+1][i-1])){

• s[j] == s[i]: 양 끝 문자가 같고
• i - j <= 2: 길이가 3이하인 경우는 바로 확인 가능  (i = 2; j= 0 일때 배열에선 0,1,2 니까 길이가 3이다. 예 bab)
• 그 외는 내부 문자열 dp[j+1][i-1]이 팰린드롬인지 확인

1. s.charAt(j) == s.charAt(i)

→ 먼저 양 끝 문자가 같아야 팰린드롬일 가능성이 생긴다.
예: "a**bab**a"에서 양쪽 a가 같아야 팰린드롬일 가능성이 있다..

2. dp[j + 1][i - 1] == true

→ 가운데 문자열 s[j+1..i-1]이 이미 팰린드롬이어야 전체도 팰린드롬이다.

예를 들어:

 j가 0, i= 4

• 전체 문자열: s[0..4] = "ababa"
• 양끝 같음: s[0] == s[4] == 'a'
• 중간 부분: s[1..3] = "bab" → 이게 팰린드롬이어야 "ababa"도 팰린드롬

조금 이해가 안간다면 이렇게 설명할 수 있다. 

i = 1

• j = 0 → s[0]="b", s[1]="a" → 다름 → dp[0][1]=false

i = 2

• j = 0 → s[0]="b", s[2]="b", 길이=3 → 가운데 "a"는 팰린드롬 (dp[1][1]=true) → dp[0][2] = true
• j = 1 → s[1]="a", s[2]="b" → 다름 → dp[1][2] = false

➡ "bab" 팰린드롬 발견!

i = 3

• j = 0 → s[0]="b", s[3]="a" → 다름
• j = 1 → s[1]="a", s[3]="a", 길이=3 → 가운데 "b"는 팰린드롬 (dp[2][2]=true) → dp[1][3]=true
• j = 2 → s[2]="b", s[3]="a" → 다름

➡ "aba" 팰린드롬 발견 (같은 길이)

i = 4

• j = 0~3 → 모두 양 끝 문자 다름 → dp[j][4] = false 전부

팰린드롬일 가능성이 있는 인덱스들을 찾았다면 이어서 그것을 dp에 체크한다.

그리고 두 인덱스 사이의 길이가 maxLen보다 클 경우 maxLen를 갱신하고

start와 end 좌표도 갱신한다.

dp[j][i] = true;
if(i-j+1>maxLen){
    maxLen = i-j+1;
    start = j;
    end = i;
}

완성된 for문은 다음과 같다.

     for(int i=0; i<n;i++){
        dp[i][i] = true;
        for(int j=0;j<i;j++){
            if(s.charAt(i)==s.charAt(j) && (i-j<=2 || dp[j+1][i-1])){
                dp[j][i] = true;
                if(i-j+1>maxLen){
                    maxLen = i-j+1;
                    start = j;
                    end = i;
                }
            }
        }
     }

모든 순회를 끝나면 DP는 이렇게 생긴다.

  j →   0   1   2   3   4
     ---------------------
i=0 |   T   F   T   F   F  = bab
i=1 |       T   F   T   F  = aba
i=2 |           T   F   F
i=3 |               T   F
i=4 |                   F



  j →   0   1   2   3   4
     ---------------------
i=0 |   b   a   b   a   d 
i=1 |       a   b   a   d
i=2 |           b   a   d
i=3 |               a   d
i=4 |                   d

이제 마지막으로 구한 두  인덱스를 사용하여 문자열 s 안의 가장 긴 팰린드롬을 리턴하면 끝이다.

class Solution {
    public String longestPalindrome(String s) {
     int n = s.length();
    if(n<=1){
        return s;
    }
     int maxLen = 1;
     int start =0;
     int end = 0;

     boolean[][] dp = new boolean[n][n];

     for(int i=0; i<n;i++){
        dp[i][i] = true;
        for(int j=0;j<i;j++){
            if(s.charAt(i)==s.charAt(j) && (i-j<=2 || dp[j+1][i-1])){
                dp[j][i] = true;
                if(i-j+1>maxLen){
                    maxLen = i-j+1;
                    start = j;
                    end = i;
                }
            }
        }
     } 

     return s.substring(start,end+1); 
    }
}

자바 공부를 하다가 보면 가끔 이런 식으로 쓰인 부분들이 있다.

List<String> filtered = stream
    .filter(name -> name.startsWith("A")) // 여기같이 표현
    .map(String::toUpperCase)  // 이거는 '메서드 참조'이다

name -> name.startsWith("A")
이게 뭐지?

이건 람다식 혹은 람다라고 하는 코드 작성법이다.

자바의 람다식(lambda expression)은 익명 함수(이름이 없는 함수)를 간결하게 표현하는 방식으로, 주로 함수형 인터페이스를 구현할 때 사용된다. Java 8부터 도입되었으며, 코드의 가독성을 높이고 간결하게 작성할 수 있는 장점이 있다.

기본 문법은 다음과 같다 :

(매개변수) -> { 실행문 }


// 매개변수 하나, 실행문 하나
x -> System.out.println(x)

// 매개변수 여러 개, 반환값 있는 경우
(x, y) -> x + y

// 실행문 여러 줄
(x, y) -> {
    int result = x + y;
    return result;
}

실제로도 보면 작성도 쉽고 읽기도 쉽다.

장점과 단점에 대해 좀 더 자세하게 알아보자.

람다식의 장점

1. 코드가 간결해짐

• 익명 클래스보다 훨씬 짧고 읽기 쉬움.

// 전통적인 방식
Runnable r1 = new Runnable() {
    public void run() {
        System.out.println("Hello!");
    }
};

// 람다식
Runnable r2 = () -> System.out.println("Hello!");

2. 가독성이 좋아짐

• 함수의 목적이 명확하고, 코드 흐름이 더 직관적.
• 특히 Stream API와 함께 쓰면 굉장히 깔끔한 코드가 가능.

List<String> list = Arrays.asList("Helldiver", "Stratagem", "Bug");
list.stream()
    .filter(s -> s.startsWith("H"))
    .forEach(System.out::println);

3. 병렬 처리 등 함수형 프로그래밍에 적합

• Stream API와 함께 사용하면 병렬 작업도 쉽게 적용할 수 있다.

list.parallelStream().forEach(System.out::println);

4. 콜백 구현이 쉬움

• 이벤트 처리, 비동기 작업 등에 콜백을 깔끔하게 구현 가능.

람다식의 단점

1. 복잡한 로직에는 부적합

• 여러 줄로 작성할 경우 오히려 가독성이 떨어짐.

(x, y) -> {
    if (x > y) return x;
    else return y;
}

복잡하면 그냥 일반 메서드나 익명 클래스로 하는 게 더 명확할 수도 있음.

2. 디버깅이 어려움

• 익명 함수이기 때문에 디버거에서 이름이 없어 추적하기 어려움.
• 예외 처리 위치도 찾기 힘들 수 있음.

3. 오용 시 가독성 하락

• 지나치게 중첩된 람다식은 오히려 코드 이해를 방해함.

list.stream()
.filter(x -> x.length() > 3)
.map(x -> x.toUpperCase())
.sorted((a, b) -> a.compareTo(b))
.forEach(System.out::println);
// 너무 길어지면 눈 아픔...

4. 익명 클래스와의 기능 차이

• 익명 클래스는 다중 메서드를 구현하거나 상태를 가질 수 있지만, 람다식은 그럴 수 없음

이런 람다식이지만 이걸 활용하기 위해서는 함수형 인터페이스를 써야한다는 전제가 있다.

함수형 인터페이스란?

• 자바에서 람다식은 익명 구현 객체를 생성하는 문법이다.
• 이때 어떤 인터페이스를 구현하는 객체가 생성되는데, 추상 메서드가 하나만 있어야 어떤 메서드를 구현할지 애매하지 않기 때문에 그 조건이 필요함.

@FunctionalInterface
interface MyFunction {
    void run();
}

@FunctionalInterface 어노테이션은 선택 사항이지만, 붙이면 컴파일러가 실수로 두 개 이상의 추상 메서드를 만들지 않도록 도와준다.

// 컴파일 에러 발생!
@FunctionalInterface
interface InvalidInterface {
    void method1();
    void method2(); // 에러!
}

1. 함수형 인터페이스의 특징

• 단 하나의 추상 메서드만 존재
• default, static 메서드는 여러 개 있어도 무관 (이것들은 추상 메서드가 아님)
• @FunctionalInterface는 선택이지만, 붙이는 걸 권장

2. 예시: 직접 만든 함수형 인터페이스와 람다식 사용

@FunctionalInterface
interface Calculator {
    int calculate(int a, int b);
}

public class Test {
    public static void main(String[] args) {
        Calculator add = (a, b) -> a + b;
        Calculator multiply = (a, b) -> a * b;

        System.out.println(add.calculate(3, 4));      // 7
        System.out.println(multiply.calculate(3, 4)); // 12
    }
}

3. 자바에서 제공하는 주요 함수형 인터페이스

Java 8부터 java.util.function 패키지에서 많이 제공하고, 이걸 기반으로 스트림 API, 람다식 등에서 사용함.

3-1. 예시:

1. Predicate<T>

• T를 받아 조건 검사 후 boolean 반환

import java.util.function.Predicate;

public class Main {
    public static void main(String[] args) {
        Predicate<Integer> isPositive = x -> x > 0;

        System.out.println(isPositive.test(10)); // true
        System.out.println(isPositive.test(-5)); // false
    }
}

2. Supplier <T> — "공급자"

• 아무것도 받지 않고, T를 리턴하는 함수형 인터페이스
• 메서드: T get()

import java.util.function.Supplier;

public class SupplierExample {
    public static void main(String[] args) {
        Supplier<String> stringSupplier = () -> "HELLDIVERS 2 - MISSION READY!";

        System.out.println(stringSupplier.get());
    }
}

3. Consumer <T> — "소비자"

• T를 받아서 소비만 하고, 리턴값은 없음
• 메서드: void accept(T t)

import java.util.function.Consumer;

public class ConsumerExample {
    public static void main(String[] args) {
        Consumer<String> printStratagem = stratagem -> System.out.println("Deploying: " + stratagem);

        printStratagem.accept("Eagle Airstrike");
    }
}

4. Function <T, R> — "변환자"

• T를 받아서 R로 변환
• 메서드: R apply(T t)

import java.util.function.Function;

public class FunctionExample {
    public static void main(String[] args) {
        Function<String, Integer> stringLength = str -> str.length();

        System.out.println("Length: " + stringLength.apply("Super Earth"));
    }
}

개인적으로 람다식을 잘 사용을 안 해서 아직도 어색하다. 

나중에 시간이 되면 람다식 연습도 해봐야겠다.

자바의 Stream API는 Java 8부터 도입된 기능으로, 컬렉션(Collection) 데이터를 처리할 때 선언형(Declarative) 방식으로 간결하고 효율적으로 작업할 수 있도록 도와주는 기능이다.

쉽게 말하면, 데이터를 필터링하고, 변형하고, 집계하는 일련의 작업을 파이프라인처럼 연결해서 처리할 수 있는 도구라고 보면 된다.

Stream API는 단독으로 뭔가 하는 게 아니라
"데이터 → Stream → 연산들"이라는 전체 흐름 속에서 사용된다는 점이 핵심이다.

1. Stream 만드는 방법 (데이터 → Stream)

Stream API를 쓰기 위해서는 반드시 "스트림 객체"를 만들어야 한다.
즉, Stream은 “데이터 소스”로부터 시작해서, 그 위에 중간 연산과 최종 연산을 쌓는 구조이다.

가장 많이 쓰는 순서부터 한 번 작성해 보겠다.

1. 컬렉션(Collection)으로부터

List<String> list = List.of("A", "B", "C");
Stream<String> stream = list.stream();

• .stream() → 순차 스트림
• .parallelStream() → 병렬 스트림 (멀티코어 처리)

list.stream()은  실제로 Stream<String> stream = list.stream(); 이렇게 변수에 담는 걸 생략한 것 뿐이다.

2. 배열로부터

String[] arr = {"A", "B", "C"};
Stream<String> stream = Arrays.stream(arr);

• Collections를 상속 받지 않은 Arrays(배열)은 Arrays.stream()을 이용하여 stream객체를 생성 가능하다.

3. Stream 클래스의 정적 메서드 사용

Stream<String> stream = Stream.of("A", "B", "C");

• .of() → 가변 인자를 스트림으로
• .generate(Supplier) → 무한 스트림 (ex: 랜덤값 반복 생성)
• .iterate(seed, UnaryOperator) → 무한 반복 스트림

예:

Stream<Integer> nums = Stream.iterate(1, n -> n + 1); // 1, 2, 3, ...

Stream<String> stream = Stream.of("a", "b", "c"); 

Stream<int[]> intArrayStream = Stream.of(new int[]{1, 2, 3});

4. 파일 등 외부 자원

Stream<String> lines = Files.lines(Paths.get("file.txt"));

5. Stream.builder() 을 활용하여 수동으로 만들 때

Stream.Builder<String> builder = Stream.builder();

builder.add("apple");
builder.add("banana");
builder.add("cherry");

Stream<String> stream = builder.build();

간단한 버전 :

Stream<String> stream = Stream.<String>builder()
    .add("apple")
    .add("banana")
    .add("cherry")
    .build();

주의할 점 :

• .build()를 호출한 후에는 .add()를 더 이상 사용할 수 없음 (불변 스트림 생성)
• 너무 많은 요소를 직접 add()로 넣는 건 귀찮음 → 이럴 땐 List.stream()이나 Stream.of()가 더 나음

Stream 만들기 요약 정리

Stream 객체를 만들었다면 이걸 활용해야 한다.

만들어지 Stream 객체를 사용하기 위해서는 2단계 과정을 더 거쳐야한다. 바로 중간 연산과 최종 연산이다.

1. 중간 연산 (Intermediate Operations)

스트림을 변형시키고 연결만 하고, 실제 실행은 최종 연산이 호출될 때까지 지연됨 (lazy evaluation).

2. 최종 연산 (Terminal Operations)

스트림 연산을 실행하고 결과를 반환함.
여기서 연산이 실제로 수행됨.

중간 연산의 경우 lazy하여 최종연산이 실행되기 전까지 아무 일도 일어나지 않는다. 

최종 연산은 한 번만 실행 가능하며, 중간 연산은 여러번 사용해도 된다.

3. 쉽게 기억하는 비유!

• Stream = 컨베이어 벨트
• 중간 연산 = 벨트 위에서 필터링, 변형, 정렬하는 장치들
• 최종 연산 = 완성품을 포장하거나 소비하는 마지막 과정
• 포장하고 나면, 벨트는 멈추고 재사용 불가

예시 :

List<String> names = List.of("Alice", "Bob", "Charlie", "David");

long count = names.stream()
    .filter(name -> name.length() > 3)  // 중간 연산
    .map(String::toUpperCase)          // 중간 연산
    .distinct()                        // 중간 연산
    .count();                          // 최종 연산

System.out.println(count); // 3

Stream API를 활용하려면 람다(Lambda)식도 알아야한다.

참 귀찮은 일이지만 다음 포스트에 한 번 람다식에 관해 써보겠다.