ㅋㅋ맨

DFS 공부 중 , 이것이 코딩테스트다(나동빈 저) 책에 나오는 문제와 백준의 유사한 문제를 풀면서 이해가 잘 되지 않은 부분을 정리하였다. 음료수 얼려먹기 문제 N * M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 떄 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 * 5 얼음틀 예시에서는 아이스크림이 총 3개 생성된다. 입력 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1

참고 링크 : https://chanhuiseok.github.io/posts/algo-23/ 백트래킹이란? 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 최적화 문제와 결정 문제를 푸는 방법이 된다. DFS (깊이 우선 탐색) : 가능한 모든 경로(후보) 탐색. 경우의 수를 줄이지 못함 ( 최적화 문제에 부적합 ) 백트래킹 : 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 탐색 x 예시로 최대 / 최솟값을 찾는 문제에서 MAX_VALUE , MIN_VALUE 등을 두고 탐색 중 MIN_VALUE 보다 크면 최솟값이 될 수 없으므로 탐색을 중단하고 뒤로 돌아가는 식으로 구현할 수 있겠다. 문제풀이에서는 DFS등으로 모든 경우의 수를 탐색하는 과..

문제링크 : https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net import sys input = sys.stdin.readline N = int(input()) # 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N # 숫자 카드에 적혀있는 정수 arr = list(map(int, input().split())) M = int(input()) # 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수..