9x9 스도쿠 퍼즐이 주어졌을 때, 스도쿠 규칙에 맞게 수가 채워지도록 해야한다.

생각

판은 9x9 총 81칸 모든 빈칸이 0이라고 생각했을 때 1~9까지 숫자가 들어갈 수 있고 모든 경우를 탐색하면 $O(9^{81})$이다. 제한 시간에 풀 수 없다고 생각함. 하지만 이건 브루트 포스 방식이고 제약 조건 걸어서 가지치기 되면 속도를 줄일 수 있다고 생각. 빈칸 '0'에 숫자를 하나 넣으면 행, 열, 3x3 판에 다른 숫자를 쓸 수 없기에 선택지가 줄어든다.

풀이 구조

가지치기 위해서 넣을려고 하는 숫자가 괜찮은지 확인해야한다. 숫자를 넣을 때마다 반복문을 돌려 가로, 세로, 3x3에 겹치는 수가 있는지 확인하면 시간초과 날 것. 그래서 숫자 사용했는지 기록하는 배열 3개 구성.

• row[i][num] - i번째 행에 num 있는지
• col[j][num] - j번째 행에 num 있는지
• square[k][num] - k번째 3x3에 num 있는지 => k = (i//3)*3 + (j//3) 이러면 해당 칸에 num을 넣어도 되는지 O(1)에 확인 가능하다.

판에 '0'인 수를 모아두는 배열을 만들어서 '0' 좌표들 값을 통해 백트래킹으로 수행

결론

1. 빈 칸에 1~9까지 숫자 넣어보기
2. 행, 열, 3x3에 이미 존재하는 숫자라면 가지치기
3. 존재하지 않는 숫자라면 다음 빈 칸으로 넘어가기
4. 모든 빈 칸을 채웠다면 스도쿠 완성, 출력 후 종료

풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# row[i][num] - i번째 행에 num 있는지
# col[j][num] - j번째 행에 num 있는지
# square[k][num] - k번째 3x3에 num 있는지

board = [list(input().rstrip()) for _ in range(9)]
check = []

row = [[False] * 10 for _ in range(9)]
col = [[False] * 10 for _ in range(9)]
square = [[False] * 10 for _ in range(9)]

def func(cnt):
    if cnt == len(check):
        for li in board:
            print("".join(li))

        sys.exit(0)

    x, y = check[cnt]
    k = (x // 3) * 3 + (y // 3)

    for number in range(1, 10):

        if not row[x][number] and not col[y][number] and not square[k][number]:
            row[x][number] = col[y][number] = square[k][number] = True
            board[x][y] = str(number)

            func(cnt + 1)
            row[x][number] = col[y][number] = square[k][number] = False
            board[x][y] = '0'


for i in range(9):
    for j in range(9):
        num = int(board[i][j])
        if num == 0: check.append((i, j))
        else:
            row[i][num] = True
            col[j][num] = True
            k = (i // 3) * 3 + j // 3
            square[k][num] = True


func(0) # check배열 첫 번째 좌표 값부터 백트래킹 시작

https://www.acmicpc.net/problem/15591

문제 요약

주어진 입력 K, V에 대해 V번 노드보다 K(가중치)이상으로 연결된 노드 개수 구하기

풀이 과정

처음 생각

인접 행렬을 이용해 특정 노드에서 다른 노드까지의 거리를 각각 구하는 것

생각 바꾸기

그런데 노드 개수 N개에 간선이 N-1개로 적기 때문에 굳이 인접 행렬로 하지 않아도 되고, 각 쿼리마다 어떤 노드에서 연결된 다른 노드들 중 조건 만족하는 곳만 찾으면 된다. 무엇보다 문제를 읽어보면 이는 트리라는 것을 알 수 있다.

핵심

어떤 노드에서 다른 노드로 갈 때 중간에 있는 여러 edges들 중 min(edges) >= K를 만족해야하지만 가능 경로에서 K보다 작다면 더 이상 볼 필요가 없다. 즉, 굳이 min(edges)를 구하지 않아도 된다.

흐름

• (u, v, cost)를 입력 받아 인접리스트에 add
• Q 개수 만큼 각 노드 u를 시작으로 dfs 순회해서 조건 K에 만족하는 경로가 있는지 찾기
• 있다면 cnt++

구현

import java.util.*;
import java.io.*;

public class Main {

    static class Pair {
        int end;
        int cost;

        public Pair(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }
    }

    static int N, Q;
    static List<Pair>[] adj;
    static boolean[] isVisited;
    static int cnt;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        adj = new ArrayList[N+3];

        for(int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            adj[u].add(new Pair(v, cost));
            adj[v].add(new Pair(u, cost));
        }

        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int u = Integer.parseInt(st.nextToken());
            cnt = 0;
            isVisited = new boolean[N+3];

            dfs(u, k);
            sb.append(cnt).append('\n');
        }

        System.out.println(sb);
    }

    private static void dfs(int cur, int k) {

        isVisited[cur] = true;

        for (Pair nxt : adj[cur]) {
            if (!isVisited[nxt.end] && nxt.cost >= k) {
                cnt++;
                dfs(nxt.end, k);
            }
        }
    }
}

새로운 유저를 생성하고, DB에 insert가 발생하고 그로 인해 서버 상태가 변경된다 최종적으로 서버 상태를 바꾸기에 POST를 쓰는 것이 마땅하다.

GET 방식의 회원가입은 안되는 것인가? 서버는 그냥 코드를 실행하는 것인데, 동작할 수 있지 않을까? 라는 의문을 가졌다. 사실상 구현이 불가능한 것은 아니다.

다음처럼 코드를 짜봤다.

@RestController
@RequiredArgsConstructor
public class Controller {

    private final UserRepository userRepository;

    @GetMapping("/signup")
    public ResponseEntity<String> signup(@RequestParam String email, @RequestParam String password) {

        User user = new User(email, password);
        userRepository.save(user);

        return ResponseEntity.ok("회원가입 완료");
    }

}

RequestParam으로 2개의 인자를 받고 그걸 바탕으로 저장한다.

위와 같이 요청을 보내면 잘 저장된다.

하지만 GET 방식의 코드는 치명적인 오류가 있다. HTTP에서 GET은 안전을 의미한다. 즉, 서버 상태를 바꾸면 안 되는데 DB에 insert가 발생하여 GET의미를 위반한다.

HTTP에서 캐시는 주로 GET 응답을 재사용한다. 그런데 GET으로 상태 변경을 하면 새로고침, 크롤링, 재시도 등 같은 자동 동작에 의해 동일 요청이 반복되어 중복 생성이 발생 가능하고, 캐시가 응답을 재사용하면 실제 처리 없이 응답만 반복될 수 있다.

검색 엔진이 운영하는 프로그램으로 콘텐츠를 수집하는데, 이때 GET 링크를 통해 수집한다. GET으로 회원가입을 한다면…? 당연히 봇이 이 URL을 타고 들어가고 계정이 계속해서 생성될 것이다.

결론적으로 이는 HTTP 스펙 / REST 위반, 보안 위험, 캐싱 위험이기에 절대 사용할 수 없다.

따라서 의미있는 약속의 프로토콜이 필요했기에 HTTP가 나온 이유이지 않을까 싶다.

GET 메서드 관련해서 safe / idempotent가 언급된다.

Safe

서버의 상태를 변경해서는 안 된다. 즉, 요청을 할 시 사용자가 의도한 상태 변경이 없어야 한다. 완전히 상태 변화 없음 보다는 의도된 상태 변경이 없어야 한다.

Idempotent

멱등은 여러 번 호출해도 서버 최종 상태가 같아야 한다. 예를 들어 Delete user10을 했다면 첫 요청에 삭제된다. 이후 호출을 계속해도 이미 삭제되어 있기에 서버 최종 상태는 변화 없다. user 10은 이미 삭제되어 존재하지 않기 때문이다.

물론 첫 요청(200)의 응답과 이후 요청(404) 응답값이 다를 수 있지만 서버 상태가 같기에 멱등이다.

Cacheable

safe, idempotent와 함께 캐시 가능 여부를 볼 수 있다. 이는 응답을 저장하고 재사용이 가능한가 보는 것이다.

보면 Safe한 메서드는 Idemptoent이다. GET, HEAD 메서드만 캐시 가능하고 POST는 항상 멱등이 아니다.

PUT은 전체를 덮어쓰기 때문에 항상 멱등이지만 PATCH는 부분 수정이라는 특성 때문에 상황에 따라 다를 수 있다. 예를 들어 +10씩 되도록 연산 처리하는 요청을 반복 시 상태가 달라질 수 있게 된다.

결론

GET으로 회원가입을 구현하는 건 가능하다. 하지만 HTTP에서 GET은 조회라는 의미를 가지며, 웹에서 이를 전제로 캐시, 크롤링, 재시도 등이 이루어진다.

GET으로 상태 변경을 수행하면 이 규칙이 깨져 보안 및 의도치 않는 반복 실행이 발생해 회원가입은 POST로 설계해야 한다.

관리가 필요한 이유

컴퓨터 메모리는 한정되어 있고 컴퓨터는 메모리 자원을 효율적으로 관리해야 한다. 이때 어떤 데이터를 내보낼 것인가는 성능에 있어 매우 중요하다.

필요 사전 개념

메모리 관리에 관한 내용을 보면 '페이지' 개념이 나온다. 이를 책으로 비유해보면 다음과 같다.

• 메모리: 책상
• 페이지: 책의 낱장(종이 한 장)
• 프로세스: 여러 장의 페이지로 이뤄진 책
• 프레임: 책상 위에 페이지 딱 한 장만 놓을 수 있는 구역

프로그램 크기가 커지면 메모리에 다 들어가지 못한다. 따라서 프로그램을 일정한 단위로 쪼개서 필요한 부분만 메모리에 올린다. 이때 쪼개진 일정한 크기의 조각을 '페이지'라고 부른다.

왜 '페이지'라는 이름일까?

책의 페이지는 크기가 고정이다. OS의 페이지도 마찬가지로 고정된 크기를 갖고 있다. 크기가 같아야 프레임(메모리)의 칸에 맞게 끼워넣을 수 있다.

책의 23페이지를 읽다가 100페이지로 넘어갈 수 있는 것처럼 메모리에 페에지도 여기저기 빈 공간에 흩어져 잇다가 OS가 '페이지 테이블'을 보고 찾아 낼 수 있다.

프레임은?

페이지는 데이터를 잘라놓은 조각인 논리적 단위라면, 프레임은 페이지 하나가 들어갈 수 있는 실제 구멍인 물리적 단위이다.

따라서 프레임 하나에 여러 페이지가 들락날락 하는 것이다. 프레임은 한정되어 있고, 수많은 페이지들이 그 자리를 차지하기 위해 경쟁한다.

LRU 알고리즘 개념

LUR 알고리즘은 페이지 교체 알고리즘 중에 하나이며, 최근에 사용하지 않는 페이지를 가장 먼저 내려 보내는 알고리즘이다. (가장 오랫동안 사용되지 않은 데이터 제거)
여기에 최근에 참조된 데이터는 곧 다시 참조될 가능성이 있고, 반대로 오랫동안 참조되지 않은 데이터는 앞으로도 사용될 가능성이 낮다는 '시간 지역성' 개념이 들어간다.

위의 그림을 보면 페이지 크기는 3이고 0부터 4까지 숫자들이 참조되고 있다. 시간 1에서 참조값 0이 페이지에 들어가고 이후 시간 2,3에서 각각의 참조값이 들어간다.

시간이 4일 때 참조값은 3이지만 페이지가 꽉 차있으므로 가장 오래된 시간1에서의 참조값 0을 밀어내고 그 자리를 시간4의 참조값 3이 차지한다.

시간 7이 되었을 때 참조값 3이 들어가고자 하는데, 이미 시간6에서의 페이지를 보면 3이 존재한다. 이때는 이미 존재하기에 cached hit가 발생해 시간7에서의 참조값 3은 가장 최근 순서가 된다. 추가로 시긴7에서의 참조값 3이 이미 앞에서 있었기 때문에 페이지 부재가 발생하지 않는다

따라서 시간 8에서의 참조값 2가 들어올 때 페이지에서 3이 아닌 4가 교체되어 참조값 2가 그 자리를 차지하게 된다.

페이지 부재(폴트)

CPU가 페이지를 가져오는데 프레임에 그 페이지가 없다면 어떻게 될까? 이때 페이지 폴트가 발생한다.

CPU는 필요한 페이지가 메모리에 없음을 알고, OS가 디스크로 가서 관련 페이지를 찾는다.

추가로 만약 프레임이 꽉 찼다면 LRU같은 페이지 교체 알고리즘을 사용해 새 페이지를 앉힌다.

페이지가 너무 자주 왔다갔다 한다면?

프레임이 작아 여러 페이지가 왔다갔다를 자주한다면 거기에 많은 시간이 소요된다. 이때 컴퓨터는 '스레싱' 현상이 발생해 CPU 이용률이 떨어진다.

빌드 타임

1. 개발자가 소스 코드를 작성하고 이 파일의 확장자는 .java이며, 이는 읽을 수 있는 텍스트 형식이다.
2. JDK에 포함된 자바 컴파일러(javac)가 소스 코드를 분석한다. 이때 컴퓨터가 바로 이해하는 기계어로가 아닌, 자바 바이트코드로 변환한다. 이때 확장자는 .class이다. → 이때 바이트 코드는 특정 OS에 종속되지 않는 중간 단계 코드

런타임

1. Java Virtual Machine의 클래스 로더가 실행에 필요한 .class 여러 파일을 찾아 JVM 메모리인 런타임 데이터 영역에 올린다. 이때 자바는 한꺼번에 모든 class 파일을 올리는 게 아닌, 필요한 시점에 동적으로 올린다.
2. 메모리에 로드된 .class 파일 즉, 바이트코드는 실행 엔진에 의해 기계어로 해석된다. 이때 두 가지 방식이 병행된다.
   1. 인터프리터 : 바이트코드를 한 줄씩 읽어 실행한다. 초기에는 빠르지만, 반복되는 코드도 매번 해석해 전체적인 속도는 느릴 수 있다
   2. Just-In-Time Compiler (JIT 컴파일러) : 위의 인터프리터 단점을 보완한다. 자주 실행되는 코드(= Hot Spot)를 찾아내어 통째로 기계어로 컴파일 한 후 code cache라는 특수 메모리 영역에 저장한다. 이후에는 따로 해석 없이 바로 실행이 가능하다
3. 프로그램 실행에서 더 이상 사용되지 않는 객체를 알아서 식별해 해제한다. 이에 메모리 관리에 신경을 덜 쓸 수 있다.

과정 요약

소스 코드 작성 → 자바 컴파일러의 변환 → 클래스 로더의 동적 로딩 → 실행 엔진 가동 → 가비지 컬렉터 관리

JVM 런타임 데이터 영역에 관하여

Runtime Data Area는 JVM의 메모리 영역으로 자바가 실행하는 동안 데이터를 저장 및 관리한다.

총 5개의 구조로 나눠져 있다.

• Method Area
  • JVM이 읽어들인 필드 값, 메소드 데이터, 런타임 상수 풀이다
    • 런타임 상수 풀은 int = 100; 과 같은 리터럴 값과 심볼릭 레퍼런스(메서드 이름)라는 이름 정보가 들어가 있다.
    • 메서드가 호출 될 때, JVM이 상수 풀의 이름만 보고 실제 메모리 주소를 찾아내어 주소값을 상수 풀에 덮어 씌우는 것
• Heap Area
  • 모든 객체와 배열이 저장된다. 즉, 실제 데이터가 들어가 있는 곳이다 (주소는 스택에)
  • 특히 GC의 메인 관리 대상이며, 효율적인 GC를 위해 Young Generation과 Old Generation으로 다시 나뉜다.

• Stack Area
  • 메소드 호출 할 때 마다 ‘스택 프레임’ 블록이 쌓인다. 여기에는 지역 변수, 매개 변수, 리턴 값 등이 임시 저장되며, 메소드 종료 시 바로 제거된다.
• PC Register
  • 현재 수행하고 있는 JVM 명령의 주소를 저장한다. CPU 레지스터 개념과 유사하다
• Native Method Stack
  • 자바 외의 언어로 작성된 네이티브 코드를 실행하기 위한 메모리 공간이다.

Heap Area에 관하여

런타임 데이터 영역의 Heap 영역은 효율적 관리를 위해 Young Generation과 Old Generation으로 나눈다.

• Young: 새로운 객체들이 할당된다. 대부분 객체는 여기서 생성되고 사라진다

  • Eden: new 연산자로 생성된 객체가 위치한다

  • Survivor0 , Survivor1 : Eden 영역에 데이터가 가득차면 Eden에 있던 객체가 Survivor0 또는 Survivor1로 옮겨진다. 옮겨진 객체들은 참조되고 있는 객체들이기에, 둘 중 하나의 영역이 가득차면 다른 Survivor로 이동한다. 그렇기에 둘 중 하나는 비어 있어야 하는 특징이 있다.

  • 이 과정에서 Minor GC가 발생한다. Young 영역에서 발생하는 GC로 Eden 영역 또는 Survivor0, Survivor1에서 사용되지 않는 객체들을 삭제한다.

• Old: Survivor0, Survivor1을 왔다 갔다 하는 과정에서 살아남은 객체들(즉, Young 영역에서 살아남은 객체들)은 Old 영역으로 이동한다. Young 영역보다 크기가 크게 할당되기에 그만큼 GC가 적게 발생한다. 그럼에도 GC가 발생하게 되는데 Old 영역에서 Major GC(Full GC) 가 발생한다.

• 번외: Java7까지는 Permanaget Gen 영역이 힙에 포함되었으나, 8부터는 Metaspace라는 이름으로 분리되어 Native Memory 영역으로 옮겨갔다.

그렇다면 GC과정은 어떻게 될까?

GC는 Mark and Sweep 알고리즘 전략을 따른다.

GC가 힙 내부를 돌면서 사용 중인 객체와 사용하지 않는 객체를 식별(Mark)하고 사용되지 않는 객체들을 메모리에서 제거(Sweep)한다.

위 Young 영역에서 Eden에 데이터가 가득차면 Survivor로 옮겨지고 Survivor 1, 2를 왔다 갔다 한다고 했다. 이때 각 객체에는 age bit가 있고 이 과정을 반복하며 객체들이 번갈아 이동할 때 age를 1씩 먹는다.

객체의 age 값이 설정값인 MaxTenuringThreshold 를 초과하면 Old 영역으로 객체를 이동시킨다.

Old 영역의 공간이 부족해지면 Major GC(Full GC)가 발생하고, 이때 Stop-The-World 현상이 발생하는데, 이는 GC를 실행하는 스레드를 제외한 모든 애플리케이션 스레드가 멈춘다.

Major GC는 위에서의 Minor GC보다 훨씬 오래 걸린다. 이 시간을 줄여야하는데 이것이 GC 튜닝의 핵심이다. 힙 영역이 크면 GC 한 번에 애플리케이션 중지되는 시간(STW) 이 길어지고, 너무 작으면 GC가 자주 발생하기에 성능이 떨어지기 때문이다.

Reference

https://velog.io/@ddangle/Java-%EB%9F%B0%ED%83%80%EC%9E%84-%EB%8D%B0%EC%9D%B4%ED%84%B0-%EC%98%81%EC%97%ADRuntime-Data-Area%EC%97%90-%EB%8C%80%ED%95%B4

https://blog.devgenius.io/java-virtual-machine-architecture-9009d864fc72

http://equj65.net/tech/java8hotspot/

https://1-7171771.tistory.com/140

https://www.acmicpc.net/problem/3085

문제 정리

각 Row, Column에 따라 연속된 문자의 개수 구하기 이때 붙어있는 것끼리 교환할 수 있다.

시간복잡도

• 모든 칸 오른쪽, 아래쪽 교환 - 2 x N^2
• 교환마다 검사 2 * N^2
• 총 O(N^4) N은 최대 50

풀이 과정

교환했을 경우 어떻게 되었는지에 대한 코드가 필요하다.

• 시작은 왼쪽 위 상단부터 시작해서 오른쪽 하단으로 간다

• 그렇기에, 현재 위치에서의 오른쪽 또는 아랫쪽의 교환 시 발생하는 개수에 대해 확인

• 필요한 부분 코드

  • swap 함수 - swap()
  • 오른쪽과 교환
  • 아랫쪽과 교환
  • row, column 기준으로 개수 세기 - RowColumnCount()

위 기준으로 크게 잡고 코드를 구성하면 된다.

import java.util.*;
import java.io.*;

public class Main {

    static char[][] board;
    static int n;
    static int res;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        board = new char[n+3][n+3];
        for(int i = 0; i < n; i++) {
            board[i] = br.readLine().toCharArray();
        }

        for(int i = 0; i < n; i++) {
            for (int j = 0; j < n ; j++) {
                // 오른쪽과 교환
                if (j < n - 1) {
                    swap(i, j, i, j+1);
                    RowColumnCount();
                    swap(i, j, i, j+1);
                }

                // 밑에와 교환
                if (i < n - 1) {
                    swap(i, j, i+1, j);
                    RowColumnCount();
                    swap(i, j, i+1, j);
                }
            }
        }

        System.out.println(res);
    }

    public static void RowColumnCount() {

        // row 개수
        for(int i = 0; i < n; i++) {
            int cnt = 1;
            for (int j = 0; j < n-1; j++) {
                if (board[i][j] == board[i][j+1]) cnt++;
                else {
                    res = Math.max(res, cnt);
                    cnt = 1;
                }
            }
            res = Math.max(res, cnt);
        }

        // col 개수
        for(int j = 0; j < n; j++) {
            int cnt = 1;
            for(int i = 0 ; i < n-1; i++) {
                if (board[i][j] == board[i+1][j]) cnt++;
                else {
                    res = Math.max(res, cnt);
                    cnt = 1;
                }
            }
            res = Math.max(res, cnt);
        }
    }

    public static void swap(int x1, int y1, int x2, int y2) {
        char temp = board[x1][y1];
        board[x1][y1] = board[x2][y2];
        board[x2][y2] = temp;
    }
}

생각해내는 것은 쉬웠는데, 구현이 다소 까다로웠다.

https://www.acmicpc.net/problem/4948

구해야하는 소수의 범위는 (주어지는 숫자 + 1, 2 * 주어지는 숫자] 범위. 시간이 1초이기에 브루트포스 방식은 시간 초과 발생

-> 에라토스테네스의 체를 이용해 최대 범위 숫자인 123,456 x 2 만큼의 수가 소수인지를 저장하는 배열 사용 -> 이후 주어지는 수의 x 2 만큼의 배열을 돌면서 소수의 개수가 몇 개 인지 확인.

import java.util.*;
import java.io.*;

public class Main {



    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int[] board = new int[250000];
        board[1] = 1;

        for(int i = 2; i <= 123456; i++) {
            if (board[i] == 0) {
                int mul = 2;
                while (mul * i < 250000) {
                    board[mul * i] = 1;
                    mul++;
                }
            }
        }

        while(true) {
            int num = Integer.parseInt(br.readLine());
            if (num == 0) break;

            int cnt = 0;

            for (int i = num + 1; i <= 2 * num; i++) {
                if (board[i] == 0) {
                    cnt += 1;
                }
            }
            System.out.println(cnt);
        }


    }
}

넉넉하게 250,000의 수를 담을 수 있는 배열 선언하고 에라토스테네스의 체 방법을 이용해 코드 구성 구성

명령어 파이프라이닝 - Instruction Pipelining

• CPU가 여러 명령어를 동시에 처리하기 위해 각 명령어를 여러 단계로 분할한다. 즉 각 단계를 다른 명령어와 겹쳐서 실행한다.
• 전통적인 CPU는 한 번에 하나씩 처리하지만 파이프라인 기법의 CPU는 그렇지 않다. 여러 명령어를 다른 단계에서 동시 처리 하는 것이다.
   [출처 : 위키피디아]
• 5개의 명령어가 동시에 처리되고 있는 모습이다.

• 파이프라인 기법의 CPU는 동시에 처리함으로써 높은 성능을 가져올 수 있지만 항상 그런 것은 아니다. 이를 파이프라인 위험 - Pipeline Hazard라고 한다.

1. 데이터 위험: 데이터 의존적인 두 명령어를 동시 실행 시 파이프라인이 제대로 작동하지 않는다.

-> 명령어 B가 명령어 A의 연산 결과 R을 의존할 때, 명령어 A의 저장 결과 단계가 끝나야 명령어 B가 R을 사용 가능하다.

2. 제어 위험: 분기 or 조건문 등으로 인해 다음 실행 명령어가 무엇인지 결정을 내리지 못해 파이프라인이 멈춘다. 이를 해결하기 위해 분기 예측 기법을 사용할 수 있지만, 에측 실패 시 계산된 파이프라인을 버리게 되고 이는 성능 저하로 이어진다.

3. 구조적 위험: 한 명령어가 자원 사용 시 그 자원을 필요로 하는 다른 명령어는 멈추게 되어 파이프라인이 작동하지 않는다.

-> 서로 다른 명령어가 ALU와 같은 CPU 자원을 사용할 때가 그러하다.

Keywords

CPU, 파이프라인, 명령어, 단계, 성능 향상/저하, Hazard Hazard 3개 - 데이터, 제어, 구조

Summary

전통 CPU와 달리 지금 CPU는 여러 명령어를 동시 처리한다. 이때 파이프라이닝 기법을 사용해 성능을 높인다. 하지만 성능이 좋아지지 않는 경우가 있다. 명렁어 의존으로 인한 데이터 위험, 분기/조건 등으로 결정을 내리지 못하는 제어 위험, 자원 필요로 인한 구조적 위험이다.

자바에서 String은 불변의 객체이다. 따라서 String을 이용해 문자열 연산이 잦으면 힙 메모리에 많은 중간 객체가 생성 및 제거되고 이는 성능 저하로 이어진다.

따라서 변하지 않은 문자열을 저장할 때 적합하다.

StringBuilder와 StringBuffer는 이를 커버할 수 있다.

• StringBuilder 비동기 방식이기에 Single Thread 환경에서 변화되는 문자열에 사용한다. 비동기 방식이기에 처리 속도는 빠르다.

• StringBuffer 동기 방식으로 저장되기에 Multi Thread 환경에서 문자열이 변경될 경우 사용한다.

StringBuilder를 멀티 스레드 환경에서 사용하면 어떻게 될까?

망한다. StringBuilder에서 문자열이 추가될 때, 즉 append() 메서드가 실행되면 그 방식은 다음과 같다.

1. 현재 문자열 길이 확인
2. 추가할 문자열 공간 확인
3. 공간 부족? -> 내부 크기 확장
4. 새로운 문자열 추가
5. 전체 길이 업데이트

StringBuilder의 문제: 이 과정을 한 스레드가 끝내지 못했다면 다른 스레드가 중간에 들어올 수 있다. 그러면 덮어쓸 수도, 뒤섞일 수 있는거다.

이런 개념은 알고 있었지만 실제 코드로 딱히 쳐본적이 없었기에 둘의 차이를 보기 위해 코드로 간편하게 구현해봤다.

코드

public class Main {

    public static void main(String[] args) throws InterruptedException {

        // 1. StringBuilder 테스트 - 여러 스레드에서 동시에 접근할 때 안전하지 않다
        StringBuilder sb = new StringBuilder();

        Runnable stringBuilderTask = () -> {
            for (int i = 0; i < 1000; i++) {
                sb.append("A");
            }
        };

        Thread[] stringBuilderThreads = new Thread[10];
        for (int i = 0; i < 10; i++) {
            stringBuilderThreads[i] = new Thread(stringBuilderTask);
            stringBuilderThreads[i].start();
        }

        for (int i = 0; i < 10; i++) {
            stringBuilderThreads[i].join();
        }

        System.out.println("StringBuilder의 결과 길이: " + sb.length());



        // 2. StringBuffer 테스트 - 여러 스레드에서 동시에 접근할 때 안전하다
        StringBuffer sbf = new StringBuffer();

        Runnable stringBufferTask = () -> {
            for (int i = 0; i < 1000; i++) {
                sbf.append("A");
            }
        };

        Thread[] stringBufferThreads = new Thread[10];
        for (int i = 0; i < 10; i++) {
            stringBufferThreads[i] = new Thread(stringBufferTask);
            stringBufferThreads[i].start();
        }

        for (int i = 0; i < 10; i++) {
            stringBufferThreads[i].join();
        }

        System.out.println("StringBuffer의 결과 길이: " + sbf.length());

    }
}

첫 번째 실행 결과

StringBuilder의 결과 길이: 4009
StringBuffer의 결과 길이: 10000

두 번째 실행 결과

Exception in thread "Thread-0" java.lang.ArrayIndexOutOfBoundsException: arraycopy: last destination index 1151 out of bounds for byte[34]
StringBuilder의 결과 길이: 8799
StringBuffer의 결과 길이: 10000

StringBuilder의 값은 그때마다 다르고, 길이 계산 오류로 인한 예외도 터진다.

즉, StringBuilder는 다른 스레드에 의해 일관성이 깨지는 위험이 있는 것이다.

https://www.acmicpc.net/problem/1644

문제 정리

• 자연수를 연속된 소수의 합으로 나타내기 (중복x)
• 시간 2초, 자연수 최대 : 4,000,000

풀이 과정

시간이 빠듯하기에 O(N)이하의 시간 복잡도로 가져간다고 생각 먼저 필요한 수는 소수만 필요하기에 소수를 먼저 뽑아준다. 2 ~ N까지의 수를 뽑아야 하며, 이때 어떤식으로 뽑을지 고민 만약 2 ~ N까지 각 수마다 하나씩 i_f n % i == 0_ 과 같은 방식으로 소수를 판별하면 시간이 오래걸린다. 이에 에라토스테네스의 체 방식(def is_prime)으로 소수를 구함으로써 계산 시간을 최대한 줄인다.

그 다음 연속된 소수의 합(total)이 N이 되는지 파악하기 위해 포인터 2개(st, en)를 사용하여 total이 N보다 크다며 en을 증가시키고, 아니라면 st를 증가시킨다.

물론 total이 N과 같다면 경우의 수를 1 증가시키고 en을 증가시키냐, st를 증가시키냐에 따라 total도 늘리거나 줄어야한다.

n = int(input())

def is_prime(x):

    prime = [True] * (n + 1)
    prime[0] = prime[1] = False

    for i in range(2, int(n**0.5) + 1):

        if prime[i]:
            for j in range(i*i, n + 1, i): # i의 배수 제거 -> n까지
                prime[j] = False

    return [i for i in range(2, n+1) if prime[i]]



st = en = cnt = 0
board = is_prime(n)
board.append(0)
total = board[st]

for st in range(len(board)): # st 끝까지

    while en < len(board) - 1 and total < n:
        en += 1
        total += board[en]

    if en == len(board): break

    if total >= n:
        if total == n: cnt += 1
        total -= board[st]

print(cnt)

https://www.acmicpc.net/problem/17136

문제 요약

10 x 10 크기에 색종이를 최소 개수로 붙여야 한다.

생각

• 범위가 충분히 작기에 브루트포스 방식으로 접근한다.
• 색종이가 1x1 ~ 5x5가 있고 최소 개수가 되기 위해 그리디스럽게 5x5로 먼저 접근해도 되겠다고 생각한다.
• 브루트포스로 접근하여 모든 색종이를 다 붙여보지만 붙일 수 없는 경우라면 더 보지 않고 return 하는 게 낫다

어떤 경우일까

• 일단 붙이는 좌표 기준으로 색종이 범위가 벗어나면 붙일 수 없다
• 색종이가 크기 당 각 5개씩 있으므로 어떤 색종이를 다 썼다면 붙일 수 없다 -> 다음 색종이 사용해야한다
• 색종이를 붙이려고 하는데 기존에 사용한 색종이 개수(1을 모두 채운)보다 더 많이 사용했다며 볼 필요 없다

재귀를 사용할 때 func() 의 인자를 어떻게 잡아야 할까

• 색종이를 붙이는 위치가 필요하니깐 위치 의미하는 파라미터
• 현재까지 사용한 색종이 개수를 알아야 하는 파라미터

• func(loc, cnt)

색종이를 붙였다면 그 자리는 어떻게 처리할까

1 부분에 색종이를 붙이는 것이기에 붙였다면 그 사이즈만큼 0으로 처리해서 더 이상 보지 않는다 java fill(n, m, i, 0); // 1을 0으로 채우기 당연스럽게도 0으로 채운 부분은 다음 턴 때 다시 봐야 하기에 1로 복구 시켜야한다.

코드

import java.io.*;
import java.util.*;

public class Main{

    public static int[][] board = new int[12][12];
    public static int[] paperCount = {0, 5, 5, 5, 5, 5};
    public static int res = Integer.MAX_VALUE;


    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st;

        for(int i = 0; i < 10; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 10; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        func(0, 0);
        if(res == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(res);

    }

    private static void func(int loc, int cnt) {

        if (loc == 100) {
            res = Math.min(res, cnt);
            return;
        }

        if (res <= cnt) return;

        int n = loc % 10;
        int m = loc / 10;

        if(board[n][m] == 1) {

            for(int i = 5; i >= 1; i--) {
                if(paperCount[i] > 0 && check(n, m, i)) {
                    paperCount[i]--;
                    fill(n, m, i, 0); // 1을 0으로 채우기
                    func(n * m + 1, cnt + 1);

                    fill(n, m, i, 1); // 0으로 채웠던 부분 다시 1로 복구
                    paperCount[i]++;

                }
            }
        } else {
            func(loc + 1, cnt);
        }

    }

    private static boolean check(int n, int m, int num) {

        if(n + num > 10 || m + num > 10) return false;

        for (int i = n; i < n + num; i++) {
            for (int j = m; j < m + num ; j++) {
                if(board[i][j] == 0) return false;
            }
        }

        return true;
    }

    private static void fill(int n, int m, int num, int k) {

        for(int i = n; i < n + num; i++) {
            for(int j = m; j < m + num; j++) {
                board[i][j] = k;
            }
        }
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/42889

문제 요약

스테이지 N개에 대한 실패율 내림차순으로 구하기

접근

stages 배열에 사용자가 현재 머물고 있는 stage가 있다. 실패율은 (도전하고 있는 사용자)/(도전하고 있는 사용자 & 통과한 사용자) 분모에 들어가는 인원을 구하기 위해 이진 탐색을 이용했다.

stages 배열 [2, 1, 2, 6, 2, 4, 3, 3] 을 정렬 시키면 [1, 2, 2, 2, 3, 3, 4, 6] 만약 2의 실패율을 구해본다면 3/7이 나와야 한다.

2의 lowerBound => 1, upperBound => 4, stages 배열의 길이 : 8 즉 (upperBound - lowerBound) / (stages - lowerBound) 로 구하면 된다.

위의 방법으로 각 스테이지(1~N)를 루프를 돌아 구한 후, 정렬하면 된다. 다음 코드와 같다.

import java.util.*;
import java.io.*;

class Pair<A, B> {
    public A first;
    public B second;

    public Pair(A first, B second) {
        this.first = first;
        this.second = second;
    }
}

class Solution {

    public int[] solution(int N, int[] stages) {
        int[] answer = {};

        int[] board = new int[N+3];
        for(int i = 0; i < N; i++) {
            board[i] = i + 1;
        }

        Arrays.sort(stages);
        ArrayList<Pair<Double, Integer>> v = new ArrayList<>();

        for(int i = 0; i < N; i++) {
            int num = board[i];
            int low = lowerBound(num, stages);
            int upper = upperBound(num, stages);

            double res = 0.0;
            res = (double)(upper - low) / (stages.length - low);
            if (Double.isNaN(res)) {
                res = 0.0;
            }

            System.out.println(num + " " + res + " Low : " + low + " Upper : " + upper);

            int index = i+1;
            v.add(new Pair<>(res, index));
        }

        v.sort(Comparator.comparing(p -> p.first, Comparator.reverseOrder()));


        return v.stream().mapToInt(p -> p.second).toArray();

    }

    private static int lowerBound(int num, int[] stages) {
        int l = -1;
        int r = stages.length;

        while (l + 1 < r) {
            int mid = (l+r) / 2;
            if (stages[mid] < num) l = mid;
            else r = mid;
        }

        return r;
    }

    private static int upperBound(int num, int[] stages) {
        int l = -1; 
        int r = stages.length;

        while (l + 1 < r) {
            int mid = (l+r) / 2;
            if (stages[mid] > num) r = mid;
            else l = mid;
        }

        return r;
    }
}

stages 배열(길이 M)을 정렬 - O(MlogM) lower,upperBound - O(logM) -> 이를 N번 하기에 O(NlogM) v 정렬 - O(NlogN) 총 O(MlogM + NlogM)이 된다.

실행 결과는 다음과 같다.

다시 생각

정답은 맞았지만 위의 사진처럼 이는 상당한 시간을 요구했다. 이 문제에는 비효율적이라 생각했고 이를 카운팅 배열과 Map을 사용해 다시 구성해보았다.

stages 배열을 딱 한 번만 순회해 각 스테이지에 머물러 있는 사용자 수를 미리 계산한다. -> board[stages[i]] += 1 stages 배열을 훑으면서 board 배열에 스테이지별 도전자 수를 카운트 하는 것

코드는 다음과 같다.

import java.util.*;
import java.io.*;

class Solution {

    public int[] solution(int N, int[] stages) {
        int[] answer = {};

        int[] board = new int[N+3];
        for(int i = 0; i < stages.length; i++) {
            board[stages[i]] += 1; // board는 stages를 도전하고 있는 인원의 수
        }

        HashMap<Integer, Double> m = new HashMap<>();

        int cnt = stages.length; // 인원

        // 실패율 계산
        for(int i = 1; i <= N; i++) {
            if(board[i] == 0) m.put(i, 0.0);
            else {
                m.put(i, (double)board[i] / cnt);
                cnt -= board[i]; // 현재 스테이지 인원을 감소시켜야함
            }
        }

        // 실패율(key:value 중 value) 기준 내림차순
       return m.entrySet()
            .stream()
            .sorted((o1, o2) -> Double.compare(o2.getValue(), o1.getValue()))
            .mapToInt(map -> map.getKey())
            .toArray();
    }


}

board 배열을 순회해 각 스테이지에 머물러 있는 사용자 수 계산 (길이 M의 stages 순회) : O(M) 각 스테이지 실패율 계산 : O(N) 실패율 기준 정렬 : O(NlogN) 큰 항만 고려해서 -> O(M + NlogN)

실행 결과는 다음과 같다.

첫 번째 풀이와 비교해봤을 때 반복문 내에서 수행되는 연산의 비용을 최소화 해야 했다.

현재 상황

이전에 작성했던 User 어노테이션에서 사용자 프로필 조회를 해보면 쿼리가 두 번 나가고 있다.

첫 번째 쿼리는 userId로, 두 번째 쿼리는 userEmail로 사용자를 조회 하고 있었고 이는 똑같은 유저 정보를 두 번씩이나 불필요하게 조회한 상황...;

쿼리가 발생되는 곳을 찾아가보니 jwtFilter에서의 1차 조회, UserInfoResolver에서의 2차 조회가 발생했다.
다음 코드처럼 jwtFilter에서의 doFilterInternal 메서드에서 jwt 토큰의 userId로 사용자를 조회 후 이 정보를 인증 객체인 Authentication를 생성해 SecurityContextHolder에 저장하는 데 사용되도록 구성했었다.

try {
            String header = request.getHeader("Authorization");
            if (header != null && header.startsWith("Bearer ")) {
                String token = header.split(" ")[1];

                jwtProvider.isValid(token);

                Long userId = jwtProvider.getUserId(token);
                int tokenVersion = jwtProvider.getTokenVersion(token);
                User user = userRepository.findById(userId).orElseThrow(() -> new UserCustomException(UserErrorCode.USER_NOT_FOUND));
                if(user.getTokenVersion() != tokenVersion) {
                    throw new CustomException(UserErrorCode.LOGGED_OUT_USER);
                    }
                UserDetails userDetails = new PrincipalDetails(user);
                 Authentication authentication = new UsernamePasswordAuthenticationToken(userDetails, userDetails.getPassword(), userDetails.getAuthorities());
                SecurityContextHolder.getContext().setAuthentication(authentication);
                }
      } catch ~

2차 조회가 일어나는 UserInfoResolver에서는 @UserInfo를 처리하기 위해 resolveArgument 메서드가 실행이 되고, 여기서 SecurityContextHolder에 저장된 이메일을 통해 사용자 정보를 조회하도록 코드를 구성했었다.

@Override
    public Object resolveArgument(MethodParameter parameter, ModelAndViewContainer mavContainer, NativeWebRequest webRequest, WebDataBinderFactory binderFactory) throws Exception {

            Authentication authentication = SecurityContextHolder.getContext().getAuthentication();
            if (authentication != null && authentication.isAuthenticated()) {
                String email = authentication.getName();
                return userRepository.findByEmail(email)
                        .orElseThrow(() -> new UserCustomException(UserErrorCode.USER_NOT_FOUND));
            }


        throw new UserCustomException(UserErrorCode.UNAUTHORIZED_USER);
    }

@Override
    public Object resolveArgument(MethodParameter parameter, ModelAndViewContainer mavContainer, NativeWebRequest webRequest, WebDataBinderFactory binderFactory) throws Exception {

            Authentication authentication = SecurityContextHolder.getContext().getAuthentication();

// 이전과 달리 Principal이 null이거나 예상한 타입인 PrincipalDetails가 아닐 경우 예외가 되도록 구성
        if (authentication == null || !(authentication.getPrincipal() instanceof PrincipalDetails)) {
            throw new UserCustomException(UserErrorCode.UNAUTHORIZED_USER);
        }

// Principal에서 User 객체를 바로 가져온다.
        PrincipalDetails principalDetails = (PrincipalDetails) authentication.getPrincipal();
        return principalDetails.getUser();
    }

이렇게 구성하니 한 번의 쿼리로 유저 정보를 가져왔다.

@GetMapping("/{userId}")
    @Operation(summary = "프로필 조회")
    public CustomResponse<?> getProfile(@PathVariable("userId") Long userId, @AuthenticationPrincipal PrincipalDetails userDetails) {

        User getUser = profileQueryService.getProfile(userId);

        if (!getUser.getEmail().equals(userDetails.getUsername())) {
            // 현재 로그인한 사용자의 이메일과 조회하려는 사용자의 이메일이 다를 경우
            return CustomResponse.onFail(UserErrorCode.UNAUTHORIZED_USER);
        }
     ...

로그인된 유저의 정보를 담고 있는 객체인 PrincipalDetails와 userId의 이메일을 이용해 두 사용자가 같은지 확인하고 있다.

이에 따른 응답값은 다음과 같다.

{
  "isSuccess": false,
  "status": "UNAUTHORIZED",
  "code": "USER401",
  "message": "인증되지 않은 사용자입니다."
}

크게 문제는 없지만 service를 이용해 프로필을 얻어오고 로그인한 사용자와 비교하는 과정은 번거롭다고 느꼈고 따라서 사용자의 정보를 컨트롤러에서 쉽게 파악하기 위해, 커스텀 어노테이션을 만들기로 했다.

사용자 정보를 인지하는 커스텀 어노테이션 만들기

@Target(ElementType.PARAMETER)
@Retention(RetentionPolicy.RUNTIME)
@Documented
@Parameter(hidden = true)
public @interface UserInfo {
}

먼저 User 정보를 가져온다는 의미로 커스텀 어노테이션인 UserInfo를 만든다.

• @Target(ElementType.PARAMETER): 어노테이션이 적용될 수 있는 요소의 종류를 선택하는 것으로써, ElementType.PARAMTEER을 사용해 파라미터에만 사용할 수 있도록 지정.

• @Retention(RetentionPolicy.RUNTIME): 어노테이션 정보를 언제까지 보관할지를 결정하는 것으로써, RententionPolicy.RUNTIME울 사용해 런타임에도 어노테이션 정보가 남아 리플렉션 즉, 실행 중에 어노테이션 정보를 읽고 사용할 수 있게 하는 것.

• @Documented: javaDoc에 포함될 수 있도록하여, API 문서 관련해서 이 어노테이션이 붙은 파라미터임을 문서에서 확인할 수 있도록 한다.

• @Paramter(hidden=true): api 관련해서 스웨거를 사용하고 있기에, UserInfo의 파라미터를 API 명세에서 숨기고자 사용. 이는 인증처리가 내부에서 처리하기에 파라미터를 노출시킬 필요가 없었다.

@Component
@RequiredArgsConstructor
public class UserInfoResolver implements HandlerMethodArgumentResolver {

    private final UserRepository userRepository;


    @Override
    public boolean supportsParameter(MethodParameter parameter) {
        return parameter.hasParameterAnnotation(UserInfo.class) &&
                parameter.getParameterType().equals(User.class);
    }

    @Override
    public Object resolveArgument(MethodParameter parameter, ModelAndViewContainer mavContainer, NativeWebRequest webRequest, WebDataBinderFactory binderFactory) throws Exception {

            Authentication authentication = SecurityContextHolder.getContext().getAuthentication();
            if (authentication != null && authentication.isAuthenticated()) {
                String email = authentication.getName();
                return userRepository.findByEmail(email)
                        .orElseThrow(() -> new UserCustomException(UserErrorCode.USER_NOT_FOUND));
            }

        throw new UserCustomException(UserErrorCode.UNAUTHORIZED_USER);
    }
}

두 번째로 @UserInfo 어노테이션이 붙은 곳에 로그인한 사용자의 정보를 주입할 수 있게 HandlerMethodArgumentResolver를 구현하도록 한다. 즉, @UserInfo와 User 객체를 연동하는 것이다.

• HandlerMethodArgumentResolver를 implements하는: UserInfoResolver가 컨트롤러의 파라미터를 원하는 값으로 바인딩해줄 수 있도록 한다.
• supportsParamemter: 파라미터를 처리할 수 있는지 판단하도록 한다. 여기서는 파라미터 타입이 User일 때 true를 리턴.
• resolveArgument: 위에서 true를 반환하게 되면 어떤 값을 주입할지 결정하게 된다. SecurityContextHolder를 통해 인증 정보를 가져오고, 사용자 이메일을 통해 UserRepository를 조회한다. 여기서 유저 정보가 있으면 반환하지만 아니라면 예외를 발생시키도록 하였다.

@Configuration
@RequiredArgsConstructor
public class WebConfig implements WebMvcConfigurer {

    private final UserInfoResolver userInfoResolver;

    @Bean
    public WebClient webClient() { // 기존 코드
        return WebClient.builder().build();
    }

    @Bean
    public RestTemplate restTemplate() { // 기존 코드
        return new RestTemplate();
    }

    @Override
    public void addArgumentResolvers(List<HandlerMethodArgumentResolver> resolvers) {
        resolvers.add(userInfoResolver);
    }
}

UserInfoResolver 클래스가 작동되도록 하기 위해 스프링 mvc의 동작을 제어하는 WebConfig에서 WebMvcConfigurer을 구현함으로써, addArgumentResolver를 오버라이딩하여 userInfoResolver를 add 해준다.

    @GetMapping("")
    @Operation(summary = "프로필 조회")
    public CustomResponse<?> getProfile(@UserInfo User user) {

        User getUser = profileQueryService.getProfile(user.getId());

        return CustomResponse.onSuccess(GeneralSuccessCode.OK, ProfileConverter.from(getUser));

    }

따라서 위와 같이 @UserInfo를 사용해 유저를 굳이 서비스 쪽에서 찾지 않고 로직을 실행할 수 있도록 한다. 그런데 여기서 user.getId()를 조회한다. 이렇게 되면 getProfile에서 불필요한 쿼리가 발생되기에 @UserInfo를 사용했으므로 사용자의 정보를 바로 반환될 수 있도록 힌다.

 @GetMapping("")
    @Operation(summary = "프로필 조회")
    public CustomResponse<?> getProfile(@UserInfo User user) {

        return CustomResponse.onSuccess(GeneralSuccessCode.OK, ProfileConverter.from(user));

    }

프로젝트를 진행하면서 userId 사용이 빈번해 @UserInfo 뿐만 아니라 @UserId가 있으면 더 편리하겠다고 생각하였고 @UserInfo와 유사한 방식으로 @UserId를 생성하였다.

https://www.acmicpc.net/problem/1788

생각 및 해결

dp(바텀업)을 이용해 음수인 경우의 피보나치 수 구하기 피보나치는 n >= 0인 경우를 구하지만 이 문제는 n이 음수인 경우는 어떠한가를 묻는다 F(1) = F(0) + F(-1) F(n) = F(n-1) + F(n-2)을 아래와 같이 바꿔 F(-1)이 어떻게 값이 도출되는 지 확인. F(n-2) = F(n) - F(n-1)

결국 n >= 0인 경우와 비슷하다. 시작은 결국 n이 0과 1이기에. 단지 n < 0인 경우, 절댓값 n이 짝수 or 홀수인지 확인만 해줘야한다.

# 1788 피보나치 수의 확장


dp = [0] * 1000003

n = int(input())
MOD = 1000000000

dp[0] = 0
dp[1] = 1

for i in range(2, abs(n)+1):
  dp[i] = (dp[i-1] + dp[i-2]) % MOD

if n < 0: # 음수
  num = abs(n)
  if num % 2 == 0: # 짝수인 경우는 음수임
    print(-1)
  else: # 홀수인 경우는 양수임
    print(1)
  print(dp[num])
elif n == 0:
  print(0)
  print(0)
else:
  print(1)
  print(dp[n])

주식 코드가 저장된 stockCodeRepository에서 모든 주식 코드를 가져온다. 각 코드의 주식 정보를 saveToDb()를 통해 저장한다.

saveToDb(String response) 에서 위에서 받아온 response 값을 이용해 엔티티를 DTO에 맞게 구성하여 stocksInfoRepository에 저장하려고 하였다.

문제는 기존에 구성했던 parsingCurrentInfo()가 Mono 결과값을 반환하여 파라미터로 Mono<> dto가 오기에 기존에 생각했던 방식으로 구성할 수 없게 되었다.

그래서 Entity를 그냥 새로 만들어야 하니 파라미터 값을 일반적인 dto로 올 수 있도록 바꿔 다음과 같이 saveToDb에서 바로 만들도록 구성하여 값을 저장하도록 했다.

이렇게 하고 한국투자증권으로 request 보내보니 response 값을 받을 수 있었다.

하지만 한 가지 간과했던 건 한국투자증권 api 요청이 limit 걸려있었다는 점. 딱히 나와있지 않아서 아무생각 없었는데 막상 실행해서 여러번 요청하니 막혔다

• 다음은 관련된 Service 코드이다.

  private Mono<ResponseCurrentOutputDto> parsingCurrentInfo(String response) {
        ResponseCurrentOutputDto data = new ResponseCurrentOutputDto();
  
        try {
            JsonNode rootNode = objectMapper.readTree(response);
            JsonNode node = rootNode.path("output");
  
  

        if (node != null) {
            ResponseCurrentOutputDto outputDto = new ResponseCurrentOutputDto();

            outputDto.setStck_prpr(node.path("stck_prpr").asText());
            outputDto.setPer(node.path("per").asText());
            outputDto.setPbr(node.path("pbr").asText());

            outputDto.setStck_shrn_iscd(node.path("stck_shrn_iscd").asText());
            data = outputDto;
        }
        return Mono.just(data);
    } catch (Exception e) {
        log.error("error is : {}", e.getMessage());
        return Mono.error(e);
    }
}

public void createCurrentStocksInfo() {
    List<StockCode> stockCodeList = stockCodeRepository.findAll();


    HttpHeaders header = createHeaders();


    stocksInfoRepository.deleteAll() // DB 내용 삭제하기 위해 구성
            .thenMany(Flux.fromIterable(stockCodeList))
            .delayElements(Duration.ofMillis(500))
            .flatMapSequential(code -> webClient.get()
                            .uri(uriBuilder -> uriBuilder.path("/uapi/domestic-stock/v1/quotations/inquire-price")
                                    .queryParam("FID_COND_MRKT_DIV_CODE", "J")
                                    .queryParam("FID_INPUT_ISCD", code.getCode())
                                    .build())

                            .headers(httpHeaders -> httpHeaders.addAll(header))
                            .retrieve()
                            .bodyToMono(String.class)
                            .flatMap(response -> parsingCurrentInfo(response))
                            .flatMap(responseDto -> saveToDb(responseDto))
                    , 100)
            .subscribe(
                    result -> log.info("Saved Result : {}", result),
                    error -> log.error("Error : {}", error.getMessage()),
                    () -> log.info("All stocks processed")
            );
}

private Mono<StockInfo> saveToDb(ResponseCurrentOutputDto dto) {

    StockInfo entity = dto.toEntity();
    Mono<StockInfo> savedStockInfo = stocksInfoRepository.save(entity);
    return savedStockInfo;
}

https://www.acmicpc.net/problem/10282

문제 요약

컴퓨터가 의존할 때 특정 컴퓨터에 감염이 발생하여 그로 인해 감염되는 컴퓨터의 총 개수와 시간을 알아야 한다.

접근

컴퓨터는 단방향으로만 의존한다. 거기에 감염되는 시간 즉, 비용이 발생하게 된다. 감염되는 총 시간을 구해야한다. 시작 컴퓨터에서 어디까지 얼마나 감염되는 지를 빠르게 확인하게 된다는 점에서 최단 경로 알고리즘을 이용하게 된다.

1. 거리를 나타내는 dist배열 초기화
2. 시작 컴퓨터를 방문할 수 있도록 처리
3. 방문 가능한 컴퓨터 중 가장 가까이 있는 컴퓨터로 방문
4. 현재 컴퓨터와 인접한 컴퓨터 방문(감염되기에)
5. 최단거리인지 확인

// 해킹 10282

import java.io.*;
import java.util.*;

public class Main {

    public static class Edge implements Comparable<Edge> {

        // cost를 기준으로 우선순위 큐 되도록 구성
        int end, cost;
        Edge(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge edge) {
            return this.cost - edge.cost;
        }
    }


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        for (int z = 0; z < t; z++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int D = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            List<Edge>[] adj = new ArrayList[N+3];

            for (int i = 0; i < N+3; i++) {
                adj[i] = new ArrayList<>(); // 인접 리스트로 구성
            }

            for (int i = 0; i < D; i++) {
                st = new StringTokenizer(br.readLine());
                int end = Integer.parseInt(st.nextToken());
                int start = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());

                adj[start].add(new Edge(end, cost));
            }

            int[] dist = new int[N+3];
            Arrays.fill(dist, Integer.MAX_VALUE); // dist 배열을 큰 값으로 초기화

            PriorityQueue<Edge> pq = new PriorityQueue<>();
            pq.add(new Edge(C, 0)); // 시작 컴퓨터(감염된 컴퓨터)를 방문할 수 있도록

            int cnt = 0;
            while (!pq.isEmpty()) {
                Edge cur = pq.poll();

                if(dist[cur.end] <= cur.cost) continue; // 시간(비용)이 더 적거나 같으면 pass
                dist[cur.end] = cur.cost; // 갱신
                cnt++;

                for (Edge nxt : adj[cur.end]) { // 현재 컴퓨터와 인접한 컴퓨터들 방문(감염)
                    if (dist[nxt.end] <= cur.cost + nxt.cost) continue; // 이미 더 빠르게 감염되었다면 패스
                    pq.add(new Edge(nxt.end, cur.cost + nxt.cost));

                }
            }

            long max_num = 0;
            for (int i = 1; i <= N; i++) {
                if (dist[i] != Integer.MAX_VALUE && dist[i] > max_num) max_num = dist[i];
            }

            System.out.println(cnt + " " + max_num);

        }
    }
}

관련 링크 : https://apiportal.koreainvestment.com/apiservice-apiservice?/uapi/domestic-stock/v1/quotations/inquire-price

문서를 보면 Request, Response 관련 정보가 나와있고 특정 주식 관련 정보를 반환하기 위해 자바 코드를 이용해 구성하였다.

** 컨트롤러 **

** 서비스 ** 헤더 설정 -> 한국투자증권 uri 설정과 queryParam 설정 -> 시세 세부 정보 응답

output 관련 dto는 api 문서에 맞춰 작성하였다. 모든 작성을 마친 후 돌려보니 NullpointerException 발생

API에서 가져온 주식 정보가 Node에 담기는 데 거기에 NULL 정보가 있다고 한다. (분명 ouput 정보를 API 문서 맞게 적었는데...)

log를 찍어 확인해보니 API 문서에 반환해준다는 필드가 없었다.

API 문서에서 반환해준다는 필드를 dto에서 빼고 싶진 않아서 JsonNode에 대해 더 알아보니 get을 대체할 수 있는 path가 존재하였다. https://yeonyeon.tistory.com/136

따라서 path는 NULL이 아닌 MissingNode를 반환한다.

pat를 이용해 NullPointerException을 피함으로써 제대로 된 결과값을 얻었다.

• 사진처럼 token이 발급되면 이를 이용해 로그인하는 것

• access token으로 로그인을 하고 다른 API를 호출 시 401 에러 발생

찾아보니 인증을 처리하는 SecurityFilerChain 부분에서 오류가 발생한 것

• Security Config 다시 확인

• 당연하게도 jwtFilter를 filterChain에 추가하지 않았고 요청에서 검증 작업이 이루어지지 않아 인증이 안 된 상태로 넘어간 것

• jwtFilter() 추가하니 정상 작동하게 됨

CD 과정에서 다음과 같은 에러 발생하였다. (사진에서 argument 주지 않은 에러는 제외) err: permission denied while trying to connect to the Docker daemon socket at unix...

해결 방안

배포한 EC2에서 docker를 실행할 권한이 없기에 에러 발생하였다. 찾아보니 EC2 사용자(현재 ubuntu)를 docker 그룹에 추가 하는 게 베스트

sudo usermod -aG docker ubuntu

위 처럼 사용자(ubuntu)에 권한을 주고

sudo systemctl restart docker

재시작한 후 도커 컨테이너를 다시 실행시키면 통과된다.

다른 방안

배포관련 yml 파일의 script 부분을 sudo를 붙여서 진행 하는 것도 방법이 될 듯 하다.