백준 write-up/완전 탐색 (6) 썸네일형 리스트형 [백준] Best Grass : 11123번 - Python https://www.acmicpc.net/problem/6186 6186번: Best Grass Bessie is planning her day of munching tender spring grass and is gazing out upon the pasture which Farmer John has so lovingly partitioned into a grid with R (1 [백준] 양 한마리... 양 두마리... : 11123번 - Python https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 문제를 풀면서 몰랐던 개념 - 파이썬의 재귀 최대 깊이 기본 설정에 대한 개념 ⬇️⬇️⬇️ 아래 링크 참고 ⬇️⬇️⬇️ https://ye5ni.tistory.com/178 문제의 접근 방법 - DFS 알고리즘 사용하기 - 방문한 노드와 방문하지 않은 노드 구분하기 - 입력 받은 그리드를 저장할 수 있는 공간을 만들기 내가 막혔던 부분 - DFS 알고리즘을 구상하는 방법 - 양.. [백준] N과 M(1) : 15649번 - Python https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제를 풀면서 몰랐던 개념 백트래킹에 대한 개념 -> https://ye5ni.tistory.com/110 참고! 문제의 접근 방법 1. 아이디어 - 백트래킹 재귀함수 안에서, for문을 돌면서 1부터 N중에서 숫자를 하나 선택 - 다음 1부터 N까지 선택할 때, 이미 선택한 값이 아닌 경우 선택(방문여부 체크) - 재귀함수에서 M개를 선택할 경우 출력 2. 시간복잡도 - N^N : 중복이 가능.. [백준] 바닥 장식 : 1388번 - Python https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 문제를 풀면서 몰랐던 개념 DFS 알고리즘에 대한 개념 -> https://ye5ni.tistory.com/108 참고! 문제의 접근 방법 👀 '-' 모양의 나무 판자와 '|' 모양의 나무 판자를 나누어서 계산하기 👀 '-' 모양은 좌우(가로) 노드의 값을 비교하고 '|' 모양은 상하(세로) 노드의 값을 비교하기 👀 특정 조건을 만족해야 하는 탐색 기법의 경우에는 DFS를 사용하는 것이 유리함! 내가 막.. [백준] 단지번호붙이기 : 2667번 - Python https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제를 풀면서 몰랐던 개념 DFS 알고리즘에 대한 개념 ->https://ye5ni.tistory.com/108 참고! 문제의 접근 방법 1. 아이디어 - 2중 for문, 값 1 && 방문 X => DFS - DFS를 통해 찾은 값을 저장 후 정렬해서 출력하기 2. 시간복잡도 - DFS : O(V+E) - V, E : N^2, 4N^2 - V+E = 5N^2 ~= N2 ~= 625 >> 가능함 3... [백준] 그림 : 1926번 - Python https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제를 풀면서 몰랐던 개념 BFS 알고리즘에 대한 개념 -> https://ye5ni.tistory.com/105 참고! 문제의 접근 방법 1. 아이디어 - 2중 for => 값 1 && 방문 X => BFS - BFS 돌면서 그림 개수 +1, 최댓값을 갱신 2. 시간복잡도 - BFS : O(V+E) = V + 4V = 5V = 5(m*n) - V : m * n = 500 * 500 (m, n이 최대 .. 이전 1 다음