1. 정보처리기사 취득 준비
프로그래밍 언어 활용 과목에서는 서버 프로그램 구현, 프로그래밍 언어 활용, 응용 소프트웨어 기초 기술 활용에 관한 내용을 학습하였다. 단순히 프로그래밍 문법을 암기하는 것에 그치지 않고, 프로그램이 서버와 운영체제에서 실행되고 데이터를 처리하는 전체적인 원리를 이해하는 데 중점을 두었다.
서버 프로그램 구현에서는 사용자의 요청을 전달받아 필요한 작업을 수행하고 그 결과를 반환하는 서버 프로그램의 기본 구조를 학습하였다. 서버 프로그램은 입력된 요청을 분석한 뒤 데이터베이스 조회, 비즈니스 로직 처리, 결과 반환의 과정을 거쳐 동작한다는 점을 이해하였다. 또한 여러 기능에서 공통으로 사용되는 코드를 별도의 모듈로 분리하면 코드의 중복을 줄이고 유지보수성을 높일 수 있다는 점을 배웠다. 정해진 시간이나 조건에 따라 자동으로 작업을 처리하는 배치 프로그램의 특징과 오류 발생 시 예외를 처리하고 실행 결과를 기록하는 방법도 함께 학습하였다.
프로그래밍 언어 활용에서는 변수, 자료형, 연산자, 조건문, 반복문, 함수 등 프로그램을 구성하는 기본 문법을 정리하였다. 배열, 리스트, 스택, 큐와 같은 자료구조를 이용하여 데이터를 저장하고 처리하는 방법을 학습하고, 문제의 조건에 따라 적절한 자료구조를 선택해야 한다는 점을 이해하였다. 또한 클래스와 객체, 캡슐화, 상속, 다형성과 같은 객체지향 프로그래밍의 주요 개념을 학습하였다. 이를 통해 프로그램을 기능별 객체로 분리하면 코드의 재사용성과 확장성을 높일 수 있다는 점을 알 수 있었다.
응용 소프트웨어 기초 기술 활용에서는 운영체제, 데이터베이스, 네트워크와 관련된 기본 개념을 학습하였다. 운영체제 부분에서는 프로세스와 스레드의 차이, CPU 스케줄링, 기억장치 관리, 교착상태의 발생 조건과 해결 방법을 살펴보았다. 데이터베이스 부분에서는 트랜잭션의 특성, 데이터 무결성, 병행 제어, 회복 기법을 학습하였다. 네트워크 부분에서는 OSI 7계층과 TCP/IP 구조, IP 주소, 포트 번호, 주요 프로토콜의 역할을 정리하였다.
이번 학습을 통해 프로그램은 작성된 코드만으로 동작하는 것이 아니라 운영체제, 데이터베이스, 네트워크, 서버 환경과 상호작용하며 실행된다는 점을 이해하였다. 또한 정보처리기사 문제를 풀 때 개별 용어만 암기하기보다 각 기술이 실제 시스템에서 어떤 역할을 수행하는지를 연결하여 학습하는 것이 중요하다는 점을 알 수 있었다.
2. 코딩테스트 공부
from collections import deque
# =========================================================
# 1. DFS - 연결 요소의 개수 구하기
# 서로 연결된 정점들을 하나의 그룹으로 보고,
# 그래프에 몇 개의 독립된 그룹이 존재하는지 계산
# =========================================================
def count_connected_components(n, edges):
graph = [[] for _ in range(n + 1)]
for start, end in edges:
graph[start].append(end)
graph[end].append(start)
visited = [False] * (n + 1)
def dfs(start):
stack = [start]
visited[start] = True
while stack:
current = stack.pop()
for next_node in graph[current]:
if not visited[next_node]:
visited[next_node] = True
stack.append(next_node)
component_count = 0
for node in range(1, n + 1):
if not visited[node]:
dfs(node)
component_count += 1
return component_count
n = 7
edges = [
(1, 2),
(2, 3),
(4, 5),
(6, 7)
]
print(
"연결 요소의 개수:",
count_connected_components(n, edges)
)
# =========================================================
# 2. BFS - 미로의 최단 거리 구하기
# 1은 이동 가능한 칸, 0은 이동할 수 없는 칸
# 시작점에서 도착점까지 이동하는 최소 칸 수 계산
# =========================================================
def shortest_maze_path(maze):
rows = len(maze)
cols = len(maze[0])
queue = deque([(0, 0)])
distance = [[-1] * cols for _ in range(rows)]
distance[0][0] = 1
directions = [
(-1, 0),
(1, 0),
(0, -1),
(0, 1)
]
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 maze[next_row][next_col] == 0:
continue
if distance[next_row][next_col] != -1:
continue
distance[next_row][next_col] = distance[row][col] + 1
queue.append((next_row, next_col))
return distance[rows - 1][cols - 1]
maze = [
[1, 1, 0, 1, 1],
[0, 1, 0, 1, 0],
[1, 1, 1, 1, 0],
[1, 0, 0, 1, 1],
[1, 1, 1, 0, 1]
]
print(
"미로의 최단 이동 거리:",
shortest_maze_path(maze)
)
# =========================================================
# 3. DFS - 경로 존재 여부 확인
# 출발 정점에서 목표 정점까지 이동할 수 있는지 확인
# 방향성이 있는 그래프를 인접 리스트로 표현
# =========================================================
def has_path(graph, start, target):
visited = set()
stack = [start]
while stack:
current = stack.pop()
if current == target:
return True
if current in visited:
continue
visited.add(current)
for next_node in graph.get(current, []):
if next_node not in visited:
stack.append(next_node)
return False
directed_graph = {
1: [2, 3],
2: [4],
3: [5],
4: [6],
5: [],
6: []
}
print(
"1번에서 6번까지 경로 존재 여부:",
has_path(directed_graph, 1, 6)
)
# =========================================================
# 4. BFS - 특정 거리의 도시 찾기
# 시작 정점에서 정확히 K개의 간선을 지나 도착하는 정점 탐색
# =========================================================
def find_nodes_at_distance(n, edges, start, target_distance):
graph = [[] for _ in range(n + 1)]
for from_node, to_node in edges:
graph[from_node].append(to_node)
distance = [-1] * (n + 1)
distance[start] = 0
queue = deque([start])
while queue:
current = queue.popleft()
for next_node in graph[current]:
if distance[next_node] == -1:
distance[next_node] = distance[current] + 1
queue.append(next_node)
result = []
for node in range(1, n + 1):
if distance[node] == target_distance:
result.append(node)
return result
n = 6
edges = [
(1, 2),
(1, 3),
(2, 4),
(3, 4),
(3, 5),
(4, 6)
]
print(
"1번 정점에서 거리가 2인 정점:",
find_nodes_at_distance(n, edges, 1, 2)
)
# =========================================================
# 5. BFS - 이분 그래프 판별
# 인접한 두 정점이 서로 다른 그룹에 속하도록
# 그래프를 두 가지 색으로 구분할 수 있는지 확인
# =========================================================
def is_bipartite_graph(n, edges):
graph = [[] for _ in range(n + 1)]
for start, end in edges:
graph[start].append(end)
graph[end].append(start)
color = [0] * (n + 1)
for start in range(1, n + 1):
if color[start] != 0:
continue
queue = deque([start])
color[start] = 1
while queue:
current = queue.popleft()
for next_node in graph[current]:
if color[next_node] == 0:
color[next_node] = -color[current]
queue.append(next_node)
elif color[next_node] == color[current]:
return False
return True
n = 5
edges = [
(1, 2),
(2, 3),
(3, 4),
(4, 5),
(5, 1)
]
print(
"이분 그래프 여부:",
is_bipartite_graph(n, edges)
)
# =========================================================
# 6. DFS - 섬의 개수와 크기 구하기
# 2차원 지도에서 상하좌우로 연결된 땅을 하나의 섬으로 판단
# =========================================================
def find_islands(grid):
rows = len(grid)
cols = len(grid[0])
visited = [[False] * cols for _ in range(rows)]
directions = [
(-1, 0),
(1, 0),
(0, -1),
(0, 1)
]
def dfs(start_row, start_col):
stack = [(start_row, start_col)]
visited[start_row][start_col] = True
size = 0
while stack:
row, col = stack.pop()
size += 1
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 grid[next_row][next_col] == 0:
continue
if visited[next_row][next_col]:
continue
visited[next_row][next_col] = True
stack.append((next_row, next_col))
return size
island_sizes = []
for row in range(rows):
for col in range(cols):
if grid[row][col] == 1 and not visited[row][col]:
island_sizes.append(dfs(row, col))
island_sizes.sort()
return len(island_sizes), island_sizes
grid = [
[1, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 1, 0, 0],
[1, 1, 1, 0, 1],
[0, 1, 0, 0, 1]
]
island_count, island_sizes = find_islands(grid)
print("섬의 개수:", island_count)
print("각 섬의 크기:", island_sizes)이번 주에는 코딩테스트 대비를 위해 그래프의 기본 표현 방법과 DFS, BFS를 활용한 다양한 유형의 문제 풀이를 진행하였다. 단순히 정점을 정해진 순서로 방문하는 문제뿐만 아니라 연결 요소의 개수, 경로 존재 여부, 최단 거리, 특정 거리의 정점 탐색, 이분 그래프 판별, 2차원 영역 탐색 문제를 함께 학습하였다.
그래프 기본 유형에서는 정점과 간선으로 대상 간의 연결 관계를 표현하고, 주어진 간선 정보를 인접 리스트로 변환하는 방법을 연습하였다. 인접 리스트는 각 정점과 직접 연결된 정점만 저장하기 때문에 간선의 수가 상대적으로 적은 그래프를 효율적으로 표현할 수 있다는 점을 이해하였다.
연결 요소 탐색 유형에서는 아직 방문하지 않은 정점을 발견할 때마다 DFS를 새롭게 실행하였다. 한 번의 DFS에서 방문되는 모든 정점은 서로 연결된 하나의 그룹에 해당하며, 탐색을 시작한 횟수를 세면 그래프 전체의 연결 요소 개수를 구할 수 있다는 원리를 학습하였다.
경로 존재 여부 유형에서는 출발 정점부터 DFS를 수행하면서 목표 정점에 도달할 수 있는지 확인하였다. 모든 경로를 직접 저장하지 않더라도 방문 가능한 정점을 탐색하는 과정에서 목표 정점이 발견되는지를 검사하면 경로의 존재 여부를 판단할 수 있다는 점을 이해하였다.
격자와 영역 탐색 유형에서는 2차원 배열의 각 칸을 하나의 정점으로 보고, 상하좌우로 이동할 수 있는 관계를 간선으로 해석하였다. 이동할 좌표가 배열의 범위 안에 있는지, 이동 가능한 칸인지, 이미 방문한 칸인지 차례대로 검사하는 방식으로 섬의 개수와 각 섬의 크기를 계산하였다.
BFS 최단 거리 유형에서는 시작점에서 가까운 위치부터 단계적으로 탐색하였다. 가중치가 없는 그래프에서는 BFS를 통해 어떤 정점에 처음 도착했을 때의 거리가 최단 거리가 되므로, 미로의 최소 이동 횟수나 도시 간 최소 이동 횟수를 구하는 문제에 활용할 수 있다는 점을 학습하였다.
특정 거리 탐색 유형에서는 각 정점의 방문 여부만 저장하는 대신 시작점으로부터의 거리를 배열에 기록하였다. 현재 정점의 거리보다 1만큼 큰 값을 다음 정점에 저장하여, 탐색이 끝난 뒤 정확히 지정된 거리에 있는 정점만 찾는 방법을 연습하였다.
이분 그래프 판별 유형에서는 서로 연결된 정점들이 같은 그룹에 속하지 않도록 두 가지 색을 번갈아 지정하였다. 아직 색이 정해지지 않은 정점에는 현재 정점과 반대되는 색을 지정하고, 이미 같은 색으로 지정된 두 정점이 연결되어 있다면 이분 그래프가 아니라는 방식으로 판별하였다.
DFS는 하나의 경로를 가능한 깊게 탐색하기 때문에 연결된 영역의 크기, 경로 존재 여부, 연결 요소의 개수 등을 확인하는 문제에 활용하였다. 재귀 함수로도 구현할 수 있지만, 실습에서는 스택을 직접 사용하여 탐색 순서를 명확하게 확인하고 입력 규모가 큰 경우 발생할 수 있는 재귀 깊이 문제를 줄였다.
BFS는 큐를 사용하여 시작점에서 가까운 정점부터 순서대로 탐색하였다. 정점을 큐에서 꺼낼 때가 아니라 큐에 추가하는 시점에 방문 처리해야 같은 정점이 중복으로 들어가는 것을 방지할 수 있다는 점도 함께 학습하였다.
이번 학습을 통해 그래프 문제에서는 먼저 문제의 대상을 정점과 간선으로 어떻게 표현할 것인지 판단하는 과정이 중요하다는 점을 이해하였다. 또한 단순한 방문이 목적인지, 연결된 영역을 찾아야 하는지, 최단 거리를 구해야 하는지에 따라 DFS와 BFS 중 적절한 탐색 방법을 선택해야 한다는 점을 알 수 있었다.
같은 그래프 탐색 알고리즘을 사용하더라도 문제에서 요구하는 결과에 따라 방문 여부, 거리, 색상, 영역의 크기 등 추가로 저장해야 하는 정보가 달라진다는 점도 이해하였다. 이를 통해 DFS와 BFS의 구현 코드를 단순히 암기하기보다, 문제의 조건에 맞게 탐색 과정과 저장 정보를 변형하는 연습이 필요하다는 점을 배웠다.
