# DFS
[프로그래머스/ JavaScript] 피로도
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로
[파이썬] 카카오코테 2022 양궁 대회
세 가지 중요한 포인트를 기록한다. 먼저, do_score에 결함이 있었다. aim -1 for 문에서 돌려주었는데, 문제는 continue 조건에서는 aim -=1을 수행할 수 없었기 때문에 문제가 발생했다. (디버깅하는데 엄청 오래걸렸다. for문의 구조를 rang
[자료구조] 그래프(Graph) - 깊이우선탐색(DFS) & 너비우선탐색(BFS)
하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것특정한 정점에서 다른 정점으로 갈 수 있는지 없는지를 탐색을 통하여 알 수 있다. \- e.g. 특정 도시에서 다른 도시로 갈 수 있는지 없는지깊이부터 우선적으로 탐색하는 기법시작 정점에서 한 방향으
백준 14716번: 현수막
"백준 14716번: 현수막" 문제를 풀어보았다!ANT가 처음 알고리즘 대회를 개최하게 되면서 현수막을 내걸었다.저번 학기 영상처리 수업을 듣고 배웠던 지식을 최대한 응용 해보고 싶은 혁진이는 이 현수막에서 글자가 몇 개인지 알아보는 프로그램을 만들려 한다.혁진이는 우
[백준] 11725번 : 트리의 부모
트리의 부모 찾기이번 문제는 DFS를 약간 변형하는 문제였다.DFS를 정확히 알고있다면 간단한 문제였다.DFS는 깊이 우선 탐색으로 루트 노드에서부터 순차적으로 탐색에 들어가는데, 재귀 함수로 구현된 DFS에서 자식 노드로 탐색에 들어가기 전에 부모 노드를 저장해주면
[Programmers] 퍼즐 조각 채우기(Lv.3)(C++)
풀이 소요시간 : 약 2시간꽤 어려운 구현 + 탐색 문제였다. DFS를 한번 돌면서 각 퍼즐조각의 형태를 저장하고, Game_Board의 빈칸 구조를 탐색하며 빈칸 구조와 퍼즐 형태를 비교해야했다. 이 과정에서 퍼즐 조각을 돌리지 않기 위해 Game_Board를 90도
백준 16173번: 점프왕 쩰리 (Small)
"백준 16173번: 점프왕 쩰리 (Small)" 문제를 풀어보았다!‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.‘쩰리’는 가로와 세로의 칸 수가
백준 26169번: 세 번 이내에 사과를 먹자
5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자는 사과가 1개 있는 격자, 장애물이 있는 격자, 빈칸으로 되어 있는 격자로 구분된다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c는 열 번호를 나타낸
BFS & DFS
너비 우선 탐색 (BFS) 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘 BFS의 특징 Queue를 이용하여 구현할 수 있다. 시작 지점에서 가까운 정점부터 탐색한다. V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V+E)
[파이썬] 카카오2023 미로 탈출 명령어
응용된 DFS 문제이다. 내 경우에 중요했던 첫번째 포인트는 문제에서 DFS를 수행하는 경우가 두 가지 경우로 나누어진다는 점.그리고 두 번째 포인트는 불가능한 case를 정확히 찾는 것이다.기본적으로 이문제는 for 문 수행순서를 d l r u 네 가지를 정확하게 표
[Programmers] 소수 찾기(Lv.2)(C++)
풀이 소요시간 : 15분해당 문제를 풀면서 완전 탐색보다 조금 더 빠른 소수 판독 방법을 공부했다. 2부터 sqrt(N)까지 나누어 떨어지는 수가 하나라도 있다면 소수가 아니라고 할 수 있다. 다만 N이 0이나 1인 경우 예외처리를 반드시 해주어야한다.
[알고리즘] 그래프 탐색 알고리즘(DFS/BFS)
코딩테스트를 대비한 알고리즘 포스팅 해시(Hash)편은 여기 참고 !코딩테스트를 대비한 알고리즘 포스팅 스택/큐(Stack/Queue)편은 여기 참고 !코딩테스트를 대비한 알고리즘 포스팅 힙(Heap)편은 여기 참고 !코딩테스트를 대비한 알고리즘 포스팅 정렬(Sort)
백준 1012번 : 유기농 배추
class를 깨면 백준 티어가 빨리 오른다는 말을 듣고 class에 있는 문제들을 하나씩 풀어보던 중, 완탐 문제를 마주하게 되었다.완전 탐색의 아주 기본적인 문제임에도 불구하고 부끄럽게도 3차 시도만에 맞추었다. 1차 때 ni, nj의 범위를 고려하기 전에 visit
백준 3055 '탈출'
각 칸이 물에 잠기기까지 남은 시간을 구한다.초기에는 물이 있는 칸에는 0, 돌과 비버굴은 -1, -2로 따로 표시해서 예외처리를 하고, 나머지 칸은 $\\infty$로 둔다.물 칸에서 BFS를 이용해 물에 잠기기까지 남은 시간을 갱신한다.고슴도치의 위치에서 BFS로