[IT/코딩테스트] 99클럽 코테 스터디13일차 TIL + BOJ2529

 

오늘의 문제

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

 

 

오늘은 내가 풀었다기 보다는 다른 분들의 풀이를 보면서 공부했다는 쪽이 더 가깝다.

그래서 우선 아래에 코드를 적어두고 다음에 한 번 더 풀어야할 것 같다!

 

---

오늘 공부한 내용

백트래킹과 DFS 

 

사실 백준 사이트에서는 백트래킹으로 분류가 되어있었는데, 

다른 분들의 풀이 글들을 보니 많은 분들이 dfs 로 구현한 코드를 올려두셨다.

 

그래서 백트래킹과 dfs 에 대해서 알아보게 되었다.

 

https://kwanik.tistory.com/34

백트래킹(Backtracking)과 DFS(Depth-First Search)

 

** dfs

: 모든 경로를 끝까지 확인?

 

** 백트래킹

: 과정을 반복하면서 불필요한 경로 탐색은 진행하지 않는 것.

: 기억해두는 것.

 

 

해결 코드

n = int(input())
brackets = list(input().split())
visited = [0] * 10
result = []


def check_up(i, j, k):
    if k == '<':
        return i < j
    else:
        return i > j


def dfs(iter, temp):
    if iter == n + 1:
        result.append(temp)
        return

    for i in range(10):
        if not visited[i]:
            if iter == 0 or check_up(temp[-1], str(i), brackets[iter - 1]):
                visited[i] = 1
                dfs(iter + 1, temp + str(i))
                visited[i] = 0


dfs(0, "")

print(result[-1])
print(result[0])

 

 

** check_up 함수

: 부등호 식이 올바른지 확인하고 그 결과를 리턴해주는 함수

 

** dfs 함수

: check_up 함수의 결과를 확인하면서 재귀적으로 숫자 탐색

 

** result

: [-1] -> 가장 큰 값

: [0] -> 가장 작은 값

 

 

 

아무래도 나에게 역시 지금 가장 필요한건 dfs, bfs 를 확실하게 이해하는 것 같다.

조금이라도 dfs, bfs 이 내용이 나오면 코드 작성이 어렵다🥹

 

우선 정처기 끝내고 코테 공부 빡세게 해보자....

부족한 부분이 너무 많다 지금....