dfs

[백준] 3584. 가장 가까운 공통 조상 - Python

[Gold IV] https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 처음 보는 LCA (Lowest Common Ancestor) 문제. DFS를 통해 Root 노드부터 각 노드의 깊이(depth)를 저장하고, 입력된 두 노드의 depth를 맞춘 후, 공통 조상이 나올 때까지 그대로 거슬러 올라가는 식으로 해결하였다. 이 풀이의 경우 O(N)의 Time Complexity로 해결한 경우이며..

[백준] 3109. 빵집 - C++

[Gold II] https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 우선, 찬찬히 살펴보면, 첫 번째 열의 모든 칸에서부터, 최대한 많이 마지막 열의 칸으로 연결해야 한다. 이 때, Greedy하게 첫째 열의 맨 위(첫 번째) 칸에서부터 시작해도 되며, 오른쪽 위 / 오른쪽 / 오른쪽 아래 3개의 선택지 중, 오른쪽 위를 선택하는 것이 이후 파이프 연결에서 가장 유리하므로, 또한 Greedy하게 오른쪽 위 - 오른쪽 - 오른쪽 아래 순으로, 가능한 선택지를..

[백준] 1520. 내리막 길 - C++

[Gold III] https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 1 Bottom-Up 방식의 DP. 오른쪽 아래부터 왼쪽 위까지 채워나가는 방식으로 구현했다. 오른쪽과 아래로만 갈 수 있는 줄 알았는데, 위와 왼쪽으로도 갈 수 있어서 WA. #include #include #include #define init cin.tie(0)->ios_base::sync_with_stdio(0); typedef long long ll; using nam..

[백준] 1987. 알파벳 - python

[Gold IV] https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 1 이건 그냥.. DFS, Backtracking 이용해서 Recursion으로 풀면 되겠다- 라고 간단하게 생각했다. 그런데 가볍게 짠 코드에서 TLE. import sys sys.setrecursionlimit(100000) R, C = map(int, input().split()) board = [list(input()) for _ in range(R)] res..

[백준] 1260. DFS와 BFS - 파이썬

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 기본적인 DFS, BFS 구현 문제. dictionary를 사용한다면, 없는 key에 접근하지 않도록 유의할 것. 예외처리를 하지 않고 제출했다가, 런타임 에러(keyError)가 남. line 30~32, 49~51과 같이 정점에 연결된 간선이 없을 때를 예외처리 해 주면 된다. 아마 정점이 딱 하나만 들어왔을 때 Error가 났을 듯. from col..

[프로그래머스] 64064. 불량 사용자

2019 카카오 개발자 겨울 인턴십 - 64064. 불량 사용자 Python 풀이 풀이 우선 user_id 배열의 크기는 1 이상 8 이하입니다. banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다. 의 조건이 존재하기 때문에, 효율성을 크게 따질 필요는 없어 보임. isSame() => banned ID에 user ID가 들어갈 수 있는 지 확인하는 함수. 하나 만들어 놓고, 빈 dictionary(able) 생성해서, banned_id 의 index 순으로 대입 가능한 user_id 의 배열을 집어넣어 놓음. user_id = ["frodo", "fradi", "crodo", "abc123", "frodoc"] banned_id = ["fr*d*", "*rodo", "***..