# DFS

26개의 포스트

[BOJ 16638] 괄호 추가하기 2 (Java)

BOJ 16638 괄호 추가하기 2괄호 추가하기 1은 쉽게 풀었던 것 같은데 비슷한 아이디어가 다시 떠오르지 않아서 힘들었다. 이 문제의 핵심 아이디어는 다음과 같다.괄호는 연산자 기준으로 씌워진다.괄호를 어떻게 씌워줄까 굉장히 고민되는데 괄호는 연산자를 중심으로 씌워

2일 전
·
0개의 댓글

[BOJ 16988] Baaaaaaaaaduk2 (Easy) (Java)

BOJ 16988 Baaaaaaaaaduk2 (Easy)예전에 봤을 때는 왜 그렇게 어려웠던건지... 다시 보니 간단한 문제다.1\. 돌 두개를 놓는 모든 경우를 수행한다.2\. 맵 전체 검은 돌에 대한 라벨링을 한다. 동시에 죽은 그룹의 돌을 모두 세어 ans에 최댓

3일 전
·
0개의 댓글

[BOJ 16986] 인싸들의 가위바위보 (Java)

BOJ 16986 인싸들의 가위바위보첨부그림 때문에 문제를 풀 의욕이 없어지는 문제, 하지만 알고보면 평소에 풀던 완전탐색과 다를 바가 없다.지우가 낼 수 있는 N개의 손동작을 순열로 구한다.지우, 경희, 민호의 게임을 시뮬레이션 한다.승부가 발생할 경우 경기 진행 순

3일 전
·
0개의 댓글

[BOJ 4574] 스도미노쿠 (Java)

BOJ 4574 스도미노쿠알고리즘이 어려운 문제는 아니였으나 구현이 까다로워 상당히 힘들었다. 스도쿠 판을 모두 채운 후에 유효성 체크를 하는 것이 아니라 백트래킹을 실시하는 중에 방문체크를 통해서 항상 옳은 경우만 나오도록 하는 것이 중요했다.row, col, squ

7일 전
·
0개의 댓글

[BOJ 1937] 욕심쟁이 판다 (Java)

BOJ 1937 욕심쟁이 판다다이나믹프로그래밍 유형도 재미가 하다보니 있는 것 같다. 주어진 데이터 기반으로 각 지역에서 이동할 수 있는 최댓값으로 DP 테이블을 갱신해나가는 문제, 이 블로그에 굉장히 잘 설명되어있다.한 번 갱신한 지역은 다시 갱신하지 않아도 되기 때

2020년 2월 18일
·
0개의 댓글

[BOJ 16197] 두 동전 (Java)

BOJ 16197 두 동전사방탐색을 통해서 최소이동으로 동전 하나만을 떨어뜨리는 문제다. 사방탐색 + 최소이동을 보자마자 BFS를 떠올려야 하지만 '10번 안으로 들어와야한다.'라는 조건을 보고 바로 DFS 탈출조건을 떠올렸다. 그래서 먼저 DFS로 풀이하게 되었다.

2020년 2월 13일
·
0개의 댓글

[BOJ 9944] NxM 보드 완주하기 (Java)

BOJ 9944 NxM 보드 완주하기재밌는(쉽게 풀리는...) 백트래킹 문제였다.

2020년 2월 11일
·
0개의 댓글

[BOJ 4991] 로봇 청소기 (Java)

BOJ 4991 로봇 청소기 문제풀이 '로봇 청소기로 가장 가까운 더러운 곳을 BFS로 찾고 그 지점에서 다시 가장 가까운 지점을 BFS로 찾는다.' 라는 아이디어로 즐겁게 구현했지만... 바로 틀렸습니다를 보게 되었다... 위 아이디어의 문제점을 살펴보자면 그리디한 방법이다. 현재 지점에서 가장 가까운 지점을 방문해나가지만 전체적으로 보았을 때 최소거리...

2020년 2월 5일
·
0개의 댓글

[BOJ 1707] 이분 그래프 (Java)

BOJ 1707 이분 그래프 문제풀이 처음에 이분 그래프의 의미를 잘못 이해해서 시간이 조금 걸린 문제다. 이분 그래프는 그래프의 정점을 두 그룹으로 나누었을 때 같은 그룹에 속한 정점끼리는 인접하지 않는 것이다. 따라서 그래프를 탐색하는 과정에서 현재 정점과 다음 정점의 그룹이 다르면 된다. 그래프의 탐색은 DFS, BFS 모두 가능하며 나는 DFS로 ...

2020년 1월 31일
·
0개의 댓글

[백준 2468] 안전영역

2020년 1월 17일
·
0개의 댓글

[백준 11403] 경로찾기

2020년 1월 17일
·
0개의 댓글

2019 winter PS --version Basic (day22)

백준 1167 -- 1) 백준 1167 : 트리의 지름 (https://www.acmicpc.net/problem/1167) 후;;; 컴과사 시간때 풀었었는데... dfs를 모든 leaf노드에서 돌리려고 했다가 TL.. dfs를 아무 leaf에서 돌리고 또 2번 돌리면 그 길이가 최대가 된다는 것을 배웠거늘.. dfs를 처음 돌렸을 때 최대거리가 되는...

2020년 1월 14일
·
0개의 댓글

백준 11724 연결 요소의 개수 (Java)

풀이 백준 DFS/BFS 문제와 거의 비슷한 문제로 DFS 또는 BFS를 사용하여 간선으로 연결되어있는 정점들의 집합의 갯수를 찾는 문제. 정점의 개수 만큼 for을 돌며 visited에 기록이 되어있지 않으면 DFS/BFS함수에 들어가서 해당 연결 되어있는 간선들을 찾고 연결 요소들을 모두 찾고 나올 시 count해주는 방식으로 구현. 소스코드 ...

2020년 1월 6일
·
0개의 댓글

백준 1260 DFS/BFS (Java)

풀이 인접행렬 또는 인접리스트를 활용해 풀 수 있는 문제인데 인접행렬 사용시 시간 복잡도 : O(V^2) 인접리스트 사용시 시간 복잡도 : O(V+E) 이므로 인접리스트를 사용하여 푸는 것이 좋다. 양방향 간선이기 때문에 ArrayList>를 사용해서 하나의 간선을 입력받을 시 반대 간선도 같이 저장 시켜주는 방식으로 구현. ex)...

2020년 1월 6일
·
0개의 댓글

2019 winter PS --version Basic (day11)

백준 2606, 7785 -- 1) 백준 2606 : 바이러스 (https://www.acmicpc.net/problem/2606) 전형적인 DFS문제 (BFS가 더 빠르다고는 하던거 같은데 아무튼 이게 손에 익어서) 1과 연결된 노드가 몇개인지 거르면 끗. https://github.com/JangJuMan/2019-winter-PS/11_2606.c...

2020년 1월 3일
·
0개의 댓글
post-thumbnail

재귀함수는 왜 어려울까?

혹시, 다음에 해당하시나요? > 1. 공부하다가 재귀가 나오면 퍽 하고 숨이 막히고, 어지럽다. 재귀를 사용하면 불안해서 반복문을 사용한다. 내가 짠 재귀는 무한히 호출될것 같다. 어떤 값을 반환해야할지 모르겠다. gvsc (1).png 역시 for문이 짱이지 지금부터, 다음 3가지에 초점을 맞추고, 재귀를 쉽게 알아볼께요 함수의 의미 정의 어떤 값을...

2020년 1월 1일
·
0개의 댓글

TIL - N-Queens Algorithm, Back tracking

Today What I Learned Javascript를 배우고 있습니다. 매일 배운 것을 이해한만큼 정리해봅니다. * Algorithm : N-Rooks & N-Queens 1. N-Rooks & N-Queens: n * n의 체스판에 룩(Rook)과 퀸(Queen)을 충돌 없이n개 배치하는 알고리즘이다. 2. 체스 룰은 이번에 정확히 배웠는데...

2019년 12월 1일
·
0개의 댓글

[Algorithm] N-Queens

N-Queens N-Queens Problem은 NxN의 체스판에 N개의 퀸을 서로 충돌하지 않게 놓는 방법 혹은 그 수를 구하는 문제다. 예를 들어 4-Queens의 정답은 두 가지가 가능하다. 4queens1.png4queens2.png N-Queens의 정답을 찾기 위해서 필요한 키워드는 DFS(깊이우선탐색, Depth First Search), 재귀...

2019년 11월 29일
·
0개의 댓글