no image
[MySQL] NULL 처리 함수 (ifnull, coalesce, nullif, if, case when ... then... end)
SQL에서 NULL을 다른 값으로 치환하거나, NULL 여부를 판단하는 방식이 많이 쓰인다. 다시 한번 정리하고자 한다. IFNULL()값이 NULL일 때 대체 값을 반환한다.IFNULL(expression, value_if_null) expression : null 여부를 검사할 값value_if_null : expression이 null 일 때 대신 반환할 값 => expression이 null이면 대체값을 반환하고, null이 아니면 그대로 반환한다! 예시SELECT IFNULL(NULL, 'NONE'); -- 'NONE'SELECT IFNULL(5, 6); -- 5SELECT IFNULL(5/0, '..
2025.11.20
no image
[MySQL] JOIN (INNER JOIN, OUTER JOIN)
JOIN- 2개 이상 테이블에서 연관된 데이터를 결합하여 조회할 때 사용- 여러 테이블을 join하면 각 테이블의 데이터를 공통 컬럼 기준으로 연결해 하나의 결과로 반환한다.- INNER JOIN / LEFT OUTER JOIN / RIGHT OUTER JOIN으로 구분된다. INNER JOIN- 두 테이블에서 모두 일치하는 행만 반환한다!SELECT columnsFROM 테이블1INNER JOIN 테이블2ON 테이블1.column = 테이블2.column; 위 예시에서, 양 테이블의 데이터 중 ON 절의 조건에 맞는 교집합만 결과로 반환한다.조건에 맞지 않은 행은 제외한다.만약, ON절이 없이 INNER JOIN만 있으면, 모든 행을 서로 곱한 결과 즉 카타시안 곱을 만든다! LEFT OUTER..
2025.11.16
no image
[MySQL] 집계함수 (ROUND, COUNT)
ROUND 함수숫자를 지정한 소수점 자리수로 반올림해 반환하는 함수자릿수를 지정하지 않으면 정수로 반올림해준다. ROUND(숫자, 자릿수) 이 때,자릿수를 생략하면 0의 자릿수 즉 정수 단위로 반올림한다. ( 2-> 소숫점 둘째 자리까지)자릿수가 양수이면 소수점 이하 기준으로 반올림한다.자리수가 음수이면 소수점 왼쪽 자릿수를 기준으로 반올림한다. (-2 -> 100의 자리까지 반올림) mysql> SELECT ROUND(125.315);-- 결과: 125mysql> SELECT ROUND(125.315, 0);-- 결과: 125mysql> SELECT ROUND(125.315, 1);-- 결과: 125.3mysql> SELECT ROUND(125.315, 2);-- 결과: 125.32mysql> SEL..
2025.11.12
no image
[MySQL] GROUP BY
GROUP BY절이란여러 행의 데이터를 집계할 때, 하나 이상의 컬럼을 기준으로 그룹화할 때 사용.동일한 값을 가진 행들을 묶어 중복을 제거한다.집계함수와 함께 사용하여 어떤 통계치를 낼 때 사용한다. SELECT 컬럼명1, 컬럼명2, ...., 집계함수(컬럼명)FROM 테이블명GROUP BY (컬럼명1, 컬럼명2,...); 여기서 유의해야할 규칙은, SELECT에 명시된 컬럼들 중집계함수 (MAX, COUNT, AVG 등)안에 들어가지 않는 컬럼명은 전부 GROUP BY절에 명시해야 한다는 것이다. 집계하지 않을 컬럼을 SELECT에 명시해놓고 GROUP BY로 묶지 않는다면, MySQL 입장에서는 헷갈리기 떄문이다. 예를 들어 부서 별 평균 연봉을 구하고자 하는데, SELECT 부서, 성별, AVG..
2025.11.11
no image
프로그래머스: 호텔 방 배정[레벨 4] / Java
프로그래머스: 호텔 방 배정https://school.programmers.co.kr/learn/courses/30/lessons/64063 문제 설명한 고객이 원하는 방 번호가 이미 배정되어 있다면,해당 방 번호보다 큰 방 중 비어 있는 가장 가까운(작은) 번호의 방을 찾아 배정해야 한다.각 고객은 한 번씩만 방문하고, 방의 개수는 매우 크기 때문에(최대 10¹²) 효율적인 탐색이 필요하다.1차 시도 (오답)보자마자 유니온-파인드 방식을 사용하려 했지만, k값이 10의 12제곱으로 매우 커 배열로 관리하기는 힘들어 보였다.그래서 HashMap을 사용해 필요한 방 번호만 활성화해 관리하고자 했다. import java.util.*;class Solution { public long[] soluti..
2025.11.11
no image
백준 17143: 낚시왕[Gold 1] / Java
백준 17143: 낚시왕https://www.acmicpc.net/problem/17143문제 설명R×C 격자 위에 여러 마리의 상어가 있다.상어는 각각 속도(s), 방향(d), 크기(z)를 가지고 있으며, 낚시왕은 1열부터 오른쪽으로 한 칸씩 이동하면서 가장 가까운 상어를 낚고, 이후 모든 상어가 동시에 이동한다.같은 칸에 여러 상어가 도착하면 가장 큰 상어만 살아남는다. 1차 시도 (오답)import java.io.*;import java.util.*;public class Main { // 상하우좌 static int[] dr = {0, -1, 1, 0, 0}; static int[] dc = {0, 0, 0, 1, -1}; static class Shark { int r, c, s, d, z; ..
2025.10.24
no image
백준 1918: 후위표기식[Gold 2] / Java
백준 1918: 후위 표기식https://www.acmicpc.net/problem/1918문제 설명중위 표기식(예: A+B*C)을 후위 표기식(예: ABC*+)으로 바꾸는 문제다. 연산자의 우선순위와 괄호 구조를 고려해 후위표기식으로 만들어야 한다. 처음 접근 방식처음엔 “연산자 스택”과 “괄호 처리를 위한 임시 스택” 두 개를 만들어서 닫는 괄호가 나올 때마다 여는 괄호가 나올 때까지 임시 저장 후 한꺼번에 출력하는 방식으로 접근했다. - 연산자 스택: +, -, *, / 저장 - 임시 스택: 괄호 내부의 피연산자와 연산자 임시 보관 - 여는 괄호 개수를 세기 위해 cnt 사용 이 방식으로 구현했을 때, 괄호 내부를 처리할 때는 정상적으로 작동했지만 괄호 밖의 우선순위 ..
2025.10.21
no image
백준 1865: 웜홀[Gold 3] / Java
백준 1865: 웜홀https://www.acmicpc.net/problem/1865문제 설명N개의 지점과 M개의 도로, W개의 웜홀이 있다.도로는 양방향, 웜홀은 단방향이며, 웜홀을 지나면 시간이 거꾸로 흐른다.즉, 웜홀의 가중치는 음수로 표현된다.이때, 그래프 어딘가에 “시간이 줄어드는 순환 경로(음수 사이클)” 가 존재한다면“YES”를, 그렇지 않다면 “NO”를 출력해야 한다.처음 접근: BFS 탐색문제에서 “시간을 되돌리는 웜홀”이라는 문장을 보고 처음엔 단순하게 생각했다.“모든 지점을 BFS로 돌면서, 시간이 줄어드는 루프가 생기는지 찾아보면 되지 않을까?”그래서 처음 시도는 이렇게 했다:도로와 웜홀을 각각 리스트로 분리해서 관리 (List roads, List wormholes)각 지점을 시..
2025.10.19
no image
정렬 알고리즘
선택정렬처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞 데이터와 바꾸는 것.가장 작은 수를 찾기 위해 매번 N번의 순회O(N2) ← N+(N-1)+….+2 = (N2+N-2)/2 private static void selectSort(int[] w) { // 정렬 시작지점 for (int i = 0; i w[j]) { minIdx = j; } } swap(i, minIdx, w); } } 삽입 정렬처리되지 않은 데이터를 하나씩 골라 앞 수와 비교해 바꿔가며 적절한 위치에 삽입평균 시간복잡도: O(N2)기존 배열이 거의 정렬되어 있을수록 빠르게 동작 ⇒ 최선의 경우 O(N) private static void insertSort(int[] w) { // 정렬 대상 ..
2025.10.17
no image
[Infra] Docker, Docker-compose 설치하는 법 (Ubuntu)
시스템 업데이트 sudo apt updatesudo : 관리자 권한으로 실행apt update : 최신 패키지 업데이트 사전 필수 패키지 설치 sudo apt install -y apt-transport-https ca-certificates curl software-properties-common 패키지ca-certificates : 서버가 HTTPS 통신할 때 필요한 공인 인증서들을 모아둔 패키지. 인증된 사이트(예: Docker 저장소)에 안전하게 연결하기 위해 필요.curl: 명령어로 인터넷 서버에서 파일을 다운로드하거나 요청을 보낼 수 있는 툴. Docker GPG 키나 설치 스크립트를 다운로드할 때 사용.gnupg: 소프트웨어 설치 시 신뢰할 수 있는지 검증하는 "전자 서명" 기능을..
2025.10.04

 

 

 

SQL에서 NULL을 다른 값으로 치환하거나, NULL 여부를 판단하는 방식이 많이 쓰인다.

 

 

 

 

다시 한번 정리하고자 한다.

 

IFNULL()

값이 NULL일 때 대체 값을 반환한다.

IFNULL(expression, value_if_null)

 

expression : null 여부를 검사할 값

value_if_null : expression이 null 일 때 대신 반환할 값

 

=> expression이 null이면 대체값을 반환하고, null이 아니면 그대로 반환한다!

 

예시

SELECT IFNULL(NULL, 'NONE');               		 -- 'NONE'
SELECT IFNULL(5, 6);                                    -- 5
SELECT IFNULL(5/0, 'Dividing by 0 returns NULL');        -- 'Dividing by 0 returns NULL'

 

 

COALESCE()

여러 값 중 첫 번째 NULL이 아닌 값을 반환

COALESCE(expression1, expression2, ..., expression_n)

 

왼쪽부터 순서대로 검사하여 첫 번째 NULL이 아닌 값을 반환한다.

만약 모든 인자가 NULL이면 NULL을 반환한다.

 

예시

SELECT COALESCE(NULL, NULL, 'A', 'B');                -- 'A'
SELECT COALESCE('A', 'B', NULL, 'C');                 -- 'A'
SELECT COALESCE(NULL, 1, 2, 3);                       -- 1
SELECT COALESCE(NULL, 'NONE', 'backup');  		-- 'NONE'
SELECT COALESCE(NULL, NULL, NULL);                    -- NULL

 

 

NULLIF

두 값이 같으면 NULL을, 다르면 첫 번째 값을 반환

NULLIF(expression1, expression2)

 

 

예시

SELECT NULLIF('A', 'A');             -- NULL
SELECT NULLIF('A', 'B');             -- 'A'
SELECT NULLIF(5, 5);                 -- NULL
SELECT NULLIF(5, 6);                 -- 5

 

 

 

IF

조건식이 참인지 거짓인지에 따라 다른 값을 반환

IF(condition, value_if_true, value_if_false)

 

condition : 조건식

value_if_true : 조건식이 참일 때 반환할 값

value_if_false : 조건식이 거짓일 때 반환할 값

 

예시

SELECT IF(100 < 200, 'yes', 'no');  
-- 결과: 'yes'
SELECT IF(STRCMP('A','B')=0, 'same', 'different');  
-- 결과: 'different'
SELECT IF(100 < 200, 5000, 6000);  
-- 결과: 5000

 

 

CASE WHEN ... THEN ... ELSE ... END

여러 조건을 순서대로 판단하고,
처음으로 TRUE가 되는 조건의 결과(result) 를 반환한다.
조건이 하나도 만족하지 않으면 ELSE절의 값을 반환하고,
ELSE가 없으면 NULL을 반환한다.

CASE [expression]
    WHEN condition_1 THEN result_1
    WHEN condition_2 THEN result_2
    ...
    WHEN condition_n THEN result_n
    ELSE result
END

 

만약 expression이 있다면, 해당 컬럼의 값을 조건에 따라 분기하는 것이고,

expression이 없이 그냥 주어진다면, 여러 컬럼을 조건으로 걸 수 있어 유연하게 사용 가능하다.

 

예시

SELECT name, score, age,
CASE
  WHEN score >= 90 THEN 'High'
  WHEN score >= 80 AND age < 20 THEN 'Rising'
  WHEN age > 40 THEN 'Senior'
  ELSE 'Normal'
END AS level
FROM students;

expression이 없기에, score와 age 등 여러 컬럼을 조건에 따라 분기처리했다. 

 

 

 

프로그래머스 예제

12세 이하인 여자 환자 목록 출력하기

PATIENT 테이블에서 12세 이하인 여자환자의 환자이름, 환자번호, 성별코드, 나이, 전화번호를 조회하는 SQL문을 작성해주세요. 이때 전화번호가 없는 경우, 'NONE'으로 출력시켜 주시고 결과는 나이를 기준으로 내림차순 정렬하고, 나이 같다면 환자이름을 기준으로 오름차순 정렬해주세요.

 

SELECT COALESCE(TLNO, 'NONE'), IFNULL(TLNO, 'NONE'), IF(TLNO IS NULL, 'NONE', TLNO),
    CASE
    WHEN TLNO IS NULL THEN 'NONE'
    ELSE TLNO
    END AS TLNO
FROM PATIENT
WHERE AGE<=12 AND GEND_CD='W'
ORDER BY AGE DESC, PT_NAME;

위와 같이 SQL문을 짜면 어떻게 나올까??

 

모두 NULL 처리가 잘 됐다!

[MySQL] JOIN (INNER JOIN, OUTER JOIN)

친환경 개발자
|2025. 11. 16. 23:57

 

JOIN

- 2개 이상 테이블에서 연관된 데이터를 결합하여 조회할 때 사용

- 여러 테이블을 join하면 각 테이블의 데이터를 공통 컬럼 기준으로 연결해 하나의 결과로 반환한다.

- INNER JOIN / LEFT OUTER JOIN / RIGHT OUTER JOIN으로 구분된다.

 

 

 

INNER JOIN

- 두 테이블에서 모두 일치하는 행만 반환한다!

SELECT columns
FROM 테이블1
INNER JOIN 테이블2
ON 테이블1.column = 테이블2.column;

 

위 예시에서, 양 테이블의 데이터 중 ON 절의 조건에 맞는 교집합만 결과로 반환한다.

조건에 맞지 않은 행은 제외한다.

만약, ON절이 없이 INNER JOIN만 있으면, 모든 행을 서로 곱한 결과 즉 카타시안 곱을 만든다!

 

 

 

LEFT OUTER JOIN

- 왼쪽 테이블의 모든 행을 포함하고, 오른쪽 테이블과 일치하는 행만 결합한다.

SELECT columns
FROM 테이블1
LEFT [OUTER] JOIN 테이블2
ON 테이블1.column = 테이블2.column;

 

 

왼쪽 테이블(테이블1)의 모든 행을 가져오고, 오른쪽(테이블2)의 컬럼 값은 일치하는 값이 없으면 결과에 NULL이 들어간다.

 

즉, 왼쪽 기준의 전체 데이터 + 교집합.

 

 

 

RIGHT OUTER JOIN

- 왼쪽 테이블의 모든 행을 포함하고, 오른쪽 테이블과 일치하는 행만 결합한다.

SELECT columns
FROM 테이블1
RIGHT [OUTER] JOIN 테이블2
ON 테이블1.column = 테이블2.column;

 

오른쪽 테이블(테이블1)의 모든 행을 가져오고, 왼쪽(테이블2)의 컬럼 값은 일치하는 값이 없으면 결과에 NULL이 들어간다.

 

즉, 오른쪽 기준의 전체 데이터 + 교집합.

[MySQL] 집계함수 (ROUND, COUNT)

친환경 개발자
|2025. 11. 12. 22:14

 

 

ROUND 함수

숫자를 지정한 소수점 자리수로 반올림해 반환하는 함수

자릿수를 지정하지 않으면 정수로 반올림해준다.

 

 

ROUND(숫자, 자릿수)

 

이 때,

자릿수를 생략하면 0의 자릿수 즉 정수 단위로 반올림한다. ( 2-> 소숫점 둘째 자리까지)

자릿수가 양수이면 소수점 이하 기준으로 반올림한다.

자리수가 음수이면 소수점 왼쪽 자릿수를 기준으로 반올림한다. (-2 -> 100의 자리까지 반올림)

 

mysql> SELECT ROUND(125.315);
-- 결과: 125

mysql> SELECT ROUND(125.315, 0);
-- 결과: 125

mysql> SELECT ROUND(125.315, 1);
-- 결과: 125.3

mysql> SELECT ROUND(125.315, 2);
-- 결과: 125.32

mysql> SELECT ROUND(125.315, -1);
-- 결과: 130   (10단위로 반올림)

mysql> SELECT ROUND(125.315, -2);
-- 결과: 100   (100단위로 반올림)

mysql> SELECT ROUND(-125.315);
-- 결과: -125

 

 

 

COUNT 함수

지정된 표현의 개수를 반환한다.

조건을 만족하는 행의 수를 계산할 때 사용한다.

중요한건, 컬럼의 값이 NULL 이면, 카운트하지 않는다

 

SELECT COUNT(표현식)
FROM 테이블명
[WHERE 조건];

 

SELECT 컬럼 1, 컬럼 2, ... 컬럼 n, COUNT(표현식)
FROM 테이블명
[WHERE 조건]
GROUP BY 컬럼 1, 컬럼 2, ... 컬럼 n;

 

COUNT에 들어가지 않는 컬럼은 GROUP BY에 반드시 포함해야 한다.

 

[MySQL] GROUP BY

친환경 개발자
|2025. 11. 11. 17:36

 

GROUP BY절이란

여러 행의 데이터를 집계할 때, 하나 이상의 컬럼을 기준으로 그룹화할 때 사용.

동일한 값을 가진 행들을 묶어 중복을 제거한다.

집계함수와 함께 사용하여 어떤 통계치를 낼 때 사용한다.

 

 

SELECT 컬럼명1, 컬럼명2, ...., 집계함수(컬럼명)
FROM 테이블명
GROUP BY (컬럼명1, 컬럼명2,...);

 

여기서 유의해야할 규칙은,

 

SELECT에 명시된 컬럼들 중

집계함수 (MAX, COUNT, AVG 등)안에 들어가지 않는 컬럼명은 전부 GROUP BY절에 명시해야 한다는 것이다.

 

집계하지 않을 컬럼을 SELECT에 명시해놓고 GROUP BY로 묶지 않는다면,

 

MySQL 입장에서는 헷갈리기 떄문이다.

 

예를 들어 부서 별 평균 연봉을 구하고자 하는데,

 

SELECT 부서, 성별, AVG(연봉)
FROM 직원테이블
GROUP BY 부서;


라고 성별을 추가해버리면,

 

중복된 부서를 전부 그룹화 했을 때 성별이 남자 여자 모두 합쳐졌을 것 아닌가.

 

그럼 MySQL은 남자라고 표시해야할 지 여자라고 표시해야할 지 헷갈릴 것이다.

 

그러니 올바른 쿼리문은 조건에 따라 아래 둘 중 하나이다.

 

 

-- 부서별, 성별별 평균 연봉을 구할 때
SELECT 부서, 성별, AVG(연봉)
FROM 직원테이블
GROUP BY 부서, 성별;
-- 부서별 평균 연봉을 구할 때
SELECT 부서, AVG(연봉)
FROM 직원테이블
GROUP BY 부서;

 

 

여기서 조건을 걸고 싶으면 (예를 들면 성별이 남자인 직원들의 부서별 평균 연봉)

 

HAVING을 사용하면 된다.

 

-- 부서별, 성별별 평균 연봉을 구하되, 각 부서별 성별별 최소 연봉이 150보다 큰 그룹만 표시하도록.
SELECT 부서, 성별, AVG(연봉)
FROM 직원테이블
GROUP BY 부서, 성별
HAVING MIN(연봉)>150;

 

 

 

 

프로그래머스: 호텔 방 배정

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

 

 

문제 설명

한 고객이 원하는 방 번호가 이미 배정되어 있다면,

해당 방 번호보다 큰 방 중 비어 있는 가장 가까운(작은) 번호의 방을 찾아 배정해야 한다.
각 고객은 한 번씩만 방문하고, 방의 개수는 매우 크기 때문에(최대 10¹²) 효율적인 탐색이 필요하다.


1차 시도 (오답)

보자마자 유니온-파인드 방식을 사용하려 했지만, k값이 10의 12제곱으로 매우 커 배열로 관리하기는 힘들어 보였다.

그래서 HashMap을 사용해 필요한 방 번호만 활성화해 관리하고자 했다.

 

import java.util.*;

class Solution {
    public long[] solution(long k, long[] room_number) {
        int size = room_number.length;
        long[] answer = new long[size];
        
        Map<Long, Long> rooms = new HashMap<>();
        Map<Long, ArrayList<Long>> waitings = new HashMap<>();
        
        int idx = 0;
        for (long num : room_number) {
            
            if (rooms.get(num) == null) { // 미배정
                answer[idx++] = num;
                long nextRoom = num + 1;
                
                if (rooms.get(nextRoom) == null)
                    rooms.put(num, nextRoom);
                else
                    rooms.put(num, rooms.get(nextRoom));
                
                if (waitings.get(nextRoom) == null)
                    waitings.put(nextRoom, new ArrayList<>());
                waitings.get(nextRoom).add(num);

                if (waitings.get(num) != null) {
                    for (long w : waitings.get(num)) {
                        rooms.put(w, nextRoom);
                        waitings.get(nextRoom).add(w);
                    }
                    waitings.get(num).clear();
                }
                continue;
            }

            answer[idx++] = rooms.get(num);
            long nextRoom = rooms.get(num) + 1;
            
            if (rooms.get(nextRoom) == null)
                rooms.put(num, nextRoom);
            else
                rooms.put(num, rooms.get(nextRoom));
        }
        return answer;
    }
}

 

 

  • rooms: key=방번호, value=가장 가까운 다음 방번호
  • waitings: key = 방번호, value= 해당 방을 가리키고 있는 다른 방들의 리스트

방 배정 관계를 연결 리스트처럼 갱신하는 접근이었다.
배정된 방 번호를 key로, 다음 후보 방 번호를 value로 두면 된다 생각했다.

 

그러나 실제로 돌려보니 중복 배정이 발생하거나, 방 번호가 꼬이는 현상이 있었다.

  1. rooms.put(num, nextRoom)만 갱신 → 요청 번호 기준으로만 갱신됨
    • 실제로 배정된 방 번호가 아니라 “희망 번호”를 기준으로 갱신해서 체인 구조가 끊기거나 잘못 연결됨.
  2. 과도한 복잡성
    • waitings 리스트를 매번 돌며 일괄 갱신하다보니 너무 많은 갱신이 필요해 최악의 경우 O(N²)로 커졌고,
      코드를 작성하는 것도 너무 복잡했다.

2차 시도 (성공)

import java.util.*;

class Solution {
    public long[] solution(long k, long[] room_number) {
        int size = room_number.length;
        long[] answer = new long[size];
        int idx = 0;
        Map<Long, Long> p = new HashMap<Long, Long>();
        
        for (long r : room_number) {
            long assigned = find(r,p);
            answer[idx++] = assigned;
            p.put(assigned, find(assigned+1,p));
        }
        
        return answer;
    }
    public long find(long x, Map<Long, Long> p) {
        if (p.get(x)== null) {
            return x;
        }
        long parent = find(p.get(x), p);
        p.put(x, parent);
        return parent;
    }
}

 

union-find 방식이 맞았다.

 

parent배열을 관리할 때, 배열로 관리하지 않고 Map으로 관리하면 되었다.

 

나는 find메서드를 호출할 때 최대 20만개의 방이 있을 수 있으니 스택오버플로우가 발생할거라 생각했다.

 

하지만 실제로 구현해보니 발생하지 않았다. 테스트케이스가 그렇게까지 극한으로 가진 않은 모양이다.

 

만약 테스트케이스가 [1, 1, 1, 1, .....] 이렇게 20만 개짜리 배열이 들어온다면,

 

1 > 2> 3> 4> .... > 200000

 

까지 경로 압출 없이 스택을 타고 들어가 스택오버플로우가 발생할 수 있을 것이다.

 

이를 해결하려면, 스택 대신 while문으로 구현해야할 것 같다.

 

회고

처음엔 단순히 HashMap으로 방 배정 상태를 추적하면 될 줄 알았다.
하지만 이 문제의 본질은 다음 비어있는 노드를 효율적으로 찾는 연결 관계를 만드는 것이다.

불필요한 리스트 관리보다 경로 압축 기반 union-find탐색이 훨씬 명확하고 빠르다.

 

결론은 너무 복잡하게 생각하지 말자..

 

 

 

 

백준 17143: 낚시왕
https://www.acmicpc.net/problem/17143

문제 설명

R×C 격자 위에 여러 마리의 상어가 있다.
상어는 각각 속도(s), 방향(d), 크기(z)를 가지고 있으며, 낚시왕은 1열부터 오른쪽으로 한 칸씩 이동하면서 가장 가까운 상어를 낚고, 이후 모든 상어가 동시에 이동한다.
같은 칸에 여러 상어가 도착하면 가장 큰 상어만 살아남는다.

 


1차 시도 (오답)

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

public class Main {
	// 상하우좌
	static int[] dr = {0, -1, 1, 0, 0};
	static int[] dc = {0, 0, 0, 1, -1};
	static class Shark {
		int r, c, s, d, z;
		boolean isAlive;
		public Shark(int r, int c, int s, int d, int z) {
			super();
			this.r = r;
			this.c = c;
			this.s = s;
			this.d = d;
			this.z = z;
			this.isAlive = true;
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[R+1][C+1];
		Shark[] sharks = new Shark[M+1];
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken()); // 속도
			int d = Integer.parseInt(st.nextToken()); // 방향
			int z = Integer.parseInt(st.nextToken()); // 크기
			
			sharks[i] = new Shark(r, c, s, d, z);
			map[r][c] = i;
		}
		
		int ans = 0;
		for (int c=1; c<=C; c++) {
			// 낚시
			for (int r=1; r<=R; r++) {
				if (map[r][c] > 0) {
					ans += sharks[map[r][c]].z;
					sharks[map[r][c]].isAlive = false;
					map[r][c] = 0;
					break;
				}
			}
			
			// 상어 이동
			for (int i=1; i<=M; i++) {
				Shark s = sharks[i];
				if (!s.isAlive) continue;
				// 이동 위치 계산
				int nr = s.r + dr[s.d]*s.s;
				int nc = s.c + dc[s.d]*s.s;
				
				while (nr<1 || nr >R || nc<1 || nc>C) {
					if (nr<1) {
						nr = 1+(1-nr);
						s.d = 2;
					}
					else if (nr>R) {
						nr = R-(nr-R);
						s.d = 1;
					}
					else if (nc<1) {
						nc = 1+(1-nc);
						s.d = 3;
					}
					else if (nc>C) {
						nc = C-(nc-C);
						s.d = 4;
					}
				}
				
				// 겹치는지 확인
				if (map[nr][nc] == 0) {
					if (map[s.r][s.c] == i) map[s.r][s.c] = 0;
					s.r = nr;
					s.c = nc;
					map[nr][nc] = i;
				} else {
					// 이미 이동 마친 상어면 진짜 있는거니까 크기 비교
					if (map[nr][nc] < i) {
						int winner = 0;
						int loser = 0;
						if (s.z > sharks[map[nr][nc]].z) {
							winner = i;
							loser = map[nr][nc];
						} else {
							winner = map[nr][nc];
							loser = i;
						}
						// 사망 처리
						sharks[loser].isAlive = false;
						// 승자 이동 처리
						if (map[sharks[winner].r][sharks[winner].c] == winner) map[s.r][s.c] = 0;
						sharks[winner].r = nr;
						sharks[winner].c = nc;
						map[nr][nc] = winner;
					}
					// 아니면 그냥 이동해버리기
					else {
						if (map[s.r][s.c] == i) map[s.r][s.c] = 0;
						s.r = nr;
						s.c = nc;
						map[nr][nc] = i;
					}
				}
			}
			
		}
		System.out.println(ans);
	}
}

 

로직

 

  • 초기화
    • 상어마다 위치와 속도·방향·크기를 입력받아 Shark 객체로 관리하고,
      map 배열에는 그 상어의 번호를 기록했다.
    • map[r][c] = i → “i번 상어가 (r, c)에 있다”는 의미.
  • 낚시 단계
    • 낚시꾼이 오른쪽으로 한 칸 이동할 때마다, 해당 열의 가장 위쪽 상어를 잡고 map[r][c] = 0으로 비워준다.
    • 잡힌 상어는 isAlive = false로 표시하고, 크기를 점수에 더한다.
  • 상어 이동 단계
    • for문으로 모든 상어를 순회하며 map배열 기준으로 이동 처리
    • 만약 이동한 칸에 다른 상어가 이미 있으면, 이동 처리한 상어면 그 자리에서 즉시 크기 비교해 큰 상어만 남겼다.
    • 이동 처리하지 않은 상어면 그냥 무시하고 이동시켰다

 

 

 

문제는 이동 단계에서 발생했다.

이동 중인 상어가 이미 map을 갱신한 상어의 흔적을 보고 움직이게 된다.

즉, 모든 상어가 동시에 이동해야 하는데, 실제로는 이전 상어의 이동 결과를 보면서 순차 이동하게 되는 구조다. 따라서 같은 입력이라도 “이동 순서”에 따라 결과가 달라질 수 있고,
문제의 요구사항인 **‘동시 이동 후 충돌 판정’**이 깨져버린다.

처음에는 단순하게 map 하나로 모든 단계를 처리하려 했다.
map에 상어 번호를 저장해두고, 낚시 → 이동 → 충돌 처리를 모두 같은 배열에서 진행했다.
이 방식의 장점은 구현이 직관적이라는 점이었지만,
곧 “동시 이동”이라는 조건에서 큰 문제가 생겼다.

  1. 낚시 시점에서 map[r][c] = 0을 먼저 해서 NPE 발생
  2. 상어가 “동시에” 이동하지 않고 순차적으로 map을 덮어씀
  3. 결과적으로 같은 칸에 도착한 상어의 크기 비교가 불완전함

 

2차 시도 (성공)

1차에서 가장 큰 문제였던 “동시 이동 처리”를 해결하기 위해
새로운 맵(newMap)을 만들어 이동 결과를 저장하도록 수정했다.

이후 이동이 모두 끝나면 map = newMap으로 갱신하도록 했다.

		for (int c = 1; c <= C; c++) 
        	// 동시 이동 처리를 위한 map 생성
			int[][] newMap = new int[R + 1][C + 1];
            
			// 상어 이동
			for (int i = 1; i <= M; i++) {
				Shark s = sharks[i];
				if (!s.isAlive)
					continue;
				// 이동 위치 계산
				int nr = s.r + dr[s.d] * s.s;
				int nc = s.c + dc[s.d] * s.s;

				while (nr < 1 || nr > R || nc < 1 || nc > C) {
					if (nr < 1) {
						nr = 1 + (1 - nr);
						s.d = 2;
					} else if (nr > R) {
						nr = R - (nr - R);
						s.d = 1;
					} else if (nc < 1) {
						nc = 1 + (1 - nc);
						s.d = 3;
					} else if (nc > C) {
						nc = C - (nc - C);
						s.d = 4;
					}
				}

				// 겹치는지 확인
				if (newMap[nr][nc] == 0) {
					newMap[nr][nc] = i;
					s.r = nr;
					s.c = nc;
				} else {
					int j = newMap[nr][nc];
					if (sharks[j].z > s.z) {
						s.isAlive = false;
					} else {
						newMap[nr][nc] = i;
						sharks[j].isAlive = false;
						s.r = nr;
						s.c = nc;
					}
				}
                
				// map 갱신
				map = newMap;
			}
		}

 

하지만 여전히 아쉬운 점이 있었다.

 

이동 처리 시, 상어의 속도가 매우 크면, 벽에 부딪히며 상하 or 좌우로 지나치게 많이 왔다갔다하게 된다.

 

예를 들어 R=5, s=100이면 1행에 있던 상어가 5행까지 가서 방향 전환, 다시 1행까지 가서 방향 전환, ... 을 수십번 반복해야 한다.

 

이를 개선하기 위해 규칙을 찾아야 했다.

 

 

 

3차 시도 (개선)

결국 규칙을 찾아 속도 s를 축약했다. 간략히 설명하자면,

 

C가 4인 상어의 좌우 이동 과정을 쭉 한 줄로 나열했을 때

1 2 3 4 3 2 1 2 3 4 3 2 1
6 5 <- 4 <- 3 <- 2 <- 1 <- 현재 위치 -> 1 -> 2 -> 3 -> 4 -> 5  6

 

이다. 이 때, 상어가 2의 위치에서 오른쪽이든 왼쪽이든 다시 제자리로 돌아오려면 몇칸을 이동해야 할까?

 

=> 6칸이다!

 

즉 아래와 같이 축약할 수 있다.

 

  • 세로 이동이면 s %= 2*(R-1)
  • 가로 이동이면 s %= 2*(C-1)

이렇게 하면 이동 시 실제 필요한 거리만 계산하므로
시간 복잡도를 줄일 수 있다.

 

입력 시 속도를 축약해 저장해버렸다.

 

		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken()); // 속도
			int d = Integer.parseInt(st.nextToken()); // 방향
			int z = Integer.parseInt(st.nextToken()); // 크기
			
            	// 속도 축약!
			if (d==1 || d==2) {
				s %= 2*(R-1);
			} else {
				s %= 2*(C-1);
			}

			sharks[i] = new Shark(r, c, s, d, z);
			map[r][c] = i;
		}

 

 

결과

결과적으로 2차 시도 대비 3차 시도에서 수행시간을 16% 단축했다!


회고

이 문제는 단순 구현처럼 보여도 “동시 이동 처리”와 “속도 축약”이라는 두 가지 포인트가 있었다.


특히 s가 큰 테스트케이스에서는 시간 초과를 피하려면 왕복 주기 축약이 필요했다.

 

마치 실버 수준 문제가 여러 개 합쳐져 골드 문제가 된 느낌이였다.

 

기본기가 필요함을 느꼈다!

 

 

 

 

 

백준 1918: 후위 표기식
https://www.acmicpc.net/problem/1918

문제 설명

중위 표기식(예: A+B*C)을 후위 표기식(예: ABC*+)으로 바꾸는 문제다.  
연산자의 우선순위와 괄호 구조를 고려해 후위표기식으로 만들어야 한다.

 


처음 접근 방식

처음엔 “연산자 스택”과 “괄호 처리를 위한 임시 스택” 두 개를 만들어서  
닫는 괄호가 나올 때마다 여는 괄호가 나올 때까지 임시 저장 후 한꺼번에 출력하는 방식으로 접근했다.
   
- 연산자 스택: +, -, *, / 저장  
- 임시 스택: 괄호 내부의 피연산자와 연산자 임시 보관  
- 여는 괄호 개수를 세기 위해 cnt 사용  

이 방식으로 구현했을 때,  
괄호 내부를 처리할 때는 정상적으로 작동했지만  
괄호 밖의 우선순위 계산(예: A+B*C)에서 엉뚱한 답이 나왔다.  
즉, 연산자 우선순위를 코드 내에서 직접 비교하지 않으면  
단순히 괄호 단위로만 구분되는 구조였다.

 


개선 ver.

문제를 다시 살펴보면, 사실 이 문제는  
“연산자 우선순위”만 잘 처리하면 괄호 두 개가 필요 없다.

핵심 규칙은 아래와 같다.

1. 피연산자는 바로 출력  
2. 여는 괄호(`(`):는 바로 스택에 push  
3. 닫는 괄호(`)`)는 여는 괄호가 나올 때까지 스택에서 pop → 출력  
4. 연산자(+,-,*,/):  이게 중요하다.
   - 스택의 맨 위 값이 우선순위가 자기보다 높거나 같으면 pop  → 출력  
   - 자기 자신을 스택에 push


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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 연산자를 담을 스택
		Stack<Character> st = new Stack<>();

		// 괄호 처리를 위한 임시 스택
		StringBuilder ans = new StringBuilder();

		char[] inputs = br.readLine().toCharArray();
		for (char c : inputs) {
			// 연산자일 때
			// 후순위 연산자면 여는괄호 나올때까지 모두 pop
			if (c == '+' || c == '-') {
				while (!st.isEmpty() && st.peek() != '(') {
					ans.append(st.pop());
				}
				st.push(c);
			}
			// 우선순위 연산자도 동일 우선순위일 경우 모두 pop
			else if (c == '*' || c == '/') {
				while (!st.isEmpty() && (st.peek() == '*' || st.peek() == '/')) {
					ans.append(st.pop());
				}
				st.push(c);
			} else if (c == '(') {
				st.push(c);
			}
			// 닫는 괄호일 때
			else if (c == ')') {
				// 여는 괄호가 나올 때까지 pop
				while (st.peek() != '(') {
					ans.append(st.pop());
				}
				// 여는 괄호 제거
				st.pop();
			}
			// 피연산자일 땐 바로 ans 저장
			else {
				ans.append(c);
			}
		}
		// 남은것 비우기
		while (!st.isEmpty()) {
			ans.append(st.pop());
		}

		System.out.println(ans);

	}
}

 


개선 과정

1. 스택 2개 →  1개
처음엔 답을 출력할 때 편리함을 위해 피연산자, 연산자를 각각 담아 관리하려 했다. 피연산자는 아예 스택에 담을 필요 없이 바로 출력하면 되는 문제였다.

2. pop 조건   
   처음엔 우선순위보다 높을 때만 고려해 pop했다. 하지만 A/B*C 와 같은 상황에서 AB/C* 가 나와야 하는데 ABC*/ 로 곱하기를 먼저 해버리는 상황이 발생한다. 우선순위가 같아도 앞에 있는 연산자가 우선순위를 가지므로, 같은 경우도 고려해야 한다.

 


회고

- 괄호 처리에 집중하다 보니 연산자 우선순위 처리를 생각하지 못해 시간이 많이 지체됐다.
- 후위표기 방식 자체에 대해 친숙하지 못해 더 오래 걸렸던 것 같다.
- 처음의 방식은 복잡하지만, 이런 시행착오 덕분에 후위표기식에 대한 알고리즘을 확실히 이해했다.

백준 1865: 웜홀[Gold 3] / Java

친환경 개발자
|2025. 10. 19. 17:08

 

 

 

 

백준 1865: 웜홀

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


문제 설명

N개의 지점과 M개의 도로, W개의 웜홀이 있다.
도로는 양방향, 웜홀은 단방향이며, 웜홀을 지나면 시간이 거꾸로 흐른다.
즉, 웜홀의 가중치는 음수로 표현된다.

이때, 그래프 어딘가에 “시간이 줄어드는 순환 경로(음수 사이클)” 가 존재한다면
“YES”를, 그렇지 않다면 “NO”를 출력해야 한다.


처음 접근: BFS 탐색

문제에서 “시간을 되돌리는 웜홀”이라는 문장을 보고 처음엔 단순하게 생각했다.

“모든 지점을 BFS로 돌면서, 시간이 줄어드는 루프가 생기는지 찾아보면 되지 않을까?”

그래서 처음 시도는 이렇게 했다:

  • 도로와 웜홀을 각각 리스트로 분리해서 관리  (List<Node> roads, List<Node> wormholes)
  • 각 지점을 시작점으로 BFS 탐색
  • 시간이 더 짧아지는 경로(times[e] > times[s] + w)를 만나면 음수 사이클이라고 판단

하지만 문제가 생겼다.
BFS는 가중치가 일정하거나 양수일 때만 정상적으로 작동한다.
음수 가중치가 있으면 “방문했어도 다시 돌아가야 하는 경우”가 생기는데,
BFS는 이런 갱신을 반영할 수 없다.

그래서 시간이 과거로 가는 경우 방문했어도 다시 돌아가게끔 하는 방식을 생각했지만,

사이클이 발생했을 때는 무한대로 시간이 과거로 가기 때문에 대응할 수 없었다.


새로운 알고리즘: 벨만포드(Bellman-Ford) 알고리즘

 

이 문제의 핵심은 음수 사이클을 찾는 것이었다.

문제를 다시 읽어보면, 결국 출발점에 다시 되돌아왔을 때 시간이 더 과거이면 되는 것이었고,

결국 무조건 사이클이 발생하는 조건이어야 했다. 그것도 음의 사이클로만 발생해야 하는 것이다.
그 역할을 정확히 수행하는 알고리즘이 바로 벨만포드 알고리즘이다.

 

간략한 구조

  • 다익스트라처럼, dist 배열을 만들어 출발점만 0, 나머진 무한대로 초기화
    (단, 이 문제는 사이클만을 찾아야 하기에 모든 dist를 0으로 만들어야 한다.)
  • 모든 간선을 순회하며 (dist[시작점]이 무한대가 아니면서, dist[시작점] + 가중치 < dist[도착점]) 을 충족하면 값을 갱신하는 행위를 V−1번 반복
  • 사이클을 찾기 위해, 모든 간선 순회를 1번 더 반복한다.
    이 때 dist에 갱신이 일어난다면, 음수 사이클이 존재한다는 뜻이다.

 


코드

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

public class Main {
	public static class Edge {
		int s;
		int e;
		int w;

		public Edge(int s, int e, int w) {
			super();
			this.s = s;
			this.e = e;
			this.w = w;
		}

	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int W = Integer.parseInt(st.nextToken());
			Edge[] edges = new Edge[M * 2 + W];

			List<Edge>[] adjList = new List[N + 1];
			int idx = 0;
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				int w = Integer.parseInt(st.nextToken());
				edges[idx++] = new Edge(s, e, w);
				edges[idx++] = new Edge(e, s, w);
			}
			for (int i = 0; i < W; i++) {
				st = new StringTokenizer(br.readLine());
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				int w = Integer.parseInt(st.nextToken());
				edges[idx++] = new Edge(s, e, -w);
			}

			// 벨만-포드 알고리즘
			System.out.println(bellmanFord(edges, N) ? "YES" : "NO");
		}
	}

	private static boolean bellmanFord(Edge[] edges, int N) {
		int[] dist = new int[N + 1];
		Arrays.fill(dist, 0);

		// 모든 간선을 순회 => N-1번 반복
		// Why? 한 지점에서 다른 지점으로 갈 때 최소 거리는 사이클이 있지 않은 한, 최대 N-1개의 간선을 쓰기 때문
		for (int i = 0; i < N - 1; i++) {
			boolean updated = false;
			for (Edge e : edges) {
				if (dist[e.s] + e.w < dist[e.e]) {
					dist[e.e] = dist[e.s] + e.w;
					updated = true;
				}
			}
			if (!updated)
				break;
		}

		for (Edge e : edges) {
			if (dist[e.s] + e.w < dist[e.e]) {
				return true;
			}
		}

		return false;
	}
}
 

개선 과정

1. 처음엔 모든 정점에서 벨만포드를 실행했다.

  • 각 정점마다 bellmanFord(i) 호출
  • 논리적으로는 맞지만, 시간복잡도 O(V²E) → 시간초과

2. dist 값을 모두 0으로 변경

  • 최단거리를 구하는 게 목적이 아니라, 음수 사이클을 찾는게 목적이다.
  • 따라서 굳이 출발점을 선택해가며 N번 순회할 필요 없이dist를 0으로 하는게 시간복잡도 상 이득이다.
  • 시간복잡도 O(VE) 로 감소 → 통과

3. 조기 종료 최적화

  • 한 라운드에서 갱신이 한 번도 없으면(updated == false),
    모든 최단경로가 확정된 상태이므로 더 돌 필요 없음 → break

배운점

  • BFS는 가중치가 음수일 땐 쓸 수 없다. 사이클에서 막히거나, 방문 체크에서 막힌다..
  • 새로운 벨만 포드 알고리즘에 대해 알게 됐다.
  • 다익스트라와 유사하지만, 음수 가중치일 때 사용할 수 있고, 사이클을 찾고자 할 때에도 사용할 수 있다!
  • 음수 가중치 하나로 알고리즘 자체가 달라져 버린다는 것이 흥미로웠다.

정렬 알고리즘

친환경 개발자
|2025. 10. 17. 16:44

 

선택정렬

  • 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞 데이터와 바꾸는 것.
  • 가장 작은 수를 찾기 위해 매번 N번의 순회
  • O(N2) ← N+(N-1)+….+2 = (N2+N-2)/2
	private static void selectSort(int[] w) {
		// 정렬 시작지점
		for (int i = 0; i < w.length - 1; i++) {
			int minIdx = i;
			// 범위 내 최저값 찾기
			for (int j = i + 1; j < w.length; j++) {
				if (w[minIdx] > w[j]) {
					minIdx = j;
				}
			}
			swap(i, minIdx, w);
		}
	}

 

 

삽입 정렬

  • 처리되지 않은 데이터를 하나씩 골라 앞 수와 비교해 바꿔가며 적절한 위치에 삽입
  • 평균 시간복잡도: O(N2)
  • 기존 배열이 거의 정렬되어 있을수록 빠르게 동작 ⇒ 최선의 경우 O(N)
	private static void insertSort(int[] w) {
		// 정렬 대상 구간 => 첫 인덱스는 정렬된 것으로 보고 인덱스 1부터 시작
		for (int i = 1; i < w.length - 1; i++) {
			// 정렬 대상 원소를 정렬된 구간의 수와 비교하며 삽입
			for (int j = i + 1; j > 0; j--) {
				// 나보다 작은 원소를 만날 때까지 스왑
				if (w[j] < w[j - 1]) {
					swap(j, j - 1, w);
				} else
					break;
			}
		}
	}

 

 

버블정렬

  • 인접한 두 원소를 검사하며 정렬하는 알고리즘
  • 1회전 시 가장 마지막 인덱스에 가장 큰 수가 배치되고, 회전을 거듭할수록 뒤쪽부터 정렬되는 방식
  • 평균 시간복잡도:O(N2)

장점

  • 구현이 매우 간단하다.

단점

  • 위치 교환 과정이 많아 비효율
  • 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
  • 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
	private static void bubbleSort(int[] w) {
		// 뒤쪽부터 정렬됨 -> 정렬 완료된 부분 직전까지만 정렬하도록 제한
		for (int i = w.length - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (w[j] > w[j + 1]) {
					swap(j, j + 1, w);
				}
			}
		}
	}

 

 

퀵 정렬

  • 기준 데이터를 설정하고 그 기준보다 큰 데이터와 자근데이터의 위치를 바꾸는 방법
  • 병합정렬과 더불어 대부분 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
  • 기본 방식은 첫 데이터를 기준데이터(Pivot)로 설정함
  • O(N logN)
  • 최악의 경우 O(N2) → 이미 정렬된 경우
	private static void quickSort(int[] w, int start, int end) {
		if (start >= end) {
			return;
		}
		int pivot = w[start];
		int l = start + 1;
		int r = end;
		while (l <= r) {
			// 왼쪽부터 나보다 큰거 찾기
			while (l <= end && w[l] <= pivot) {
				l += 1;
			}
			// 오른쪽부터 나보다 작은거 찾기
			while (r > start && w[r] >= pivot) {
				r -= 1;
			}
			// l, r 교차하는 순간 피봇과 작은수 위치 스왑
			if (l > r) {
				swap(start, r, w);
             // 교차하지 않으면 l, r만 스왑
			} else
				swap(l, r, w);
		}
		quickSort(w, start, r - 1);
		quickSort(w, r + 1, end);
	}

 

 

 

병합정렬

단점

  • 임시 배열이 필요하다.
  • 제자리 정렬이 아니다.
  • 배열 크기가 큰 경우에는 이동 횟수가 많으므로 비효율 발생한다.

장점

  • 최선과 최악 모두 시간복잡도 O(NlogN)으로, 안정적인 정렬 방법
  • 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
    • 제자리 정렬(in-place sorting)로 구현할 수 있다.
  • 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.
	private static void mergeSort(int[] w, int start, int end) {
		if (start >= end)
			return;

		int mid = (start + end) / 2;
		mergeSort(w, start, mid);
		mergeSort(w, mid + 1, end);

		merge(w, start, mid, end);
	}

	private static void merge(int[] w, int start, int mid, int end) {
		int[] tmp = new int[end - start + 1];
		int l = start;
		int r = mid + 1;
		int tIdx = 0;
		while (l <= mid && r <= end) {
			if (w[l] <= w[r]) {
				tmp[tIdx++] = w[l++];
			} else {
				tmp[tIdx++] = w[r++];
			}
		}
		while (l <= mid) {
			tmp[tIdx++] = w[l++];
		}
		while (r <= end) {
			tmp[tIdx++] = w[r++];
		}

		for (int i = 0; i < tmp.length; i++) {
			w[start + i] = tmp[i];
		}
	}

 

 

 

 

 

시스템 업데이트 

 

sudo apt update
  • sudo : 관리자 권한으로 실행
  • apt update : 최신 패키지 업데이트

 

 

 

사전 필수 패키지 설치

 

sudo apt install -y apt-transport-https ca-certificates curl software-properties-common

 

 패키지

  • ca-certificates : 서버가 HTTPS 통신할 때 필요한 공인 인증서들을 모아둔 패키지. 인증된 사이트(예: Docker 저장소)에 안전하게 연결하기 위해 필요.
  • curl: 명령어로 인터넷 서버에서 파일을 다운로드하거나 요청을 보낼 수 있는 툴. Docker GPG 키나 설치 스크립트를 다운로드할 때 사용.
  • gnupg: 소프트웨어 설치 시 신뢰할 수 있는지 검증하는 "전자 서명" 기능을 제공하는 툴. Docker GPG 키를 확인하고 인증하는 데 필요해.
  • lsb-release: 서버가 어떤 리눅스 배포판 버전인지 (Ubuntu 22.04, 등)을 알려주는 유틸리티. Docker 저장소를 설정할 때 리눅스 버전을 자동으로 가져올 때 필요
  • software-properties-common: APT 저장소를 쉽게 추가하거나 관리하는 명령어(add-apt-repository)를 제공해. Docker 저장소 등록이나 PPA 추가할 때 사용

 

패키지가 설치되어있는지 확인하는 명령어

dpkg -l | grep [패키지명]

 

 

 

Docker 공식 GPG 키 다운로드

sudo mkdir -p /etc/apt/keys
  • -p : 디렉터리가 이미 존재해도 에러 없이 넘어감
curl -fsSL <https://download.docker.com/linux/ubuntu/gpg> | sudo gpg --dearmor -o /usr/share/keyrings/docker-archive-keyring.gpg

: curl -fsSL

  • Docker GPG 키를 다운로드한다.
  • f (실패 시 메시지 표시)
  • s (출력 메시지 숨김)
  • L (리다이렉트를 따라가서 다운로드)

: sudo gpg --dearmor

  • 다운로드한 GPG키를 다운로드 한 GPG 키를 바이너리 형식으로 변환

: -o /usr/share/keystrings/docker-archive-keyring.gpg

  • GPG 키를 저장할 경로를 지정함

 

GPG키란?

  • "파일이 신뢰할 수 있는 출처인지" 확인하는 전자 서명
  • 소프트웨어를 다운로드할 때, 해커가 조작한 파일이 아닌지 검증할 때 사용한다.
  • Docker 설치 시 GPG 키로 패키지의 무결성과 진짜 여부를 확인한다.

 

Docker 저장소 추가

echo "deb [arch=$(dpkg --print-architecture) signed-by=/usr/share/keyrings/docker-archive-keyring.gpg] <https://download.docker.com/linux/ubuntu> $(lsb_release -cs) stable" | sudo tee /etc/apt/sources.list.d/docker.list > /dev/null
  • dpkg --print-architecture: 시스템 아키텍처(예: amd64)를 가져온다
  • signed-by : 위에서 다운 받은 GPG 키 지정
  • lsb_release -cs : 배포판 코드네임(예: jammy)을 가져온다.

 

다시한번 패키지 목록 업데이트

sudo apt update

 

 

 

Docker, Docker compose 설치

sudo apt install -y docker-ce docker-ce-cli containerd.io docker-buildx-plugin docker-compose-plugin
  • docker-ce : Docker 엔진 (Community Edition). 컨테이너를 생성, 실행, 관리하는 핵심 서버 컴포넌트
  • docker-ce-cli: Docker CLI (Command Line Interface). docker run, docker ps 같은 명령어를 제공하는 커맨드 라인 도구
  • containerd.io: Docker 내부에서 컨테이너를 실제로 실행시키는 저수준 런타임. 독립 실행 가능하며 Kubernetes에서도 사용된다.
  • docker-buildx-plugin: 다양한 플랫폼(arm64, amd64 등)과 고급 빌드를 지원하는 Docker 빌드 플러그인. docker buildx build 명령어를 사용 가능하게 한다.
  • docker-compose-plugin: 여러 컨테이너를 정의하고 함께 실행할 수 있게 해주는 Compose 기능을 Docker CLI에 통합한 플러그인. docker compose 명령어 제공