백엔드 개발 공부 일지

1) 깊이우선탐색 (DFS) Depth First Search의 약자로 깊이 우선 탐색을 의미하며, 하나의 경우의 수에 대하여 모든 경우의 수를 조사하고 다음 경우의 수를 조사하면서 해를 찾는 과정 ※ 깊이우선탐색과 스택 위 예시에서 DCBA 의 Stack로 구현했을때 AB를 확인하고 C를 확인하는 것이 아닌 EJ를 다시 스택하여 경우의수를 찾는 구조로 해결한다. 깊이우선탐색의 가장 대표적인 예시는 미로찾기이다. while len(stack)>0: # 스택에 데이터가 있따면 now = stack.pop() #stack의 가장 마지막 데이터 추출 if now == dest: # 정답 여부 검사 return True x = now[1] y = now[0] if x-1 > -1 : # 왼쪽으로 이동할수 있다면..

● 숫자카드 2 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나..

● 탐색이란? 많은 데이터 속에서 원하는 데이터를 찾는 것으로 웹에서 특정 문자를 가진 웹문서를 찾거나 신용카드나 버스카드 역시 검색 알고리즘을 사용한다. 탐색의 종류는 다음과 같이 많은 것들이 있다. 완전탐색 이분탐색 깊이우선탐색 너비우선탐색 문자열탐색 KMP BM 이 포스트에서는 가장 기본이 되는 완전 탐색, 이분 탐색, 깊이우선탐색, 너비우선탐색 만 다룰 예정이다. ● 완전탐색 브루트 포스(Brute Force)라고도 불리며 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색하는 효율성 관점에서 최악의 방법으로 소개된다. (물론 그만큼 풀리지 않는 방법이 없다는 장점이 있다.) 대표적인 완전탐색의 구현 방법은 반복문과 재귀함수(완전 탐색 외의 동적 계획법, 백트래킹, 탐욕법등 다양한 ..