1. 정보처리기사 취득 준비
데이터베이스 구축 과목에서는 논리 데이터베이스 설계와 물리 데이터베이스 설계에 관한 내용을 학습하였다. 사용자의 요구사항을 데이터 구조로 변환하고, 이를 실제 데이터베이스에 구현하는 전체 과정을 이해하는 데 중점을 두었다. 논리 설계에서는 데이터 간 관계와 구조를 명확하게 정의하고, 물리 설계에서는 저장 공간과 조회 성능, 무결성 등을 고려하여 실제 운영 환경에 적합한 데이터베이스를 구성하는 방법을 학습하였다.
관계 데이터베이스 모델에서는 데이터를 행과 열로 구성된 릴레이션 형태로 표현하는 방법을 학습하였다. 릴레이션은 테이블, 튜플은 행, 속성은 열에 해당하며, 각 속성이 가질 수 있는 값의 범위를 도메인이라고 한다는 점을 이해하였다. 또한 하나의 릴레이션에는 동일한 튜플이 중복될 수 없고, 튜플과 속성의 순서는 데이터의 의미에 영향을 주지 않는다는 관계형 데이터베이스의 특징을 정리하였다.
관계 데이터베이스에서 필요한 데이터를 추출하기 위해 관계 대수의 기본 연산도 학습하였다. 조건에 맞는 행을 선택하는 셀렉션, 필요한 열만 추출하는 프로젝션, 여러 릴레이션을 연결하는 조인 연산의 특징을 이해하였다. 합집합, 교집합, 차집합과 같은 집합 연산을 적용할 때는 두 릴레이션의 속성 수와 도메인이 서로 대응되어야 한다는 점도 배웠다.
데이터 모델링 및 설계에서는 현실 세계의 업무와 데이터를 개체, 속성, 관계로 분석하여 데이터베이스 구조로 표현하는 과정을 학습하였다. 요구사항 분석 결과를 바탕으로 주요 개체와 속성을 정의하고, 개체 간 관계를 ER 다이어그램으로 표현하는 개념적 데이터 모델링의 과정을 이해하였다. 이후 개념적 모델을 테이블 구조로 변환하고 기본키와 외래키를 정의하는 논리적 데이터 모델링 과정도 함께 학습하였다.
정규화에서는 데이터의 중복을 줄이고 삽입, 삭제, 갱신 이상 현상을 방지하기 위해 테이블을 분해하는 방법을 학습하였다. 제1정규형에서는 속성값의 원자성을 확보하고, 제2정규형에서는 부분 함수 종속을 제거하며, 제3정규형에서는 이행 함수 종속을 제거한다는 점을 이해하였다. 정규화는 단순히 테이블을 나누는 작업이 아니라 데이터의 일관성과 유지보수성을 높이기 위한 설계 과정이라는 점을 알 수 있었다.
물리 요소 조사 및 분석에서는 실제 데이터베이스를 구축하기 전에 데이터의 양, 증가 속도, 조회 빈도, 갱신 빈도, 응답 시간, 저장 공간 등의 운영 조건을 분석하는 방법을 학습하였다. 동일한 논리적 데이터 모델이라도 사용 환경과 처리량에 따라 물리적 설계가 달라질 수 있으며, 자주 조회되는 데이터와 자주 변경되는 데이터를 구분하여 저장 구조를 설계해야 한다는 점을 이해하였다.
DB 물리 속성 설계에서는 논리 데이터 모델에서 정의한 속성을 실제 데이터베이스의 컬럼으로 구현하는 방법을 학습하였다. 각 컬럼에 적절한 데이터 타입과 길이를 지정하고, 기본값과 NULL 허용 여부, 제약조건을 설정하는 과정을 정리하였다. 데이터 타입을 지나치게 크게 설정하면 저장 공간이 낭비될 수 있고, 반대로 너무 작게 설정하면 정상적인 데이터가 저장되지 않을 수 있으므로 실제 데이터의 범위와 사용 목적을 고려해야 한다는 점을 배웠다.
인덱스 설계에서는 특정 데이터의 검색 속도를 높이기 위해 별도의 접근 경로를 구성하는 방법을 학습하였다. 조회 조건이나 조인 조건에 자주 사용되는 컬럼에 인덱스를 적용하면 검색 성능을 높일 수 있지만, 데이터가 추가되거나 변경될 때 인덱스도 함께 갱신되므로 삽입과 수정 성능에는 부담이 될 수 있다는 점을 이해하였다. 따라서 모든 컬럼에 인덱스를 생성하는 것이 아니라 조회 빈도와 선택도, 데이터 변경 빈도를 고려하여 설계해야 한다는 점을 알 수 있었다.
데이터베이스 무결성과 키에서는 데이터의 정확성과 일관성을 유지하기 위한 제약조건을 학습하였다. 기본키는 각 튜플을 유일하게 식별하며 중복값과 NULL을 허용하지 않고, 외래키는 다른 테이블의 기본키를 참조하여 테이블 간 관계를 표현한다는 점을 정리하였다. 후보키, 기본키, 대체키, 슈퍼키의 차이를 구분하고, 외래키를 통해 참조 무결성을 유지해야 한다는 점을 이해하였다.
개체 무결성은 기본키에 NULL이나 중복값이 입력되지 않도록 하는 규칙이며, 참조 무결성은 외래키가 참조하는 값이 부모 테이블에 존재하도록 하는 규칙이라는 점을 학습하였다. 도메인 무결성은 속성에 정의된 데이터 타입과 범위에 맞는 값만 입력되도록 제한하는 방식으로, 각 무결성 제약조건이 데이터 오류를 예방하는 역할을 한다는 점을 이해하였다.
DB 반정규화에서는 정규화된 데이터 구조의 조회 성능을 높이기 위해 의도적으로 데이터 중복을 허용하는 방법을 학습하였다. 자주 조인되는 테이블을 통합하거나, 반복적으로 계산되는 값을 별도의 컬럼에 저장하고, 필요한 테이블을 중복 생성하여 조회 경로를 단축할 수 있다는 점을 이해하였다.
반정규화를 적용하면 조회 속도와 시스템 응답 시간을 개선할 수 있지만, 같은 데이터가 여러 위치에 저장되므로 데이터 수정 시 모든 값을 일관되게 변경해야 한다는 부담이 발생한다. 따라서 반정규화는 단순히 테이블을 합치는 작업이 아니라 정규화된 구조에서 실제 성능 문제가 확인되었을 때 적용해야 하며, 데이터 정합성을 유지할 수 있는 관리 방안도 함께 마련해야 한다는 점을 배웠다.
이번 학습을 통해 논리 데이터베이스 설계는 데이터의 관계와 구조를 정확하게 표현하는 과정이고, 물리 데이터베이스 설계는 이를 실제 시스템 환경에 맞게 구현하고 최적화하는 과정이라는 점을 이해하였다. 또한 정규화, 인덱스, 무결성, 반정규화는 각각 독립된 개념이 아니라 데이터의 일관성과 성능 사이에서 적절한 균형을 찾기 위해 함께 고려해야 하는 요소라는 점을 알 수 있었다.
2. 코딩테스트 공부
# =========================================================
# 1. 연산자 끼워 넣기
# 주어진 수의 순서는 유지하고 연산자의 배치를 완전탐색하여
# 계산 결과의 최댓값과 최솟값을 구하는 문제
# =========================================================
def operator_insertion(numbers, operators):
maximum = -float("inf")
minimum = float("inf")
def calculate(left, right, operator):
if operator == 0:
return left + right
if operator == 1:
return left - right
if operator == 2:
return left * right
# 음수 나눗셈은 0을 향해 버림
if left < 0:
return -((-left) // right)
return left // right
def backtrack(index, current_value):
nonlocal maximum, minimum
if index == len(numbers):
maximum = max(maximum, current_value)
minimum = min(minimum, current_value)
return
for operator in range(4):
if operators[operator] == 0:
continue
operators[operator] -= 1
next_value = calculate(
current_value,
numbers[index],
operator
)
backtrack(index + 1, next_value)
operators[operator] += 1
backtrack(1, numbers[0])
return maximum, minimum
numbers = [3, 4, 5]
operators = [1, 0, 1, 0]
maximum, minimum = operator_insertion(numbers, operators)
print("연산 결과의 최댓값:", maximum)
print("연산 결과의 최솟값:", minimum)
# =========================================================
# 2. N-Queen
# 같은 열과 대각선에 퀸이 배치되지 않도록 가지치기하며
# N개의 퀸을 배치하는 모든 경우의 수를 계산
# =========================================================
def count_n_queens(n):
columns = [False] * n
diagonal_down = [False] * (2 * n - 1)
diagonal_up = [False] * (2 * n - 1)
count = 0
def backtrack(row):
nonlocal count
if row == n:
count += 1
return
for col in range(n):
down_index = row - col + n - 1
up_index = row + col
if columns[col]:
continue
if diagonal_down[down_index]:
continue
if diagonal_up[up_index]:
continue
columns[col] = True
diagonal_down[down_index] = True
diagonal_up[up_index] = True
backtrack(row + 1)
columns[col] = False
diagonal_down[down_index] = False
diagonal_up[up_index] = False
backtrack(0)
return count
print("8-Queen 배치 경우의 수:", count_n_queens(8))
# =========================================================
# 3. 부분 수열의 합
# 각 숫자를 선택하거나 선택하지 않는 모든 경우를 탐색하여
# 목표값을 만드는 부분 수열의 개수를 계산
# =========================================================
def count_subsequence_sum(numbers, target):
count = 0
def backtrack(index, current_sum, selected_count):
nonlocal count
if index == len(numbers):
if selected_count > 0 and current_sum == target:
count += 1
return
# 현재 숫자를 선택
backtrack(
index + 1,
current_sum + numbers[index],
selected_count + 1
)
# 현재 숫자를 선택하지 않음
backtrack(
index + 1,
current_sum,
selected_count
)
backtrack(0, 0, 0)
return count
numbers = [-7, -3, -2, 5, 8]
target = 0
print(
"목표 합을 만드는 부분 수열의 개수:",
count_subsequence_sum(numbers, target)
)
# =========================================================
# 4. 연구소 안전 영역
# 빈칸 중 세 곳에 벽을 설치하는 모든 조합을 확인하고,
# 바이러스가 퍼진 뒤 남는 안전 영역의 최댓값 계산
# =========================================================
from collections import deque
from itertools import combinations
def maximum_safe_area(lab):
rows = len(lab)
cols = len(lab[0])
empty_cells = []
virus_cells = []
for row in range(rows):
for col in range(cols):
if lab[row][col] == 0:
empty_cells.append((row, col))
elif lab[row][col] == 2:
virus_cells.append((row, col))
directions = [
(-1, 0),
(1, 0),
(0, -1),
(0, 1)
]
maximum = 0
for walls in combinations(empty_cells, 3):
copied = [row[:] for row in lab]
for row, col in walls:
copied[row][col] = 1
queue = deque(virus_cells)
while queue:
row, col = queue.popleft()
for dr, dc in directions:
next_row = row + dr
next_col = col + dc
if not (
0 <= next_row < rows
and 0 <= next_col < cols
):
continue
if copied[next_row][next_col] != 0:
continue
copied[next_row][next_col] = 2
queue.append((next_row, next_col))
safe_area = sum(
copied[row][col] == 0
for row in range(rows)
for col in range(cols)
)
maximum = max(maximum, safe_area)
return maximum
lab = [
[2, 0, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 1, 2, 0],
[0, 1, 1, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 1],
[0, 1, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0]
]
print("최대 안전 영역:", maximum_safe_area(lab))
# =========================================================
# 5. 스도쿠 풀이
# 빈칸에 가능한 숫자를 넣고 조건을 만족하지 않으면
# 이전 상태로 돌아가 다른 숫자를 선택
# =========================================================
def solve_sudoku(board):
empty_cells = []
rows = [set() for _ in range(9)]
columns = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for row in range(9):
for col in range(9):
value = board[row][col]
if value == 0:
empty_cells.append((row, col))
continue
rows[row].add(value)
columns[col].add(value)
boxes[(row // 3) * 3 + col // 3].add(value)
def backtrack(index):
if index == len(empty_cells):
return True
row, col = empty_cells[index]
box_index = (row // 3) * 3 + col // 3
for number in range(1, 10):
if number in rows[row]:
continue
if number in columns[col]:
continue
if number in boxes[box_index]:
continue
board[row][col] = number
rows[row].add(number)
columns[col].add(number)
boxes[box_index].add(number)
if backtrack(index + 1):
return True
board[row][col] = 0
rows[row].remove(number)
columns[col].remove(number)
boxes[box_index].remove(number)
return False
backtrack(0)
return board
sudoku = [
[0, 3, 5, 4, 6, 9, 2, 7, 8],
[7, 8, 2, 1, 0, 5, 6, 0, 9],
[0, 6, 0, 2, 7, 8, 1, 3, 5],
[3, 2, 1, 0, 4, 6, 8, 9, 7],
[8, 0, 4, 9, 1, 3, 5, 0, 6],
[5, 9, 6, 8, 2, 0, 4, 1, 3],
[9, 1, 7, 6, 5, 2, 0, 8, 0],
[6, 0, 3, 7, 0, 1, 9, 5, 2],
[2, 5, 8, 3, 9, 4, 7, 6, 0]
]
solved_sudoku = solve_sudoku(sudoku)
print("스도쿠 풀이 결과:")
for row in solved_sudoku:
print(*row)
# =========================================================
# 6. 외판원 순회
# 한 도시에서 출발해 모든 도시를 한 번씩 방문하고
# 출발점으로 돌아오는 최소 비용을 백트래킹으로 탐색
# =========================================================
def travelling_salesman(costs):
n = len(costs)
visited = [False] * n
minimum_cost = float("inf")
visited[0] = True
def backtrack(current, visited_count, total_cost):
nonlocal minimum_cost
# 현재 비용이 이미 최적값 이상이면 탐색 중단
if total_cost >= minimum_cost:
return
if visited_count == n:
return_cost = costs[current][0]
if return_cost != 0:
minimum_cost = min(
minimum_cost,
total_cost + return_cost
)
return
for next_city in range(1, n):
if visited[next_city]:
continue
if costs[current][next_city] == 0:
continue
visited[next_city] = True
backtrack(
next_city,
visited_count + 1,
total_cost + costs[current][next_city]
)
visited[next_city] = False
backtrack(0, 1, 0)
return minimum_cost
costs = [
[0, 10, 15, 20],
[5, 0, 9, 10],
[6, 13, 0, 12],
[8, 8, 9, 0]
]
print(
"모든 도시를 순회하는 최소 비용:",
travelling_salesman(costs)
)이번 주에는 코딩테스트 대비를 위해 완전탐색과 백트래킹 유형의 문제 풀이를 진행하였다. 완전탐색은 가능한 모든 경우를 빠짐없이 확인하여 정답을 구하는 방식이며, 백트래킹은 탐색 도중 현재 선택이 조건을 만족할 수 없다고 판단되면 이전 단계로 돌아가 다른 선택을 시도하는 방식이라는 점을 이해하였다.
완전탐색 문제를 해결할 때는 먼저 전체 경우의 수가 입력 범위 안에서 실제로 탐색 가능한 크기인지 판단해야 한다. 반복문, 순열, 조합, 부분집합, 비트마스크, 재귀 함수 등을 활용하여 모든 후보를 생성할 수 있지만, 입력의 크기가 커지면 경우의 수가 급격하게 증가하므로 시간 복잡도를 먼저 계산하는 것이 중요하다는 점을 학습하였다.
연산자 끼워 넣기 유형에서는 숫자의 순서는 유지하면서 주어진 연산자를 배치하는 모든 경우를 재귀적으로 탐색하였다. 각 단계에서 사용할 수 있는 연산자의 개수를 하나씩 줄이고, 탐색이 끝난 뒤 다시 복구하는 방식으로 같은 연산자 개수 정보를 재사용하였다. 이를 통해 별도의 연산자 순열을 모두 저장하지 않고도 모든 계산 결과를 확인할 수 있었다.
N-Queen 유형에서는 각 행마다 하나의 퀸을 배치하되, 같은 열과 대각선에 이미 퀸이 존재하는 경우 해당 선택을 즉시 제외하였다. 모든 칸에 퀸을 놓아본 뒤 마지막에 조건을 검사하는 것보다, 퀸을 배치하는 순간 열과 대각선 조건을 확인하는 것이 탐색 범위를 크게 줄일 수 있다는 점을 이해하였다.
부분 수열의 합 유형에서는 각 숫자를 선택하는 경우와 선택하지 않는 경우로 나누어 모든 부분집합을 탐색하였다. 원소가 N개라면 가능한 선택 상태가 2의 N제곱개가 되며, 재귀 함수의 각 단계가 하나의 원소에 대한 선택 여부를 의미한다는 점을 학습하였다. 또한 아무 원소도 선택하지 않은 공집합을 정답에서 제외해야 하는 경우 선택한 원소의 개수를 별도로 관리해야 한다는 점도 배웠다.
연구소 안전 영역 유형에서는 빈칸 가운데 세 곳을 선택하여 벽을 세우는 모든 조합을 생성하고, 각 조합마다 BFS를 실행하여 바이러스의 확산 결과를 확인하였다. 이 문제를 통해 완전탐색은 다른 알고리즘과 결합하여 사용할 수 있으며, 후보 상태는 조합으로 생성하고 각 상태의 결과는 그래프 탐색으로 평가할 수 있다는 점을 이해하였다.
스도쿠 유형에서는 빈칸에 들어갈 수 있는 숫자를 하나씩 넣고, 행과 열, 3×3 구역의 조건을 만족하지 못하면 이전 선택을 취소하였다. 숫자를 넣은 뒤 다음 빈칸으로 이동하고, 정답을 찾지 못하면 해당 숫자를 제거하여 상태를 원래대로 복구하는 백트래킹의 기본 구조를 연습하였다.
스도쿠의 각 빈칸에서 1부터 9까지 모든 숫자를 단순하게 시도할 수도 있지만, 이미 행과 열, 구역에 존재하는 숫자를 집합으로 관리하면 불가능한 후보를 빠르게 제외할 수 있었다. 이를 통해 가지치기의 효율은 조건 검사에 필요한 정보를 어떤 자료구조로 관리하는지에 따라서도 달라질 수 있다는 점을 알 수 있었다.
외판원 순회 유형에서는 현재 도시에서 아직 방문하지 않은 도시로 이동하는 모든 순서를 탐색하고, 모든 도시를 방문한 뒤 출발 도시로 돌아오는 비용을 계산하였다. 방문 배열을 통해 같은 도시의 중복 방문을 방지하고, 현재까지의 비용이 이미 구한 최솟값보다 크거나 같으면 이후 탐색을 중단하는 방식으로 가지치기를 적용하였다.
순열 유형에서는 선택 순서에 따라 결과가 달라지므로 방문 배열을 이용하여 아직 선택하지 않은 원소를 하나씩 추가해야 한다는 점을 학습하였다. 조합 유형에서는 선택 순서가 결과에 영향을 주지 않으므로 다음 탐색을 현재 인덱스 이후부터 시작하여 동일한 원소 집합이 다른 순서로 중복 생성되는 것을 방지해야 한다는 차이를 이해하였다.
백트래킹에서는 선택, 재귀 호출, 상태 복구의 세 단계가 정확하게 이루어져야 한다는 점을 학습하였다. 선택 과정에서 방문 배열이나 개수, 합계 등을 변경했다면 재귀 호출이 끝난 뒤 반드시 이전 상태로 돌려놓아야 다른 탐색 경로가 영향을 받지 않는다. 상태를 제대로 복구하지 않으면 아직 선택하지 않은 후보가 이미 사용된 것으로 처리되는 오류가 발생할 수 있다는 점을 알 수 있었다.
가지치기에서는 현재 상태가 이미 문제의 조건을 위반했거나, 이후 어떤 선택을 하더라도 기존의 최적 결과보다 좋아질 수 없는 경우 탐색을 중단하였다. N-Queen에서는 열과 대각선의 충돌 여부를 검사했고, 외판원 순회에서는 현재 누적 비용과 기존 최솟값을 비교하였다. 문제마다 가지치기의 기준은 다르지만, 현재 상태만으로 이후 탐색의 필요성을 판단한다는 공통점을 이해하였다.
완전탐색과 백트래킹은 입력 크기가 작은 문제에서 강력하게 활용할 수 있지만, 모든 경우를 무조건 탐색하면 시간 제한을 초과할 수 있다는 점도 학습하였다. 원소가 N개인 순열은 N팩토리얼, 부분집합은 2의 N제곱, 중복 선택은 선택지 수의 깊이제곱만큼 경우의 수가 증가하므로 문제의 제한을 보고 탐색 가능 여부를 먼저 판단해야 한다.
이번 학습을 통해 완전탐색은 정답 후보를 빠짐없이 만드는 것이 핵심이고, 백트래킹은 후보를 만드는 과정에서 불필요한 탐색을 줄이는 것이 핵심이라는 점을 이해하였다. 두 방식은 서로 완전히 다른 알고리즘이라기보다, 완전탐색의 구조에 조건 검사와 가지치기를 추가하여 효율을 높인 관계라는 점을 알 수 있었다.
또한 문제를 해결할 때 단순히 재귀 함수를 작성하는 것보다 현재 단계에서 무엇을 선택하는지, 종료 조건은 무엇인지, 어떤 상태를 저장하고 복구해야 하는지, 어느 시점에서 가지치기를 할 수 있는지를 먼저 정의해야 한다는 점을 배웠다. 완전탐색과 백트래킹 문제는 코드의 형태를 암기하기보다 탐색 트리의 각 깊이와 선택 상태를 명확하게 설계하는 것이 중요하다는 점을 이해하였다.
