링크: https://www.acmicpc.net/problem/16987

유형: 백트래킹

난이도: 골드5

스스로 풀었는가? ✅

💻 작성 코드

import sys

readline = sys.stdin.readline
eggNum = int(readline())
egg_hps = []
egg_weights = []
answer = 0

def back(cnt):
    global answer
    if cnt == eggNum:
        broken_eggs = [hp for hp in egg_hps if hp <= 0]
        answer = max(answer, len(broken_eggs))
        return

    if egg_hps[cnt] <= 0:
        back(cnt + 1)
    else:
        is_hit = False
        for idx in range(eggNum):
            if egg_hps[idx] > 0 and egg_hps[cnt] > 0 and idx != cnt:
                is_hit = True
                egg_hps[cnt] -= egg_weights[idx]
                egg_hps[idx] -= egg_weights[cnt]
                back(cnt + 1)
                egg_hps[cnt] += egg_weights[idx]
                egg_hps[idx] += egg_weights[cnt]
        if not is_hit:
            back(cnt + 1)

for _ in range(eggNum):
    hp, weight = map(int, readline().split())
    egg_hps.append(hp)
    egg_weights.append(weight)

back(0)
print(answer)

🎯 접근 방식

1. 앞에서부터 계란을 하나씩 든다.
2. 만약 계란이 깨져있다면, 다음 계란으로 넘어간다.
3. 계란이 깨져있지 않다면, 계란 정보를 순회하면서 해당 계란과 부딪힐 수 있는 계란을 하나씩 부딪힌다.
4. 부딪힐 계란이 없다면 다음 계란으로 넘어간다. (현재 들고 있는 계란 빼고 다른 계란이 모두 깨진 경우)
5. 모든 계란을 한번씩 들었다면 깨진 계란의 개수를 센다.

💡 개선사항

1. 튜플이나 이차원 리스트를 이용해 hp와 weigh를 하나의 변수로 관리
2. 들고 있는 계란과 부딪힐 계란이 하나도 없다는 것은, 다른 계란이 모두 깨졌다는 의미이므로 다음 계란이 아니라 바로 조건 카운트로 넘어가도 된다.

문제를 잘 읽자.. 깨려는 계란도 hp > 0이여야 하는 것, 부딪히면 서로 데미지를 받는다는 걸 처음에 생각하지 못했다.

[ktb-algorithm-study] 3주차

백트래킹은 완전 탐색 알고리즘의 일종으로, 재귀를 기반으로 해를 찾는 도중에 해가 아니라고 판단되는 경우 돌아가서 다른 경로를 탐색하는 방식이다. 모든 가능한 경우의 수를 탐색하면서 조건에 맞는 해를 찾지만, 중간에 해당 상태는 정답에 도달할 수 없다고 판단되면 해당 노드부터 하위의 노드를 탐색하지 않는다.

가능한 모든 경우의 수를 탐색하되 정답 가능성이 없는 경로는 더 이상 탐색하지 않고 되돌아간다.

순열을 구하는 백트래킹 의사코드

순열과 조합 알고리즘을 다루면서 백트래킹에 대해 소개한 적이 있다.

# N개의 숫자와 M개의 선택된 숫자로 이루어진 순열을 생성하는 백트래킹 함수
백트래킹(현재 선택된 개수 cnt):
    만약 cnt가 M과 같다면: # 기저 조건 - 순열의 길이가 M
        현재까지 선택된 숫자들을 출력
        반환

    # 가능한 모든 숫자를 탐색
    for i in 0에서 N-1까지:
        만약 i번째 숫자가 아직 선택되지 않았다면:
            i번째 숫자를 선택(방문 표시)
            현재까지 선택된 숫자들에 i번째 숫자를 추가
            백트래킹(cnt + 1)  # 다음 숫자를 선택하기 위해 재귀 호출
            i번째 숫자의 선택을 해제(방문 표시 해제)
            현재까지 선택된 숫자들에서 i번째 숫자를 제거  # 상태를 되돌림

# 초기 상태로부터 백트래킹 시작
백트래킹(0)

기저 조건(base condition)은 재귀 함수에서 더 이상 재귀적으로 호출하지 않고, 즉시 결과를 반환하거나 특정 작업을 수행하는 조건을 말한다. 목표로 하는 상태, 정답에 도달한 경우에는 탐색을 이어갈 필요가 없으므로 종료한다.

위 의사코드의 핵심은 숫자를 선택해 추가한 후, 다음 상태로 이동해 모든 경우를 탐색하고, 탐색이 종료되면 선택한 숫자를 제거해 상태를 되돌려 탐색을 이어나가는 것이다. 이를 통해 가능한 수열의 모든 경우를 찾을 수 있다.

체스 퀸 문제: N-Queens 문제

체스 퀸 문제는 대표적인 백트래킹 문제로, N x N 체스판 위에 N개의 퀸을 서로 공격하지 않도록 배치하는 문제이다. 퀸은 같은 행, 열, 대각선에 위치한 다른 퀸을 공격할 수 있기 때문에 N개의 퀸이 서로를 공격하지 않도록 N개의 서로 다른 행에 배치하는 방법을 찾는 문제이다.

boardSize = int(input())
queens = []
answer = 0
columns = [False] * boardSize

def can_put_chess(now_i, now_j):
    for queen in queens:
        i, j = queen
        diff_i = abs(now_i - i)
        diff_j = abs(now_j - j)
        if diff_i == diff_j:
            return False

    return True

def put_chess(row):
    global answer, queens
    if row ==  boardSize: # 기저 조건 - 모든 퀸을 배치한 경우
        answer += 1
        return

    for j in range(boardSize):
        if not columns[j] and can_put_chess(row, j): # 해당 열에 퀸을 배치할 수 없다면 다음 열을 탐색하게 됨
            queens.append((row, j))
            columns[j] = True
            put_chess(row + 1)
            queens.remove((row, j)) # 다른 경우를 탐색하기 위함
            columns[j] = False

put_chess(0)
print(answer)

이 코드는 퀸을 체스판의 각 행에 하나씩 놓으면서 다음 행으로 이동하여 계속 놓을 수 있는지 탐색한다. 충돌이 발생하면, 해당 위치는 놓을 수 없으므로 이전 단계로 돌아가 다른 가능성을 탐색하는 과정을 반복한다. 가능한 모든 경우를 시도하면서 유효하지 않은 경우를 빠르게 배제할 수 있다.

링크: https://www.acmicpc.net/problem/1208

유형: 이분탐색, Meet in the middle

난이도: 골드1

스스로 풀었는가? ❌

💻 작성 코드

import sys
from itertools import combinations

readline = sys.stdin.readline
answer = 0
N, TARGET_SUM = map(int, readline().split())
inputs = list(map(int, readline().split()))
front_half = inputs[:N//2]
back_half = inputs[N//2:]

front_half_sequence = []
back_half_sequence = []

def generate_sequence(arr, IS_REVER_SORT):
    sequence = []
    for i in range(len(arr) + 1):
        combs = combinations(arr, i)
        for comb in combs:
            sequence.append(sum(comb))

        if IS_REVER_SORT:
            sequence.sort(reverse=True)
        else:
            sequence.sort()

    return sequence, len(sequence)

front_half_sequence, front_half_sequence_len = generate_sequence(front_half, False)
back_half_sequence, back_half_sequence_len = generate_sequence(back_half, True)

answer, front_idx, back_idx = 0, 0, 0

while front_idx < front_half_sequence_len and back_idx < back_half_sequence_len:
    front_num = front_half_sequence[front_idx]
    back_num = back_half_sequence[back_idx]
    temp_sum = front_num + back_num

    if temp_sum > TARGET_SUM:
        back_idx += 1
    elif temp_sum < TARGET_SUM:
        front_idx += 1
    else: # sum == TARGET_SUM
        temp_front_idx = front_idx
        temp_back_idx = back_idx
        while temp_front_idx < front_half_sequence_len and front_half_sequence[temp_front_idx] == front_num:
            temp_front_idx += 1

        while temp_back_idx < back_half_sequence_len and back_half_sequence[temp_back_idx] == back_num:
            temp_back_idx += 1

        answer += (temp_back_idx - back_idx) * (temp_front_idx - front_idx)
        front_idx = temp_front_idx
        back_idx = temp_back_idx

if TARGET_SUM == 0:
    answer -= 1 # 공집합 제거

print(answer)

🎯 접근 방식

1. 입력 배열을 중앙값을 기준으로 두 개의 배열로 나눈다.
2. 하위 배열에서 가능한 부분합을 계산한 후 정렬된 부분합 리스트를 생성한다.
3. 두 정렬된 리스트를 투 포인터 기법을 사용해 순회하면서 두 리스트의 합이 목표값에 도달하는 경우의 수를 계산한다.
4. 목표값이 0이라면 정답에 공집합이 포함되기 때문에 이를 제외한 결과를 출력한다.

💡 개선사항

1. 부분합을 구하는 함수를 리스트 컴프리헨션을 이용해 한줄로 줄일 수 있다.
2. 투 포인터 대신 이진탐색을 사용한다.

https://c4u-rdav.tistory.com/61 링크를 참고해 풀었다. 배열을 하위의 2개로 나누어 시간복잡도를 줄이는 방법이 인상깊다. [ktb-algorithm-study] 2주차

링크: https://www.acmicpc.net/problem/15657

유형: 백트래킹

난이도: 실버3

스스로 풀었는가? ✅

💻 작성 코드

import sys

N, M = 0, 0
sequence = []
answer = []

def back(cnt, start):
    global N, M, sequence, answer

    if cnt == M:
        print(' '.join(map(str, answer)))
        return

    for i in range(start, N):
        answer.append(sequence[i])
        back(cnt + 1, i)
        answer.pop()

readline = sys.stdin.readline
N, M = map(int, readline().split())
sequence = list(map(int, readline().split()))
sequence.sort()

back(0, 0)

🎯 접근 방식

1. 재귀 함수를 통해 길이가 M이 될 때까지 리스트에 값을 하나씩 추가한다.
2. 값을 중복으로 포함할 수 있으므로 값이 현재 순열에 포함되어있는지 확인하지 않는다.
3. 비내림차순으로 정렬되어야 하므로 start를 인자로 넘겨서 해당 값부터 반복문을 돈다.

💡 개선사항

1. print(*answer)으로 쉽게 정답을 출력할 수 있다.

[ktb-algorithm-study] 2주차

링크: https://www.acmicpc.net/problem/6603

유형: 조합

난이도: 실버2

스스로 풀었는가? ✅

💻 작성 코드

import sys
from itertools import combinations

readline = sys.stdin.readline
input = readline().rstrip('\n')
while input != '0':
    arr = list(map(int, input.split()))
    k = arr[0]
    arr = arr[1:]
    LOTTO_LEN = 6
    combs = combinations(arr, LOTTO_LEN)
    for comb in combs:
        output = ' '.join(map(str, comb))
        print(output)
    print()
    input = readline().rstrip('\n')

🎯 접근 방식

1. input으로 0이 들어올 때까지 반복적으로 배열을 입력 받는다.
2. 배열에서 6인 조합들을 만들어 출력한다.

💡 개선사항

1. 변수를 한 줄에 할당할 수 있다. k, numbers = arr[0], arr[1:]

이 문제를 풀면서 파이썬에는 do-while 문이 없다는 걸 알았다..

[ktb-algorithm-study] 2주차

링크: https://www.acmicpc.net/problem/15656

유형: 백트래킹

난이도: 실버3

스스로 풀었는가? ✅

💻 작성 코드

import sys

N, M = 0, 0
sequence = []
visited = []
answer = []

def back(cnt):
    global N, M, sequence, visited, answer

    if cnt == M:
        print(' '.join(map(str, answer)))
        return

    for i in range(N):
        answer.append(sequence[i])
        back(cnt + 1)
        answer.pop()

readline = sys.stdin.readline
N, M = map(int, readline().split())
sequence = list(map(int, readline().split()))
sequence.sort()
visited = [False] * N

if M == 1:
    output = '\n'.join(map(str, sequence))
    print(output)
else:
    back(0)

🎯 접근 방식

1. 재귀 함수를 통해 길이가 M이 될 때까지 리스트에 값을 하나씩 추가한다.
2. 값을 중복으로 포함할 수 있으므로 값이 현재 순열에 포함되어있는지 확인하지 않는다.

💡 개선사항

1. M이 1인 경우를 따로 별도로 처리할 필요가 없다.
2. 값이 중복으로 들어갈 수 있기 때문에 visited 배열은 사용하지 않는다. 코드 제출 전 꼼꼼하게 다시 확인하자.
3. print(*answer)으로 쉽게 정답을 출력할 수 있다.

💻 개선사항을 반영한 코드

import sys

N, M = 0, 0
sequence = []
answer = []

def back(cnt):
    global N, M, sequence, answer

    if cnt == M:
        print(*answer)
        return

    for i in range(N):
        answer.append(sequence[i])
        back(cnt + 1)
        answer.pop()

readline = sys.stdin.readline
N, M = map(int, readline().split())
sequence = list(map(int, readline().split()))
sequence.sort()

back(0)

[ktb-algorithm-study] 2주차

링크: https://www.acmicpc.net/problem/15655

유형: 백트래킹

난이도: 실버3

스스로 풀었는가? ✅

💻 작성 코드

import sys

N, M = 0, 0
sequence = []
visited = []
answer = []

def back(cnt, start):
    global N, M, sequence, visited, answer

    if cnt == M:
        print(' '.join(map(str, answer)))

    for i in range(start, N):
        if not visited[i]:
            visited[i] = True
            answer.append(sequence[i])
            back(cnt + 1, i + 1)
            visited[i] = False
            answer.pop()

readline = sys.stdin.readline
N, M = map(int, readline().split())
sequence = list(map(int, readline().split()))
sequence.sort()
visited = [False] * N

if M == 1:
    output = '\n'.join(map(str, sequence))
    print(output)
else:
    back(0, 0)

🎯 접근 방식

1. 재귀 함수를 통해 길이가 M이 될 때까지 리스트에 값을 하나씩 추가한다. visited 배열을 통해 순열에 값이 중복 포함되지 않도록 한다.
2. start 값부터 for문을 돎으로써 순열이 오름차순이여야 한다는 조건을 만족한다.

💡 개선사항

1. M이 1인 경우를 따로 별도로 처리할 필요가 없다.
2. visited 배열 대신 if num in list: 조건문을 통해 값이 중복으로 들어가지 않도록 한다. (코드가 짧아지고 메모리가 줄어드는 대신 실행 시간이 약간 증가)

풀이를 한번에 적으려니 기억이 안 난다.. 한 문제 풀 때마다 바로 풀이를 적는 게 편할 듯하다.

[ktb-algorithm-study] 2주차

링크: https://www.acmicpc.net/problem/15654

유형: 순열, 백트래킹

난이도: 실버3

스스로 풀었는가? ✅

💻 작성 코드

import sys

N, M = 0, 0
sequence = []
visited = []
answer = []

def back(cnt, start):
    global N, M, sequence, visited, answer

    if cnt == M:
        print(' '.join(map(str, answer)))

    for i in range(start, N):
        if not visited[i]:
            visited[i] = True
            answer.append(sequence[i])
            back(cnt + 1, i + 1)
            visited[i] = False
            answer.pop()

readline = sys.stdin.readline
N, M = map(int, readline().split())
sequence = list(map(int, readline().split()))
sequence.sort()
visited = [False] * N

if M == 1:
    output = '\n'.join(map(str, sequence))
    print(output)
else:
    back(0, 0)

🎯 접근 방식

1. sort 함수를 사용해 사전이 증가하는 순으로 수열을 정렬한다.
2. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
3. itertools 모듈의 permutations 함수를 이용해 N개의 자연수 중 길이가 M인 수열을 생성한다.
4. 생성한 수열을 출력한다.

💡 개선사항

1. 백트래킹과 순열 함수를 모두 쓸 수 있는 경우에서는 함수를 쓰자. 실제로 방법1이 실행 속도가 더 빨랐다.

[ktb-algorithm-study] 2주차

링크: https://school.programmers.co.kr/learn/courses/30/lessons/17680

유형: 구현

난이도: Lv.2

스스로 풀었는가? ✅

특이사항: 2018 KAKAO BLIND RECRUITMENT 문제

💻 작성 코드

def solution(cacheSize, cities):
    cities_in_cache = []
    total_time = 0
    CACHE_MISS_TIME = 5
    CACHE_HIT_TIME = 1

    if cacheSize == 0:
        total_time = len(cities) * CACHE_MISS_TIME
        return total_time

    for city in cities:
        city = city.lower()
        if city not in cities_in_cache:
            total_time += CACHE_MISS_TIME
            if len(cities_in_cache) >= cacheSize:
                cities_in_cache.pop(0)
            cities_in_cache.append(city)
        else:
            total_time += CACHE_HIT_TIME
            cities_in_cache.remove(city)
            cities_in_cache.append(city)

    return total_time

🎯 접근 방식

1. 캐시된 도시를 담는 배열을 선언하여 입력으로 주어지는 도시를 배열에 추가한다. 인덱스 0번째의 도시가 항상 가장 오래 전에 캐시된 도시가 되도록 유지한다.
2. 만약 이미 배열에 있다면, 가장 최근에 캐시된 도시라는 것을 나타내기 위해 캐시 배열에서 도시를 제거했다가 다시 추가한다.
3. 배열에 없다면, 가장 오래 전에 캐시된 도시를 제거하고 새롭게 도시를 추가한다.

💡 개선사항

1. deque의 maxlen을 cacheSize로 지정하면 사이즈를 초과하여 값이 추가될 때 자동으로 맨 앞의 값이 제거된다.

캐시 교체 알고리즘인 LRU를 기반으로 나온 문제라 좀 재밌었다. 캐시 알고리즘 복습해야겠다.. [ktb-algorithm-study] 2주차

TypeScript는 JavaScript의 상위 집합으로, 정적 타입 시스템과 객체지향 프로그래밍 기능을 추가하여 대규모 애플리케이션 개발을 더 안전하고 효율적으로 할 수 있게 만든 언어입니다. 컴파일 시 JavaScript로 변환됩니다.

JavaScript와의 주요 차이점

TypeScript를 사용하면 코드 작성 시 타입 오류를 사전에 잡을 수 있어 런타임 오류를 줄일 수 있습니다. 변수, 함수 매개변수, 반환값 등의 타입을 미리 검사함으로써 코드의 안정성이 높아지고, 예상치 못한 버그를 사전에 방지할 수 있습니다. 또한 타입 시스템은 팀원이 코드를 쉽게 이해할 수 있도록 만들어 주기 때문에 유지보수를 쉽게 만들어 줍니다.

TypeScript는 클래스, 인터페이스, 상속, 추상 클래스 등 객체지향 프로그래밍(OOP) 개념을 지원합니다. 이는 코드 재사용성을 높이고, 구조적인 설계를 가능하게 합니다.

타입 명시 예시

js인 경우

function add(a, b) {
  return a + b;
}

const sum = add(10, 20);
console.log(sum); // 30

ts인 경우

function add(a: number, b: number): number {
  return a + b;
}

const sum: number = add(10, 20);
console.log(sum); // 30

OOP 개념 예시

class Person {
  name: string;
  age: number;

  constructor(name: string, age: number) {
    this.name = name;
    this.age = age;
  }

  greet() {
    console.log(`Hello, my name is ${this.name} and I am ${this.age} years old.`);
  }
}

const alice = new Person("Alice", 30);
alice.greet(); // "Hello, my name is Alice and I am 30 years old."

타입 추론 예시

let message = "Hello, TypeScript!";
// TypeScript는 message 변수가 string 타입임을 자동으로 추론합니다.

message = 123; // 오류: Type 'number' is not assignable to type 'string'.

타입스크립트 적용

tsconfig.json 파일

{
  "compilerOptions": {
    "target": "es5",
    "lib": [
      "dom",
      "dom.iterable",
      "esnext"
    ],
    "allowJs": true,
    "skipLibCheck": true,
    "esModuleInterop": true,
    "allowSyntheticDefaultImports": true,
    "strict": true,
    "forceConsistentCasingInFileNames": true,
    "noFallthroughCasesInSwitch": true,
    "module": "esnext",
    "moduleResolution": "node",
    "resolveJsonModule": true,
    "isolatedModules": true,
    "noEmit": true,
    "jsx": "react-jsx"
  },
  "include": [
    "src"
  ]
}

React + Ts 앱 생성

npx create-react-app <App-name> --template typescript => 새로운 리액트 프로젝트가 생기고 tsconfig.json 파일 생성됩니다.

tsconfig.json 파일의 내용은 아래와 같습니다.

{
  "compilerOptions": {
    "target": "es5",
    "lib": [
      "dom",
      "dom.iterable",
      "esnext"
    ],
    "allowJs": true,
    "skipLibCheck": true,
    "esModuleInterop": true,
    "allowSyntheticDefaultImports": true,
    "strict": true,
    "forceConsistentCasingInFileNames": true,
    "noFallthroughCasesInSwitch": true,
    "module": "esnext",
    "moduleResolution": "node",
    "resolveJsonModule": true,
    "isolatedModules": true,
    "noEmit": true,
    "jsx": "react-jsx"
  },
  "include": [
    "src"
  ]
}

Prettier란?

코드 포맷팅 도구로, 코드의 스타일을 일관되게 유지하게 해줍니다. 탭 너비, 세미콜론 사용 여부, 따옴표 스타일 등을 자동으로 포맷팅해줍니다. 코드의 외형(스타일)을 통일되게 만들어줍니다.

ESLint란?

코드 린팅 도구로, 코드의 문법 오류나 버그가 발생할 가능성이 있는 부분을 찾아냅니다. (스타일 문제도 일부 다룰 수 있습니다.) 예를 들어, 사용하지 않는 변수, 잘못된 사용 방법, 일관되지 않은 스타일 등을 경고하거나 수정합니다. ESLint는 문법 오류와 코드 스타일을 모두 검사할 수 있지만, 주로 코딩 규칙에 관한 문제를 찾고 수정하는 데 사용됩니다.

Prettier & ESLint 적용

1. Prettier와 ESLint 및 관련 플러그인 설치 npm install --save-dev prettier eslint eslint-config-prettier eslint-plugin-prettier

2. .prettierrc.json와 .eslintrc.json 파일 생성 js 또는 json으로 파일을 생성해 원하는 규칙을 정의내리면 된다.

• 코드 예시

  • .prettierrc.json

      {
        "singleQuote": true,
        "semi": true,
        "useTabs": false,
        "tabWidth": 2,
        "trailingComma": "all",
        "printWidth": 80,
        "arrowParens": "avoid",
        "bracketSpacing": true,
        "htmlWhitespaceSensitivity": "css",
        "insertPragma": false,
        "jsxBracketSameLine": false,
        "jsxSingleQuote": false,
        "proseWrap": "preserve",
        "quoteProps": "as-needed",
        "requirePragma": false,
        "endOfLine": "auto"
      }

    
    

  • .eslintrc.json

      {
          "env": {
            "browser": true,
            "es2021": true,
            "jest": true
          },
          "extends": [
            "eslint:recommended",
            "plugin:react/recommended",
            "plugin:@typescript-eslint/recommended",
            "prettier"
          ],
          "settings": {
            "react": {
              "version": "detect"
            }
          },
          "parser": "@typescript-eslint/parser",
          "parserOptions": {
            "ecmaFeatures": {
              "jsx": true
            },
            "ecmaVersion": 12,
            "sourceType": "module"
          },
          "plugins": [
            "react",
            "@typescript-eslint",
            "prettier"
          ],
          "rules": {
            "react/react-in-jsx-scope": "off",
            "indent": ["error", 2],
            "linebreak-style": ["error", "unix"],
            "quotes": ["error", "single"],
            "semi": ["error", "always"],
            "no-extra-semi": "error",
            "no-tabs": ["error", { "allowIndentationTabs": false }],
            "prettier/prettier": ["error"]
          }
        }
    

    
    

3. vs code에서 prettier, eslint 익스텐션 설치

4. vs code명령줄(cmd+shift+p)에 .vscode/settings.json 파일에 아래 내용 추가

{
  "editor.formatOnSave": true, // 저장할 때 자동으로 코드 포맷팅을 실행
  "editor.codeActionsOnSave": {
    "source.fixAll.eslint": true // 저장할 때 자동으로 ESLint 규칙에 따라 가능한 모든 문제를 수정
  }
}

Tailwind CSS

개념

Tailwind CSS는 유틸리티 퍼스트(utility-first) CSS 프레임워크로, 빠르고 쉽게 스타일을 적용할 수 있는 도구입니다. CSS를 별도로 작성할 필요 없이 HTML 태그의 className 안에 스타일을 정의내리는 인라인 스타일로, 정의된 클래스를 사용해서 빠르게 화면을 구현할 수 있습니다. 또 자주 쓰이는 스타일은 config 파일 안에 정의내림으로써 프로젝트 전반에 쉽게 적용할 수 있습니다.

사전에 정의된 클래스는 여기에서 확인할 수 있습니다.

장점

1. 완만한 학습 곡선 공식 문서가 굉장히 잘 정리되어 있고, 기본적으로 스타일에 대한 것은 css3와 유사하기 때문에 쉽게 적응할 수 있습니다.

   
   

2. 클래스 이름을 고민할 필요 ❌

   Tailwind CSS는 미리 정의된 유틸리티 클래스 이름을 사용하기 때문에, 개발자가 직접 클래스 이름을 고민할 필요가 없습니다.

<br />

3. 빌드 최적화

   Tailwind CSS는 사용된 클래스만을 포함하도록 빌드를 최적화할 수 있습니다. 이를 통해 최종 CSS 파일의 크기를 최소화할 수 있으며, 페이지 로딩 속도를 개선할 수 있습니다. 사용하지 않는 CSS를 제거하여 빌드 파일 크기를 줄이는 퍼지 기능이 내장되어 있어, 프로덕션 환경에서 최적화된 CSS를 제공합니다.

   
   

클래스 이름을 고민하지 않아도 되고 스타일 변경사항을 빠르게 반영할 수 있다는 점이 좋습니다 👍

단점

1. HTML 코드가 길어져 복잡성 ⬆️

2. 재사용성이 떨어지는 문제

   스타일을 개별 요소에 직접 적용하는 유틸리티 클래스를 사용합니다. 이는 동일한 스타일을 여러 곳에서 반복해서 사용할 때, 일관된 변경을 적용하기 어려울 수 있습니다.

3. 동적 클래스 이름 생성이 어려움

• Tailwind CSS는 컴파일 시점에 사용된 모든 클래스 이름을 분석하여 최종 CSS 파일을 생성합니다. 그러나 클래스 이름이 문자열로 동적으로 생성되거나 조합되면, Tailwind는 이러한 클래스를 미리 알 수 없으므로, 해당 클래스에 대한 스타일을 포함하지 못합니다.
• 예를 들어 text-${size} 와 같은 코드는 동작하지 않습니다. 삼항 연산자를 쓰거나 size를 미리 정의내려야 합니다.

Tailwind CSS 적용

1. 플러그인 설치

npm install -D tailwindcss postcss autoprefixer

postCSS를 사용하면 autoprefixer 플러그인으로 밴더프리픽스를 쉽게 적용할 수 있습니다.

2. tailwind.config.js 파일 생성

npx tailwindcss init -p 명령어를 통해 init 파일을 생성합니다.

3. App.css에 아래 내용 추가

@tailwind base;
@tailwind components;
@tailwind utilities;

4. vsCode Tailwind CSS IntelliSense 익스텐션 설치

위와 같이 태그 안에 className을 선언하고 고정된 클래스 이름을 입력했을 때 값이 자동완성 된다면, 적용 완료!

순열(Permutations)

정의

서로 다른 n개 원소에서 중복 없이, 순서를 고려해 r개의 원소를 선택해 나열하는 것 나열된 순서를 고려하기 때문에 1 2와 2 1을 다른 것으로 취급한다.

예제 문제를 풀면서 순열을 어떻게 문제에 적용하는지 살펴보자.

(예제) 백준 15654번 "N과 M (5)"

문제 정보

링크: https://www.acmicpc.net/problem/15654 난이도: 실버 3

N개의 자연수 중에서 길이가 M개인 수열들을 구해 출력하는 문제이다.

1. 라이브러리 사용 (Python)

import sys
from itertools import permutations

readline = sys.stdin.readline
N, M = map(int, readline().split())
sequence = list(map(int, readline().split()))
sequence.sort()

if M == 1:
    output = '\n'.join(map(str, sequence))
    print(output)
else:
    perms = permutations(sequence, M)
    for perm in perms:
        output = ' '.join(map(str, perm))
        print(output)

1. 파이썬에서 자동으로 순열을 구해주는 라이브러리를 사용하기 위해 상단에 from itertools import permutations를 추가한다.

2. perms = permutations(sequence, M)처럼 permutations 함수에 인자로 배열과 길이를 넘기면, 배열에서 만들 수 있는 길이 M의 모든 순열이 담긴 배열이 반환된다.

예를 들어 permutations([1, 2, 3, 4], 2) 은 길이가 2인 순열을 생성한다.

반환값: [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

2. 백트래킹으로 구현

순열, 조합 문제 중에 조건이 복잡하여 라이브러리로 풀 수 없을 때 백트래킹을 이용해 구현할 수 있다.

순열을 구하는 백트래킹 의사코드

# N개의 숫자와 M개의 선택된 숫자로 이루어진 순열을 생성하는 백트래킹 함수
백트래킹(현재 선택된 개수 cnt):
    만약 cnt가 M과 같다면:
        현재까지 선택된 숫자들을 출력
        반환

    # 가능한 모든 숫자를 탐색
    for i in 0에서 N-1까지:
        만약 i번째 숫자가 아직 선택되지 않았다면:
            i번째 숫자를 선택(방문 표시)
            현재까지 선택된 숫자들에 i번째 숫자를 추가
            백트래킹(cnt + 1)  # 다음 숫자를 선택하기 위해 재귀 호출
            i번째 숫자의 선택을 해제(방문 표시 해제)
            현재까지 선택된 숫자들에서 i번째 숫자를 제거  # 상태를 되돌림

# 초기 상태로부터 백트래킹 시작
백트래킹(0)

백트래킹의 핵심은 숫자를 선택해 추가한 후, 다음 상태로 이동해 모든 경우를 탐색하고, 탐색이 종료되면 선택한 숫자를 제거해 상태를 되돌려 탐색을 이어나가는 것이다. 이를 통해 가능한 수열의 모든 경우를 찾을 수 있다. 의사코드를 기반으로 python 코드를 작성해보자.

import sys

N, M = 0, 0
sequence = []
visited = []
answer = []

def back(cnt):
    global N, M, sequence, visited, answer

    if cnt == M:
        print(' '.join(map(str, answer)))
        return

    for i in range(N):
        if not visited[i]:
            visited[i] = True
            answer.append(sequence[i])
            back(cnt + 1)
            visited[i] = False
            answer.pop()

readline = sys.stdin.readline
N, M = map(int, readline().split())
sequence = list(map(int, readline().split()))
sequence.sort()
visited = [False] * N

if M == 1:
    output = '\n'.join(map(str, sequence))
    print(output)
else:
    back(0)

변수 설명

N: 입력에서 주어지는 정수의 개수 M: 순열의 길이. 선택해야 할 숫자의 개수 sequence: 입력으로 주어지는 정수들의 리스트 visited: 배열의 각 요소가 순열에 선택된 상태인지를 나타내는 boolean 리스트로, 순열을 생성할 때 중복 선택을 방지하기 위해 사용된다. answer: 현재까지 선택된 숫자들을 저장하는 리스트. M개의 숫자가 선택될 때까지 점점 채워지며, M개의 숫자가 모두 선택되면 answer에 담긴 숫자들을 출력한 후 상태를 되돌린다.

함수 설명

back(cnt): 백트래킹 함수. 현재까지 선택된 숫자의 개수(cnt)를 인자로 받는다. cnt가 M과 같아지면 현재까지 선택된 숫자들을 answer 리스트에서 출력한다. 재귀 호출이 끝나면 visited를 False로 바꾸고 answer에서 pop을 통해 선택된 숫자를 제거한다. 이후에 다시 탐색을 이어간다.

조합(Combinations)

정의

서로 다른 n개 원소에서 중복 없이, 순서를 고려하지 않고 r개의 원소를 선택하는 것 나열된 순서를 고려하지 않기 때문에 1 2와 2 1을 같은 것으로 취급한다.

순서를 고려하지 않다는 차이점 빼고 순열과 동일하기에 자세한 설명은 생략한다.

라이브러리 이용 상단에 from itertools import combinations를 추가 combs = combinations(arr, TARGET_LEN) 처럼 정의함으로써 배열에서 원하는 길이로 조합된 수열 리스트를 구할 수 있다.

예를 들어 combinations([1, 2, 3, 4], 2) 은 길이가 2인 순열을 생성한다. 반환값: [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

마찬가지로 백트래킹을 이용해 조합을 구현할 수 있다.

[ktb-algorithm-study] 2주차

2개의 포인터를 사용하여 특정 조건을 만족하는 구간이나 숫자의 쌍을 구하는 알고리즘이다. 주로 정렬된 배열에서 사용된다. 정렬되지 않은 배열이라면 누적합을 이용해 정렬된 배열의 형태로 바꿔 사용할 수 있다.

동작 방식

다음과 같이 정렬된 배열을 생각해보자.

left는 탐색 범위의 시작을 나타내는 왼쪽 포인터이다. right는 탐색 범위의 끝을 나타내는 오른쪽 포인터이다. 우리가 선택한 구간은 left ~ right이 된다.

right 포인터가 3에 위치한다면, 구간은 1~3이 되며 그때의 sum은 1+2+3이 된다.

만약 문제에서 목표 값 N이 주어진다면, sum과 N을 비교하여 포인터만 움직이면 된다.

투 포인터 이동 원칙

• sum > N: left를 오른쪽으로 이동한다. sum의 값은 작아진다.
• sum < N: right를 오른쪽으로 이동한다. sum의 값은 커진다.
• sum == N: 정답을 찾았다. 계속 탐색하려면 right를 오른쪽으로 이동한다. sum의 값은 커진다.

현재 상태 sum과 목표 N을 비교하면서 목표에 가까워지도록 포인터를 이동한다. 특정 조건을 만족하는 범위를 찾거나, 특정 조건을 만족하는 수의 쌍을 찾는데 유용하다.

시간 복잡도

투 포인터 알고리즘의 시간 복잡도는 일반적으로 O(n)이다. 그 이유는 두 개의 포인터가 배열의 시작과 끝에서 출발하여 각 포인터가 배열을 최대 한 번만 순회하기 때문이다.

(예제) 백준 2018번 "수들의 합5"

문제 정보

• 링크: https://www.acmicpc.net/problem/2018
• 난이도: 실버 5

문제 요약

입력으로 정수 N이 주어진다. N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 구해라. 이때, 사용하는 자연수는 N이하여야 한다.

예시1. 입력으로 15가 주어짐 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. => 정답 4

예시2. 입력으로 10이 주어짐 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다. => 정답 2

문제 풀이

1부터 15까지 자연수가 나열되어있다고 생각해보자. 우리의 목표는 15를 연속된 자연수의 합으로 나타내는 것이다.

left = 1, right = 1 left부터 right까지의 합은 1이다. 목표인 15보다 작으므로 right를 이동한다.

left = 1, right = 2 left부터 right까지의 합은 1+2 = 3이다. 목표인 15보다 작으므로 right를 이동한다.

left = 1, right = 3 left부터 right까지의 합은 1+2+3 = 6이다. 목표인 15보다 작으므로 right를 이동한다.

left = 1, right = 4 left부터 right까지의 합은 1+2+3+4 = 10이다. 목표인 15보다 작으므로 right를 이동한다.

left = 1, right = 5 left부터 right까지의 합은 1+2+3+4+5 = 15이다. 목표값과 동일하므로, 정답의 개수를 +1 시킨다. (누적: 1개) 그리고 right를 이동한다.

left = 1, right = 6 left부터 right까지의 합은 1+2+3+4+5+6 = 21이다. 목표인 15보다 크므로 left를 이동한다.

left = 2, right = 6 left부터 right까지의 합은 2+3+4+5+6 = 20이다. 목표인 15보다 크므로 left를 이동한다.

left = 3, right = 6 left부터 right까지의 합은 3+4+5+6 = 18이다. 목표인 15보다 크므로 left를 이동한다.

left = 4, right = 6 left부터 right까지의 합은 4+5+6 = 15이다. 목표값과 동일하므로, 정답의 개수를 +1 시킨다. (누적: 2개) 그리고 right를 이동한다.

. . .

(반복)

그 다음은 어떻게 될까? right를 이동하면 목표값보다 커지므로 다시 left를 이동할 것이다. 이 과정을 반복하면 두 포인터가 계속 오른쪽으로 움직이게 되며, 다른 정답인 7+8(left=7, right=8), 15(left=15, right=15)을 찾아 정답이 4개가 된다.

풀이 코드

import sys

realine = sys.stdin.readline
N = int(realine())

left = 1 # 왼쪽 포인터
right = 1 # 오른쪽 포인터
sum = 1 # 현재까지의 합
answer_count = 0

while right <= N: # right가 오른쪽 끝에 도달할 때까지 진행
    if sum > N:
        sum -= left
        left += 1
    elif sum < N:
        right += 1
        sum += right
    else: # sum == N
        answer_count += 1
        right += 1
        sum += right

print(answer_count)

위에서 적었던 투포인터의 이동 법칙을 상기시켜보자.

투 포인터 이동 원칙 sum > N: left를 오른쪽으로 이동한다. sum의 값은 작아진다. sum < N: right를 오른쪽으로 이동한다. sum의 값은 커진다. sum == N: 정답을 찾았다. 계속 탐색하려면 right를 오른쪽으로 이동한다. sum의 값은 커진다.

1번 케이스) sum > N

    if sum > N:
        sum -= left
        left += 1

sum이 N보다 큰 경우를 생각해보자. left=1, right=6일 때, sum = 1+2+3+4+5+6 = 21이다. 목표한 값보다 크므로 left를 오른쪽으로 이동하고, sum에서 1을 빼고 싶다. sum에서 1을 빼기 위해서는 sum에서 left를 먼저 뺀 후(sum -= 1), left를 이동시켜야 한다.(left=2)

2번 케이스) sum < N

    elif sum < N:
        right += 1
        sum += right

sum이 N보다 작은! 경우를 생각해보자.

left=1, right=3일 때, sum = 1+2+3 = 6이다. 목표한 값보다 작으므로 right를 오른쪽으로 이동하고, sum에 4를 더하고 싶다. sum에 4를 더하기 위해서는 right를 4로 먼저 이동시킨 후(right=4), sum에 더해야 한다.(sum += 4)

3번 케이스) sum == N

    else: # sum == N
        answer_count += 1
        right += 1
        sum += right

left=4, right=6일 때, sum = 4+5+6 = 15이다. 목표한 값과 동일하므로 정답 개수를 1 늘린다. 정답이 1개였다면 반복문을 종료했겠지만, N을 만드는 연속된 자연수의 합은 여러 개일수 있으므로 탐색을 계속한다. right를 7로 이동시킨 뒤, sum에 right를 더한다. (그러면 sum이 N보다 커지므로 그 다음엔 left가 이동하고, 위의 과정이 반복될 것이다.)

정리

투 포인터는 언제 쓰는가?

정렬된 배열에서의 특정 조건을 만족하는 요소 쌍이나 부분 배열을 찾는 데 자주 사용된다. 정렬된 배열의 특성을 이용하여 두 포인터를 배열의 왼쪽에서 시작하거나 양 끝에서 시작함으로써 문제를 해결할 수 있다.

투 포인터가 양쪽 끝에서 시작하는 경우? left는 배열의 가장 왼쪽에, right는 배열에 가장 오른쪽에 위치시켜 합이 목표 값보다 작으면 왼쪽 포인터를 오른쪽으로 이동시키고, 크면 오른쪽 포인터를 왼쪽으로 이동시키는 방법

누적합과의 조합

투 포인터 알고리즘은 누적합(prefix sum)과 함께 쓰이기도 한다. 위의 예제처럼 풀기 위해서는 배열이 정렬되어있어야 한다. 마구잡이인 배열에서 특정 합을 갖는 부분 배열을 구해야 한다면 누적합을 이용할 수 있다. 각 인덱스까지의 합을 미리 구해 놓고, 두 포인터를 사용하여 누적합의 차이가 특정 값을 만족하는 부분 배열을 찾으면 된다.

슬라이딩 윈도우와의 차이점

슬라이딩 윈도우는 고정 길이를 갖는다. 예를 들어 가로 길이가 5라고 고정되어 있어서 한쪽의 포인터가 움직이면 다른쪽의 포인터도 움직인다. 가변 길이의 슬라이딩 윈도우가 투포인터라고 생각하면 될 것 같다.

참고자료

<Do it! 알고리즘 코딩 테스트 - 자바 편>

[ktb-algorithm-study] 2주차

링크: https://school.programmers.co.kr/learn/courses/30/lessons/17681

유형: 구현, 비트마스크

난이도: Lv.1

스스로 풀었는가? ✅

특이사항: 2018 KAKAO BLIND RECRUITMENT 문제

💻 작성 코드

def solution(n, arr1, arr2):
    answer = []
    SPACE = " "
    WALL = "#"
    for row_idx in range(n):
        decoded_row_arr1 = list(bin(arr1[row_idx])[2:])
        decoded_row_arr2 = list(bin(arr2[row_idx])[2:])
        if len(decoded_row_arr1) < n:
            len_diff = n - len(decoded_row_arr1)
            decoded_row_arr1 = [0] * len_diff + decoded_row_arr1

        if len(decoded_row_arr2) < n:
            len_diff = n - len(decoded_row_arr2)
            decoded_row_arr2 = [0] * len_diff + decoded_row_arr2

        row = []
        for col_idx in range(n):
            if decoded_row_arr1[col_idx] == "1" or decoded_row_arr2[col_idx] == "1":
                row.append(WALL)
                continue

            row.append(SPACE)
        answer.append(''.join(row))
    return answer

🎯 접근 방식

1. 정수 배열의 row를 하나씩 읽어 바이너리로 변환 후, 리스트로 변환한다.
2. 리스트의 길이가 n보다 작은 경우 부족한 길이만큼 왼쪽에 0을 붙인다. (n=5일 때 '1001' -> '01001')
3. 두 지도의 배열 중 하나라도 1인 경우 벽(#)을 넣고, 아니라면 공백(" ")을 넣는다.
4. 해독된 row를 리스트에서 문자열로 변환해 정답 배열에 넣는다.

💡 개선사항

프로그래머스에서 다른 사람의 풀이를 구경하다가 천재적인 코드를 발견했다.

def solution(n, arr1, arr2):
    answer = []
    for i,j in zip(arr1,arr2):
        a12 = str(bin(i|j)[2:])
        a12=a12.rjust(n,'0')
        a12=a12.replace('1','#')
        a12=a12.replace('0',' ')
        answer.append(a12)
    return answer

1. row_idx, col_idx처럼 인덱스로 접근하는 대신 .zip()를 이용하면 두 배열의 값을 한번에 읽을 수 있다.

2. 문자열의 길이를 맞추는 것은 rjust, zfill을 이용하면 된다.

   # 문자열의 길이를 5로 맞추고 왼쪽을 '0'으로 채움
   result = original.zfill(5)
   
   # 문자열의 길이를 5로 맞추고 왼쪽을 '0'으로 채움
   result2 = original.rjust(5, '0')

   zfill은 항상 0으로 채우는 반면, rjust는 문자를 지정할 수 있다는 차이가 있다. 내 코드에 적용하면 bin(number)[2:].zill(n) 이 되겠다.

3. 리스트 컴프리헨션을 이용하면 코드를 더욱 간결하게 만들 수 있다.

4. 문자열의 각 문자에 대한 순회를 위해 리스트를 만들 필요가 없다. for...in 문을 통해 간편하게 문자열의 각 문자를 순회할 수 있다.

5. 비트 OR 연산을 이용하면 두 지도의 하나라도 벽이 있는지 간단하게 확인할 수 있다.

   row1 = 9    # 이진수: 1001
   row2 = 30   # 이진수: 11110
   

""" row1 | row2 연산

01001 # 9의 이진수 (앞에 0을 붙여 5비트로 맞춤) 11110 # 30의 이진수

11111 # OR 연산 결과

따라서 row1 | row2는 32를 의미한다. """ print(row1 | row2) # 32 print(bin(row1 | row2)) # '0b11111'

<br />

---

<br />

# 💻 개선사항을 반영한 최종 코드


```python
def solution(n, arr1, arr2):
    answer = []
    SPACE = " "
    WALL = "#"

    for row1, row2 in zip(arr1, arr2):
        # 비트 OR 연산 후 이진수 문자열로 변환
        combined_row = bin(row1 | row2)[2:].rjust(n, '0')

        # 리스트 컴프리헨션을 사용하여 정답 지도의 row 생성
        decoded_row = [WALL if bit == "1" else SPACE for bit in combined_row]

        answer.append(''.join(decoded_row))

    return answer

[ktb-algorithm-study] 1주차

링크: https://school.programmers.co.kr/learn/courses/30/lessons/81301

유형: 구현

난이도: Lv.1

스스로 풀었는가? ✅

특이사항: 2021 카카오 채용연계형 인턴십 문제

💻 작성 코드

def solution(s):
    answer = s
    digit_eng_dict = {
        "zero": 0,
        "one": 1,
        "two": 2,
        "three": 3,
        "four": 4,
        "five": 5,
        "six": 6,
        "seven": 7,
        "eight": 8,
        "nine": 9
    }

    for key in digit_eng_dict.keys():
        answer = answer.replace(key, str(digit_eng_dict.get(key)))
    return int(answer)

🎯 접근 방식

1. 숫자와 영단어가 1대1로 대응되므로 dictionary를 이용한다.
2. dictionary를 순회하면서 replace method를 활용해 영단어를 숫자로 바꾼다.

💡 개선사항

1. dict.keys() 대신 dict.items()을 이용하면 쉽게 key와 value 값을 가져올 수 있다.
2. dictionary에 선언할 때부터 value를 str로 선언하면 형변환이 필요없다.

[ktb-algorithm-study] 1주차

링크: https://www.acmicpc.net/problem/17609

유형: 문자열, 투포인터

난이도: 골드5

스스로 풀었는가? ❌ (질문 게시판 이용)

💻 작성 코드 (리팩터링 전)

import sys

def check_palindrome(input_str):
    start_idx = 0
    end_idx = len(input_str) - 1
    is_pseudo_palindrome = False
    while start_idx < end_idx:
        if input_str[start_idx] == input_str[end_idx]:
            start_idx += 1
            end_idx -= 1
            continue

        if is_pseudo_palindrome:
            return 2

        if input_str[start_idx + 1] == input_str[end_idx] and input_str[start_idx] == input_str[end_idx - 1]:
            tmp_start = start_idx + 1
            tmp_end = end_idx
            is_tmp_pseudo_palindrome = False
            while tmp_start < tmp_end:
                if input_str[tmp_start] == input_str[tmp_end]:
                    tmp_start += 1
                    tmp_end -= 1
                    continue

                is_tmp_pseudo_palindrome = True
                break

            if not is_tmp_pseudo_palindrome:
                return 1

            tmp_start = start_idx
            tmp_end = end_idx - 1
            is_tmp_pseudo_palindrome = False
            while tmp_start < tmp_end:
                if input_str[tmp_start] == input_str[tmp_end]:
                    tmp_start += 1
                    tmp_end -= 1
                    continue

                is_tmp_pseudo_palindrome = True
                break

            if not is_tmp_pseudo_palindrome:
                return 1

            return 2

        if input_str[start_idx + 1] == input_str[end_idx]:
            start_idx += 1
            is_pseudo_palindrome = True
            continue

        if input_str[start_idx] == input_str[end_idx - 1]:
            is_pseudo_palindrome = True
            end_idx -= 1
            continue

        return 2

    if is_pseudo_palindrome:
        return 1

    return 0

readline = sys.stdin.readline
T = int(readline())
input_strs = []
for i in range(T):
    input_strs.append(readline().rstrip('\n'))

for input_str in input_strs:
    print(check_palindrome(input_str))

🎯 접근 방식

1. 문자열이 대칭인지 확인하기 위해 문자열의 양쪽 끝에 투포인터를 두고 중앙으로 이동시킨다.
2. 각 포인터가 위치한 문자가 같은지 아닌지 비교하여 포인터를 이동한다. 2-1. 대칭인 경우 포인터를 하나씩 이동시킨다. 2-2. 대칭이 아니고 이미 문자를 제거했던 경우(is_pseudo_palindrome == True), 2를 반환한다. 2-3. 대칭이 아닌 경우 이전에 문자를 제거하지 않았던 경우
   • 2-3-1. 왼쪽과 오른쪽 중에 한쪽 문자만 제거할 수 있는 경우, 문자를 제거하도록 포인터를 이동한 후 is_pseudo_palindrome의 값을 True로 변경한다.
   • 2-3-2. 왼쪽 문자를 제거해도 되고, 오른쪽 문자를 제거해도 되는 경우는 둘 중에 하나만 최종적으로 대칭이 성립해도 유사회문이 된다. 먼저 왼쪽 문자를 제거하고 반복문을 통해 최종적으로 대칭이 되는지 확인해 만약 대칭이라면 1을 반환한다. 왼쪽 문자를 제거한 경우 최종적으로 대칭이 되지 않는다면, 오른쪽 문자를 제거하고 반복문을 통해 최종적으로 대칭이 되는지 확인한다. 만약 대칭이라면 1을 반환하고, 아니라면 2를 반환한다.

💡 개선사항

1. 문자 제거가 일어나는 경우, 제거한 후에 최종적으로 대칭이 되는지 확인해야 하기 때문에 한쪽 문자만 제거할 수 있는 경우를 굳이 분리할 필요가 없다.
2. 왼쪽 또는 오른쪽 문자를 제거한 후 최종적으로 대칭이 되는지 확인하는 while문은 별도의 메서드로 분리할 수 있다.
3. 처음에 설계한 코드가 제출하면 틀려서, 반례를 찾는데 시간을 많이 소요했다. (e.g. ababbabaa 같은 케이스) 처음부터 설계 과정에서 여러 케이스를 떠올리며 로직을 설계하는 연습을 해야겠다.

💻 최종 코드 (리팩터링 후)

import sys

def is_palindrome(s, left, right):
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

def check_palindrome_or_not(input_str):
    start_idx = 0
    end_idx = len(input_str) - 1

    while start_idx < end_idx:
        if input_str[start_idx] == input_str[end_idx]:
            start_idx += 1
            end_idx -= 1
            continue

        # 두 경우 중에 하나라도 회문이면 유사 회문
        if is_palindrome(input_str, start_idx + 1, end_idx) or is_palindrome(input_str, start_idx, end_idx - 1):
            return 1
        return 2

    return 0

readline = sys.stdin.readline
T = int(readline())
input_strs = []
for i in range(T):
    input_strs.append(readline().rstrip('\n'))

for input_str in input_strs:
    print(check_palindrome_or_not(input_str))

[ktb-algorithm-study] 1주차

링크: https://www.acmicpc.net/problem/2230

유형: 정렬, 투포인터

난이도: 골드5

스스로 풀었는가? ✅

💻 작성 코드

import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
numbers = []
for i in range(N):
    numbers.append(int(readline()))

numbers.sort()

start_idx = 0
end_idx = 0
min_diff = sys.maxsize
while end_idx < N:
    diff = numbers[end_idx] - numbers[start_idx]
    if diff == M:
        min_diff = min(min_diff, diff)
        end_idx += 1
    elif diff > M:
        min_diff = min(min_diff, diff)
        start_idx += 1
    else:
        end_idx += 1

print(min_diff)

🎯 접근 방식

1. 수열에서 두 수를 고르기만 하면 되므로 먼저 수열을 정렬한다.
2. 차이(diff)가 목표값(M)보다 크면 start_idx 늘리고, 목표보다 작으면 end_idx 늘리고, 목표와 같으면 end_idx 늘린다.
3. 차이가 M 이상이면서 제일 작은 경우를 구해야 하므로 diff가 M 이상이라면 diff와 min_diff 값을 비교한다.

💡 개선사항

1. 차이가 M 이상이면서 제일 작은 경우를 구하기 때문에, diff == M이라면 바로 반복문을 종료해도 된다.

[ktb-algorithm-study] 1주차

링크: https://www.acmicpc.net/problem/1806

유형: 누적합, 투포인터

난이도: 골드4

스스로 풀었는가? ✅

💻 작성 코드

import sys

readline = sys.stdin.readline
N, S = map(int, readline().split())
input_numbers = list(map(int, readline().split()))
accumulated_sum = [0] # 누적합
now_sum = 0
for number in input_numbers:
    now_sum += number
    accumulated_sum.append(now_sum)

start_idx = 0
end_idx = 0
min_length = sys.maxsize

while end_idx <= N:
    temp_sum = accumulated_sum[end_idx] - accumulated_sum[start_idx]
    if temp_sum < S:
        end_idx += 1
    elif temp_sum > S:
        min_length = min(min_length, end_idx - start_idx)
        start_idx += 1
    else:
        min_length = min(min_length, end_idx - start_idx)
        end_idx += 1

if min_length == sys.maxsize:
    print(0)
else:
    print(min_length)

🎯 접근 방식

1. 부분합을 쉽게 구하기 위해 누적합 배열을 구한다. (0번째 index를 0으로 초기화하는 것 잊지 말자)
2. start_idx 와 end_idx 를 왼쪽에서 시작하여 해당 범위의 누적합과 S를 비교해 포인터를 이동시킨다.
3. 누적합이 S 이상이라면 min_length 와 비교해 작으면 업데이트한다.

💡 개선사항

1. 문제를 잘 읽자. 합이 S 이상이 되는 것 중 가장 짧은 것의 길이에서 이상 이라는 키워드를 뒤늦게 발견했다.
2. 찾아보니 슬라이딩 윈도우 기법을 사용하면 더 깔끔하게 풀 수 있다고 한다.

다른 방법으로는 temp_sum을 매번 계산하는 것이 아니라, while문 밖에 sum 변수를 하나 두고 idx가 움직일 때 변수의 값을 변경하는 방법이 있다. 하지만 기존 코드를 굳이 바꿀 필요는 없을 것 같다. 인덱스로 배열 값 가져오는 건 어차피 O(1)이니까.

[ktb-algorithm-study] 1주차

링크: https://www.acmicpc.net/problem/11728

유형: 정렬, 투포인터

난이도: 실버5

스스로 풀었는가? ✅

💻 작성 코드

import sys

readline = sys.stdin.readline

N, M = map(int, readline().split())
arr = list(map(int, readline().split()))
brr = list(map(int, readline().split()))

arr_idx = 0
brr_idx = 0
answer = []

while arr_idx < len(arr) and brr_idx < len(brr):
    a = arr[arr_idx]
    b = brr[brr_idx]
    if a < b:
        answer.append(a)
        arr_idx += 1
    else:
        answer.append(b)
        brr_idx += 1

while arr_idx < len(arr):
    answer.append(arr[arr_idx])
    arr_idx += 1

while brr_idx < len(brr):
    answer.append(brr[brr_idx])
    brr_idx += 1

output = ' '.join(map(str, answer))
print(output)

🎯 접근 방식

1. 정렬된 두 배열을 합치려면 각 배열에 있는 값을 비교해야 하므로 투포인터를 이용한다.
2. 포인터를 통해 배열을 순회하며 더 작은 값을 answer에 추가한다.
3. 한 쪽 배열의 모든 값이 합쳐졌다면 다른 배열의 남은 값을 answer에 추가한다.

💡 개선사항

1. list를 그대로 출력해서 한 번 틀렸다. 문제를 볼 때 Output을 잘 보자.
2. 병합 이후에 남은 값들을 합칠 때 answer.extend(arr[arr_idx:]) 를 통해 간단히 해결할 수 있다.

첫 한 달은 카카오테크 부트캠프의 시스템에 적응하고, 강의를 통해 지식을 쌓고, 앞으로의 목표를 고민하는 시간이었다.

📚 무엇을 배웠지?

강의는 매일 2시간씩 온라인 실시간으로 진행됐다. 12주차에는 프론트, 34주차에는 서버와 DB 지식을 배웠다. 크게 다음과 같은 주제로 진행되었다.

1~2주차

• HTML, CSS, Js
• 크로스 브라우징, 폴리필, 트랜스파일러
• Fetch API
• Context API
• 타입스크립트
• 리액트 Memoization
• CSR vs SSR
• 리액트의 코드 분할과 지연 로딩
• 리액트 데이터 페칭 전략 - React Query, SWR
• WebSocket 예시
• React 아키텍처 패턴

3주차

• 서버 상태 모니터링 방법
• 통신 프로토콜 (HTTP, WebSocket, FTP, SSH)
• API 문서화 도구 소개 (Swagger, OpenAPI, Postman, Insomnia)
• 디자인패턴 (MVC, MVP, MVVM, 싱글톤, 팩토리, 옵저버, Strategy 등)
• 인증과 권한 관리 (쿠키, 세션, 토큰, OAuth)
• 보안을 위협하는 공격 예시
• 애플리케이션 코드 최적화 방법
• 비동기 처리
• 서버 레벨 최적화
• 로드 밸런싱
• 컨테이너와 컨테이너 오케스트레이션

4주차

• RDBMS와 NoSQL
• 정규화
• ACID
• 데이터베이스 모니터링 기술
• 쿼리 최적화
• 시큐리티 코딩
• OWASP Top 10
• DevSecOps
• 시스템 아키텍처 (모놀리식, 3-Tier, MSA, 서버리스)
• 다양한 다이어그램 (유스케이스, 시퀀스 등등)

이렇게 정리하고 보니 정말 많은 것을 배웠다. 가볍게 소개하고 넘어간 개념도 있었고, 코드 레벨로 자세히 설명해주신 개념도 있었다. 개인적으로는 평소에 궁금했던 아키텍처 패턴과 다양한 최적화 기법들을 배울 수 있어 좋았다 😁

힘든 오전 시간 강의임에도 불구하고 주강사님의 강의력이 좋은 덕분에 집중할 수 있었다. 질문을 적극적으로 받아주시고, 현직자의 관점으로 답변해주시는 점이 정말 좋았다 👍👍

✅ 잘한 점

1. 강의 시간에 배운 내용을 제대로 학습하려고 노력함

4주 동안 배운 개념 중에는 기존에 알고 있었던 것도, 알고 있다고 생각했는데 실제로 몰랐던 것도, 아예 처음 접하는 것도 있었다. 이해가 안되는 건 개념과 코드 예제를 찾아보고 공식 문서를 읽으면서 이해하려고 노력했다.

2. 문서화 도전

후술하겠지만 이번 부트캠프에서 문서화 능력을 기르는 것을 하나의 목표로 잡았다. 모각코 기간에 열심히 문서를 작성하는 팀원들을 보고 자극받아 문서 작성을 도전했다. 크로스 브라우징, Nginx를 활용한 로드밸런싱, MySQL 슬로우 쿼리를 측정하는 방법에 대해 총 3편의 게시글을 작성했다.

3. 운동 (수영 + 걷기)

공부하느라 바쁜 와중에 운동?! 이라 생각할 수 있지만...

체력이 떨어짐 ➡️ 운동할 체력 없는데? ➡️ 체력이 더 떨어짐 ➡️ 운동할 체력 없는데? ➡️ ...

이제는 악순환을 벗어나야 한다. 10월부터 오프라인으로 갈려나갈려면

온라인으로 진행되는 9월까지는 꾸준히 운동하며 체력을 늘리려고 한다. 반년 만에 다시 수영을 시작하니 리프레쉬가 된다. 영법을 새롭게 배우고 조금씩 실력이 느는 게 재밌다. 강제성을 부여하기 위해 친구들과 내기를 시작해서 도망치지도 못한다. 🤣

❌ 아쉬운 점

1. 컨디션 관리 실패

중간에 감기에 걸려서 일주일 넘게 골골댔다. (의사 선생님: 신종 코로나일 수도 있고~ 아닐 수도 있어요~) 열이 나면 그냥 약 먹고 잠들어야 했고, 주말 내내 약한 두통을 앓기도 했다. 때문에 생산성이 크게 저하된 점이 아쉽다.

2. 아쉬운 학습 깊이

더 깊이 학습해보면 좋을 주제임에도 강의 자료만 보고 넘어간 개념이 몇 있다. 컨디션 문제도 있었지만, 시간이 부족하다는 핑계로 관심 있는 것만 파고들어 공부한 것 같아 아쉽다. 남은 부트캠프 기간과 그 이후에 개발을 공부하며 하나씩 천천히 공부해보려고 한다.

3. 아쉬운 문서들 이건 컨디션 난조의 문제도 있긴 한데, 총 3편의 글 중에 크로스 브라우징을 제외한 2개는 실습을 진행한 것을 기록한 정도의 글이다. 관련 내용을 더 찾아보고 정리해서 글을 보충해놔야겠다.

🎯 앞으로의 목표

꾸준히 알고리즘 문제 풀기

코테 실력이 솔직히 많이 부족하다. 시간 복잡도 계산도 잘 못하고, 알고리즘도 많이 까먹었고... 취업을 위해서 코테는 필수인 만큼 스터디에 가입했다. 꾸준히 기출을 풀면서 알고리즘 풀이 실력을 늘려보자!

학습한 개념을 프로젝트에 적용하기

시행착오를 겪으면서 실제 프로젝트에 개념을 적용하는 경험이 중요하다. 프로젝트를 진행하면서 어떤 아키텍처 패턴이 적절할지 고민해보고, 배운 최적화 방법들을 적용하여 응답 시간을 줄여보고 싶다.

문서화 능력 기르기

개발 지식을 문서화하면서 몰랐던 부분을 알게 되는 것 같다. 단순히 A라고 이해하고 넘어갔던 개념이, 글을 쓰면서 '근데 왜 A일까?'라는 의문이 들면서 추가적으로 공부하게 된다.

최종적으로는 팀에 도움이 되는 문서를 작성할 수 있는 능력을 갖추고 싶다. 😊 인턴 때 일했던 팀에서는 개발 지식을 문서화하고 이를 공유하는 문화가 있었는데, 개인의 지식이 팀 전체의 지식으로 확장되는 경험이 너무 좋았다. 연습을 꾸준히 해서 부트캠프 중에 팀원에게 유익한 정보를 공유하고 싶다.

CS 공부하기

현직자분들의 이야기를 들어보면, 실무에서는 트러블 슈팅 과정에서 정말 폭넓은 CS를 다루게 되는 것 같다. 지금까지 겉핡기 식으로만 공부를 해왔다면, 조금이라도 깊게 공부하는 습관을 들여보려고 한다. CS는 단기간에 안된다고 생각하기 때문에 우선 프로젝트를 진행하면서 나오는 개념들을 파고드는 식으로 공부해보려고 한다.

커리큘럼 맘껏 즐기기(?)

네트워킹 데이, 해커톤, 코테, 팀 프로젝트, 현업 프로젝트, 현직자와의 상담 등 기대되는 활동이 많다. 기대되는 만큼 적극적으로 참여해야지!

자기성찰

부트캠프라는 좋은 기회를 잡은 만큼 크게 성장하고 싶기에, 정답이 없는 문제들을 고민해 볼 필요성을 느꼈다. 좁게는 개발로 이루고 싶은 목표부터 넓게는 나의 성향에 대한 것까지 폭넓게 고민해봐야겠다. 나는 시야가 좁은 사람이라 의식적으로 큰 그림을 그려야 한다. 지금의 고민하는 시간이 더 큰 학습 효과를 불러일으킬 것이라 믿는다. 그리고 눈앞의 목표인 취업을 위해 진로개발 계획을 세워야겠다. 현직자의 도움을 받을 수 있는 좋은 찬스이니 개발자로서 목표를 세울 때 큰 도움을 받을 수 있을 것이다.

회고를 마치며

바쁘게 프로젝트를 구현하다보면 처음에 목표한 만큼 해내진 못할 수 있다. 하지만 최소한 시늉이라도 내다보면 아예 안하는 것보다는 훨씬 나아질 것이다. 조급함은 덜어두고 조금씩이라도 챙기는 연습을 해보자!!

이상 1개월 차 회고를 마친다. 다들 파이팅 👊 🔥

슬로우 쿼리란? 사용자가 지정한 특정 시간(seconds) 이상 걸리는 쿼리를 의미한다.

1. MySQL 설치 및 실행

brew update 
brew install mysql 
brew services start mysql 

위에서부터 차례대로 homebrew 업데이트, mysql 설치, mysql 실행이다.

2. 샘플 DataBase 다운로드 먼저 샘플 DB를 다운받는다. 방법1. MySQL 공식 사이트에서 원하는 샘플을 다운받고 압축 해제 방법2. curl -O https://downloads.mysql.com/docs/sakila-db.tar.gz 명령어로 현재 디렉토리에 다운받고 tar -xvf sakila-db.tar.gz로 압축 해제

압축 해제하면 다운받은 샘플 DB 폴더가 생기고, 그 안에 data와 schema와 모델링 파일(.mwb)이 있다. .mwb 파일은 해당 데이터베이스의 ERD 및 인덱스를 포함한 데이터베이스 구조를 표현하는 파일이라고 한다. 나는 sakila sample db를 다운 받아서 위의 이미지와 같은 폴더가 생성됐다.

3. MySQL에 샘플 DataBase 설치 mysql -u root -p 명령어로 DB에 root라는 사용자로 접속한다. (비밀번호는 설정하지 않았을 경우 엔터 입력)

SOURCE {path}/sakila-db/sakila-schema.sql;
SOURCE {path}/sakila-db/sakila-data.sql;

{path}에는 샘플 DB가 있는 파일 경로를 입력한다. 만약 다운로드 폴더에 샘플 DB가 있다면 아래와 같이 입력한다.

SOURCE 명령어를 사용해서 파일에 있는 SQL문을 실행한다면, 성공적으로 databases와 tables이 생성된 것을 볼 수 있다.

4. 슬로우 쿼리 프로파일링 설정 먼저, my.cnf 파일을 찾아서 아래와 같이 수정한다. (homebrew로 설치한 경우 /opt/homebrew/etc 에 위치했을 가능성이 높다.)

slow_query_log 는 0 또는 1의 값을 갖는다. default 값은 0으로 슬로우 쿼리 로그를 비활성화한다. no argument거나 값이 1인 경우 슬로우 쿼리 로그가 활성화된다.

log_output 은 슬로우 쿼리를 기록할 위치를 지정한다. TABLE, FILE, NONE 값을 가지며 디폴트는 FILE이다.

slow_query_log_file 는 슬로우 쿼리 로그 파일의 경로를 지정한다.

long_query_time 는 슬로우 쿼리로 간주되는 쿼리의 실행 시간(초)을 지정한다. 기본값은 10이며, 0~31536000의 범위를 가질 수 있다. 31536000는 365일을 second로 바꾼 것이다.

5. MySQL 재시작

brew services restart mysql 로 mysql을 재시작해 변경사항을 반영한다.

추가로, 아래의 명령어를 입력하면 my.cnf 에서 설정한 값을 확인할 수 있다.

SHOW VARIABLES LIKE 'slow_query_log';
SHOW VARIABLES LIKE 'slow_query_log_file';
SHOW VARIABLES LIKE 'long_query_time';

6. 슬로우 쿼리 실행 먼저, 매우 간단한 쿼리를 실행해보자.

SELECT SLEEP(0.1);

=> 실행 시간이 0.2 sec 미만이므로 slow-query.log 에 기록 ❌

다음으로 실행 시간이 0.2 sec 초과인 쿼리를 실행해보자. SELECT SLEEP(0.5); => slow-query.log 에 정상적으로 기록 ✅

슬로우 쿼리의 시간: # Time: 2024-07-24T06:22:43.696156Z

사용자와 호스트 정보: # User@Host: root[root] @ localhost [] Id: 8 (Id: 8은 MySQL 세션의 ID)

쿼리 상세 정보: # Query_time: 0.516293 Lock_time: 0.000000 Rows_sent: 1 Rows_examined: 1

• Query_time : 쿼리가 실행되는 데 걸린 시간
• Lock_time: 쿼리 실행 중에 잠금이 걸려 있는 시간
• Rows_sent: 쿼리 결과로 전송된 행의 수
• Rows_examined: 쿼리 실행 중에 검사된 행의 수

주석 아래에는 구체적인 쿼리 내용이 서술된다.

use sakila;
SET timestamp=1721802163;
SELECT SLEEP(0.5);

sakila 데이터베이스를 사용했고, 0.5초 동안 대기하는 SELECT SLEEP(0.5); 쿼리를 실행했다는 것을 알 수 있다. 중간의 SET timestamp=1721802163; 명령은 쿼리의 시작 시간을 지정하는 역할이다. 다음 줄인 SELECT SLEEP(0.5); 쿼리의 시작 시간을 timestamp=1721802163; 으로 지정했는데, Unix 타임스탬프 형식이라 시간을 확인하기 위해서는 계산을 거쳐야 한다.

조금 더 복잡한 쿼리를 날려보자.

SELECT 
    c.customer_id,
    c.first_name,
    c.last_name,
    COUNT(rental.rental_id) AS total_rentals,
    (SELECT SUM(p.amount) 
     FROM payment p 
     WHERE p.customer_id = c.customer_id 
     AND p.payment_date > '2005-01-01') AS total_payments,
    (SELECT COUNT(*)
     FROM rental r
     JOIN inventory i ON r.inventory_id = i.inventory_id
     JOIN film f ON i.film_id = f.film_id
     WHERE r.customer_id = c.customer_id
     AND f.rating = 'R') AS r_rated_rentals
FROM 
    customer c
    LEFT JOIN rental ON c.customer_id = rental.customer_id
    LEFT JOIN payment ON c.customer_id = payment.customer_id
GROUP BY 
    c.customer_id,
    c.first_name,
    c.last_name
ORDER BY 
    total_rentals DESC
LIMIT 1000;

정상적으로 기록이 된다.

참고자료 https://dev.mysql.com/doc/refman/8.4/en/slow-query-log.html