zuryeong의 개발 블로그

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

# 학습 키워드

1. 그래프 탐색 

그래프를 순회하면서 연결된 노드를 탐색하는 기법

2. 깊이우선 탐색 (DFS)

재귀나 스택을 통해 한 경로를 끝까지 탐색하고, 백트래킹하여 다른 경로를 탐색하는 방법

3. 백트래킹

특정 조건을 만족하지 않는 경로를 중간에 포기하고 돌아오는 기법

# 문제 접근 방식

1. 주어진 문제는 특정 시작점에서 목적지까지의 이동 가능 여부를 판단하는 문제로, 그래프 탐색 알고리즘 중 하나인 dfs를 사용하는 것이 적합하다.

2. 특정 정점(곰이 있는 위치)으로는 이동할 수 없으므로 이를 확인하기 위해 별도의 리스트나 딕셔너리로 곰이 위치한 노드를 기록해두어야 한다.

3. 각 노드 방문 여부를 기록하여 dfs 과정에서 사이클을 방지한다

4. 마지막 노드까지 도달했을 때 (즉, 더 이상 탐색할 연결 노드가 없을 때) yes를 출력하고 종료해야 한다

# 코드 작성

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100001)

def dfs(now_v):
    if visited[now_v] or now_v in is_bear:
        return
    visited[now_v] = True

    if not graph[now_v]:
        print("yes")
        exit(0)

    for next_v in graph[now_v]:
        if next_v not in is_bear and not visited[next_v]:
            dfs(next_v)
            visited[next_v] = False

if __name__ == "__main__":
    N, M = map(int, input().split())

    graph = [[] for _ in range(N + 1)]
    visited = [False] * (N + 1)
    for _ in range(M):
        v1, v2 = map(int, input().split())
        graph[v1].append(v2)

    S = int(input())
    is_bear = {}
    s = list(map(int, input().split()))
    for _s in s:
        is_bear[_s] = True

    dfs(1)
    print("Yes")

# 회고

1. 재귀 깊이 설정의 필요성

노드가 최대 100,000개까지 가능하므로 기본 재귀 깊이 제한(1,000)으로는 부족하다. sys.setrecursionlimit(100001)로 제한을 늘려줘야 RecursionError 없이 DFS 탐색을 할 수 있었다. 파이썬에서 DFS로 깊은 그래프를 탐색할 때는 필수적인 설정임을 다시 확인하였다.

2. 백트래킹을 통한 방문 초기화

DFS에서 특정 경로 탐색 후, 다른 경로도 탐색할 수 있도록 방문 상태를 초기화(visited[next_v] = False)하였다. 백트래킹을 적용하지 않으면 경로 접근이 제한되어 잘못된 결과를 출력할 수 있다. 이번 문제를 통해 DFS의 백트래킹이 정확한 탐색을 위한 핵심이라는 것을 다시 배웠다.

3. 곰이 있는 위치 관리 방법

곰이 있는 노드를 리스트 대신 딕셔너리로 관리하여, 접근 제한 여부를 평균 상수 시간(O(1))에 확인할 수 있도록 최적화하였다. 곰이 위치한 노드가 많을수록 리스트보다 딕셔너리가 훨씬 효율적이었으며, 문제 조건에 맞게 자료구조를 선택하는 것이 코드 효율성에 크게 기여함을 실감하였다.

4. 종료 조건 설정의 효과

경로 끝에 도달하거나 더 이상 이동할 수 없는 경우 바로 "yes"를 출력하고 종료하도록 하여 불필요한 탐색을 줄였다. 중간에 탐색을 종료함으로써 대규모 데이터에서 성능을 높일 수 있는 방법을 다시 상기하였다.

단순한 DFS 구현에서 더 나아가 탐색 조건 설정과 자료구조 선택의 중요성을 체감하였다. 최적화된 탐색을 위해서는 문제 조건에 맞는 자료구조와 종료 조건 설정이 필수적임을 깨달았고, 앞으로도 이러한 부분에 유의하며 코딩할 것이다.

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

# 학습 키워드
1. BFS(너비우선탐색)

2. 최단경로탐색

3. 그래프 표현

# 문제접근방식

1. 그래프 초기화

입력된 도시와 도로 정보를 기반으로 인접 리스트 형식의 그래프를 구성한다

2. BFS 탐색

시작 도시에서부터 BFS를 수행하면서 각 도시의 거리를 distance 리스트에 저장한다

3. 조건 확인

BFS 탐색 중 특정 거리 k에 도달하면, 해당 도시를 결과 리스트에 추가하고, 최종적으로 정렬하여 출력한다.

4. 예외 처리

k 거리만큼 떨어진 도시가 없을 경우 -1을 출력하도록 예외 처리를 추가한다.

# 코드작성

from collections import deque
import sys
f = sys.stdin.readline

n, m, k, x = map(int, f().split())
graph = [[] for _ in range(n+1)]
distance = [0] * (n+1)
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, f().split())
    graph[a].append(b)

def bfs(start):
    answer = []
    q = deque([start])
    visited[start] = True
    distance[start] = 0
    while q:
        now = q.popleft()
        for i in graph[now]:
            if not visited[i]:
                visited[i] = True
                q.append(i)
                distance[i] = distance[now] + 1
                if distance[i] == k:
                    answer.append(i)
    if len(answer) == 0:
        print(-1)
    else:
        answer.sort()
        for i in answer:
            print(i, end='\n')

bfs(x)

#회고

이 문제를 풀면서 BFS의 활용을 다시 한번 점검할 수 있었습니다. 특히 최단 거리를 계산할 때 BFS가 가지는 장점이 잘 발휘되는 문제였다고 생각합니다. 단순히 특정 거리의 도시에 도달하는 것이 아닌, 최단 거리 조건에 맞추어 예외 상황을 처리해야 했던 점에서 조건 분기와 예외 처리가 중요했습니다.

특히 이 문제는 k 거리에 해당하는 도시가 없을 때 -1을 출력하는 조건을 놓치지 않도록 주의해야 했습니다. 예외 처리를 통해 조건에 따른 출력을 명확히 함으로써 안정적인 코드를 작성할 수 있었습니다.

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

# 학습 키워드

1. DFS (깊이 우선 탐색)

2. 경로 탐색

# 문제 접근 방식

1. 두 사람 간의 촌수를 구하는 문제로, 주어진 관계를 그래프로 표현하여 두 노드 간의 최단 경로를 탐색해야 한다.

2. DFS(깊이 우선 탐색)를 사용하여 두 노드 간의 거리를 계산한다.

3. 입력으로 주어지는 사람들의 관계를 양방향 인접 리스트로 저장하고, DFS를 통해 목표 노드까지의 거리를 찾는다.

4. 탐색 중 방문하지 않은 노드에 대해 거리를 갱신하며 최종적으로 목적 노드까지의 거리를 출력한다.

# 코드 작성 

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

n=int(input().rstrip())
chon1,chon2=map(int, input().rstrip().split())
m=int(input().rstrip())
visited=[-1]*(n+1)
arr=[[] for _ in range(n+1)]

for _ in range(m):
    u,v=map(int, input().rstrip().split())
    arr[u].append(v)
    arr[v].append(u)

def DFS(node):
    if node==chon1: return
    for next_node in arr[node]:
        if visited[next_node]==-1:
            visited[next_node]=visited[node]+1
            DFS(next_node)

visited[chon2]=0
DFS(chon2)
print(visited[chon1])

# 회고

이 문제는 DFS와 그래프의 기본 개념을 복습할 수 있는 좋은 문제였다. 특히 재귀 호출을 사용하면서 파이썬의 재귀 한도 문제를 해결하는 방법을 익힐 수 있었다. 문제 해결 과정에서 visited 리스트를 촌수 계산과 방문 여부를 동시에 처리하도록 설계하여 코드의 간결함을 높일 수 있었다.

BFS와 DFS 중에서 이 문제에서는 DFS를 선택했지만, BFS로도 최단 경로를 구할 수 있어, 상황에 따라 더 적합한 탐색 방식을 선택할 필요성을 느꼈고, 재귀의 깊이를 충분히 고려하지 않을 경우 런타임 에러가 발생할 수 있어, 재귀 한도 설정에 주의해야 한다는 점을 배웠다.

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

# 학습 키워드

1. BFS (너비우선탐색) 

2. collections.deque : BFS 구현을 위한 deque 자료구조 사용법

3. sys.stdin.readline() : 입력을 짜르게 받기 위한 sys.stdin.readline() 사용법과 rstrip()의 필요성

# 문제 접근 방식

주어진 문제는 특정 정점에서 시작하는 너비우선탐색(bfs)을 통해 각 정점을 방문 순서에 따라 번호를 매기는 것이다. 이를 위해 다음과 같은 접근을 사용했다.

1. 그래프 입력과 정렬

모든 간선 정보를 입력받아 인접 리스트 형식의 그래프를 생성하고, 탐색에서의 순서를 보장하기 위해 인접 정접을 정렬한다.

2. BFS 탐색 

시작 정점에서 bfs를 수행하면서 각 정점의 방문 순서를 기록한다

3. 결과 출력

방문 순서를 기록한 리스트를 이용해 각 정점의 방문 순서를 출력한다.

# 코드 작성

from collections import deque
import sys
n, m, r = map(int, sys.stdin.readline().rstrip().split())

graph = [[] for _ in range(n+1)]
visited = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())

    graph[a].append(b)
    graph[b].append(a)

for i in range(n+1):
    graph[i].sort()

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = 1
    count = 2

    while queue :
        v = queue.popleft()

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=count
                count += 1

bfs(graph, r, visited)

for i in visited[1::]:
    print(i)

# 회고

이번 코드에서는 bfs의 기본적인 구현 방법을 익히고, 그래프 탐색에서 방문 순서를 기록하는 방법에 대해 공부하였다. 특히 deque를 이용해 bfs의 큐 구현이 효율적으로 이루어졌으며, sys.stdin.readiline()을 통해 입력 속도를 최적화한 것이 주요 학습 포인트이다.

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

# 학습 키워드

1. DFS(깊이 우선 탐색)

2. 그래프 탐색

3. 재귀함수

# 문제 접근 방식

DFS를 사용하여 시작 노드에서부터 연결된 노드를 방문 순서에 따라 기록하는 것이 핵심이다. 문제를 해결하기 위해 다음과 같은 접근을 했다.

1. 그래프 표현 

노드와 간선 정보를 받아 리스트로 그래프를 표현한다.

2. 정렬

시작 노드에서 노드로 갈 때 오름차순으로 탐색해야 하므로 인접 리스트의 각 노드를 정렬한다.

3. DFS 구현

재귀를 이용한 DFS를 통해 각 노드를 방문하여, 방문 순서대로 path에 추가하고, 이를 이용해 최종 방문 순서를 기록한다.

4. 결과 출력 

각 노드의 방문 순서를 출력 형식에 맞게 result 리스트에 담아 출력한다

# 코드 작성

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

N, M, R = map(int, input().split())
graph = [[] for _ in range(N + 1)]
path = []
result = [0] * (N + 1)
visited = [-1] * (N + 1)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, len(graph)):
    graph[i].sort()


def DFS(start):
    visited[start] = 1
    path.append(start)

    for adj_node in graph[start]:
        if visited[adj_node] == -1:
            DFS(adj_node)

    return


DFS(R)

for idx, node in zip(range(1, len(path) + 1), path):
    result[node] = idx

print(*result[1:], sep="\n")

# 회고

이번 문제를 통해 DFS에 대한 이해를 더 깊게 할 수 있었고, 특히 노드를 방문할 때 오름차순으로 정렬하여 탐색하는 방식이 방문 순서에 큰 영향을 미친다는 점을 알게 되었다.

기존에는 단순히 재귀를 통해 DFS를 구현했었지만, 이번 문제에서는 방문 순서를 기록하기 위해 path와 result 배열을 적절히 활용하는 방법을 배울 수 있어 좋았다.

또한  path와 result 배열을 활용해 노드의 방문 순서를 추적할 수 있었던 점이 인상 깊었다. 이 과정에서 DFS의 재귀 호출을 더 잘 이해하게 되었고, 그래프 탐색시 발생할 수 있는 예외 상황들을 고려하는 습관을 길러야 겠다고 생각했다.

코딩테스트 연습 - 입국심사 | 프로그래머스 스쿨

# 학습 키워드

이진탐색

최적화 문제 접근

시간 복잡도 최적화

# 문제 접근 방법

이 문제는 각기 다른 심사 시간이 주어졌을 떄, 주어진 인원을 가장 짧은 시간 안에 모두 심사하는 시간을 구하는 문제이다. 각 심사관은 고유한 심사 속도를 가지므로 특정 시간 내에 심사가 가능한 인원의 수를 계산하고, 최단 시간을 찾아내야 한다.

1. 이진 탐색을 통한 범위 축소

- 이 문제를 일반적인 반복문을 통해 해결하는 것은 비효율적이므로, 특정 시간 내에 필요 조건을 만족하는지를 기준으로 범위를 축소해가는 이진 탐색기법을 사용했다.

- 최솟값(left)은 가장 빠른 심사 시간을 의미하고, 최댓값(right)은 모든 인원이 가장 느린 심사관에게 심사를 받을 경우의 최장 시간을 의미한다.

2. 심사 가능한 인원 수 계산

- 특정 시간(mid) 내에 각 심사관이 처리할 수 있는 인원의 수를 계산하고, 이를 모든 심사관에 대해 합산하여 해당 시간 내에 처리 가능한 총 인원수(checked)를 구한다.

- 이때 checked가 목표 인원 n보다 크거나 같다면 더 짧은 시간에서도 가능할 수 있으므로 right값을 줄이고, 반대의 경우 left값을 늘리며 탐색 범위를 축소한다.

# 코드 작성

def solution(n, times):
    answer = 0
    left = min(times)
    right = max(times)*n
    while left <= right:
        mid = (left + right) // 2
        checked = 0
        for time in times:
            checked += mid // time
            if checked >= n:
                break
        if checked >= n:
            answer = mid
            right = mid - 1
        elif checked < n:
            left = mid +1
    return answer

# 회고

이진 탐색을 활용한 최적화 문제를 풀어본 경험이 있어 기본적인 접근 방식에는 큰 어려움이 없었다. 

하지만 이번 문제를 통해 탐색 범위 설정의 유연함이 필요하다는 것을 다시 느꼈다.

가장 짧은 심사 시간부터 시작하는 것이 반드시 최선이 아니고, 최댓값을 정할 때도 문제 상황에 따라 유연하게 설정할 수 있다는 점에서 새로운 인사이트를 얻었다.

목표 인원 이상이 될 경우 반복을 종료하는 조건을 넣어 반복문 효율성을 높이는 방법을 복습할 수 있었다. 이와같은 최적화 조건을 문제에 따라 다르게 적용할 수 있다는 점에서 이진 탐색 문제의 다양한 응용을 다시금 채감했다.

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

# 학습 키워드

1. 이분탐색 

이분탐색은 특정 조건을 만족하는 값을 찾는 데에 유용한 알고리즘이다. 이 문제에서는 mid 값을 활용하여 징검다리를 건널 수 있는 최대 칸을 계산한다.

2. 수열의 합

문제에서는 1부터 k까지의 합인 (k*(k+1))//2의 공식을 사용하여, k개의 징검다리를 건널 수 있는 최대 k를 찾는 데 활용한다

3. 시간 복잡도

이분 탐색을 활용하여 탐색 범위를 반으로 줄여 빠르게 답을 구할 수 있다. 일반적인 완전탐색보다 효율적이다.

# 문제 접근 방법

1. 문제 분석

1+2+3+ ... + k <= n 을 만족하는 최대의 k를 구하는 문제를 해결해야 한다.

첫 k개 자연수의 합이 n을 초과하지 않도록 최대한 큰 k를 찾아내는 것이 목표이다.

2. 이분 탐색 활용

이분 탐색을 사용하여 가능한 k의 범위를 좁혀간다.

- 초기 시작 값은 1, 종료값은 n으로 설정한다.

- mid값을 구하고, 1+2+...+mid = (mid*(mid+1))//2 공식에 따라 중간 지점까지의 합을 계산한다.

- 계산 결과가 n보다 작거나 같다면, mid가 가능한 값이라는 뜻이므로 start를 증가시키고 result를 갱신한다.

- 그렇지 않다면, mid를 mid-1로 줄여준다.

- 이 과정을 반복하여 최종적으로 result에 최대 k값을 구할 수 있다.

# 코드 작성 

t = int(input())

for _ in range(t):
    n = int(input())
    start = 1
    end = n
    result = 0

    while start <= end:
        mid = (start + end) // 2
        if ((mid+1)*mid)//2 <= n:
            start = mid + 1
            result = mid
        else:
            end = mid - 1
    print(result)

# 회고

이분 탐색은 단순 정렬된 배열에서의 탐색 뿐 아니라, 범위를 설정하고 특정 조건을 만족하는 값의 최솟값이나 최댓값을 찾는 데에도 매우 유용하다는 것을 확인했다. 이러한 문제를 통해 이분 탐색의 활용 능력을 키울 수 있다.

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

# 학습 키워드

1. 이분탐색

특정 조건을 만족하는 값을 찾기 위해 탐색 범위를 반으로 줄여가는 방법을 사용했다. 이 문제에서는 승률이 변하는 최소 게임 수를 찾기 위해 이분탐색을 활용했다.

2. 수학적 연산과 반올림 문제

승률 계산 시 (100*y)//x와 같은 정수형 연산을 통해 승률을 구하고, 정수로 표현해 소수점 문제를 방지했다.

3. 예외처리

특정 조건을 만족할 수 없는 경우(승률이 99% 이상인 경우)에 대한 예외 처리가 필요했다.

# 문제 접근 방법

1. 문제 분석

주어진 x(총 게임 수)와 y(이긴 게임 수)에서 승률 z를 구하고, 승률 z가 증가할 때 필요한 최소 게임 수를 구하는 문제이다.

- 승률 z가 99% 이상이면 게임 수를 늘려도 승률이 거의 변하지 않으므로, 이때는 -1을 출력한다.

2. 이분 탐색을 활용한 최소 게임 수 찾기

새로운 게임을 추가했을 때, 승률이 증가할 수 있는 최소의 게임 수를 찾기 위해 이분 탐색을 사용했다.

- left는 1, rigth는 x로 설정하고, 중간 값 mid를 이용하여 조건을 만족하는지 확인한다

- (y + mid) * 100 // (x + mid)를 통해 승률을 구하고, 기존 승률 z보다 크다면 mid값을 저장하고 rigth를 mid -1로 줄여 탐색 범위를 좁혀간다.

- 반대로 승률이 증가하지 않는 경우, left를 mid + 1로 증가시켜서 계속해서 탐색한다.

# 코드 작성

x,y = map(int,input().split())
z = (100*y)//x
if z >= 99:
    print(-1)
else:
    answer = 0
    left = 1
    right = x

    while left <= right:
        mid = (left+right)//2
        if (y + mid) * 100 // (x + mid) <= z:
            left = mid + 1
        else:
            answer = mid
            right = mid - 1
    print(answer)

# 회고

문제에서 승률 z가 99% 이상일 경우, 어떤 경우에도 승률을 올릴 수 없는 상태가 된다. 이와 같은 예외를 초기에 처리해줘야 불필요한 연산을 피할 수 있다. 문제풀이에서 초기 조건을 꼼꼼하게 확인하고 예외를 처리하는 것이 효율적임을 다시 느꼈다.