#문제 링크 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net #난이도 : Silver 1 #분류: DFS #코드(Python) import sys sys.setrecursionlimit(10000) n = int(input()) map_ = [] area_cnt = 0 house_cnts = [] def is_valid(x,y): if x >= 0 and y >= 0 and x < n and y < m: return True return Fa..

[프로그래머스] (Python) - 프린터 코딩테스트 연습 - 위장 programmers.co.kr * 풀이 문제에 쓰여있는 그대로 구현했다. 다만 우선순위에 따라서 자리를 이동해버리면 처음 인쇄목록의 자리값을 모르게 된다. 그래서 priorities = [2, 1, 3, 2] 를 인덱스 값을 추가한 2중 리스트로 바꾸어주었다. priorities = [ [2, 0] ,[1, 1] , [3,2] , [2. 3] ] 시간 초과가 우려되었는데, 다행히 그냥 통과되었다. * Code - Python def search_list(priorities, now) : for i in priorities : if i[0] > now[0] : return False return True def solution(prior..

문제 링크 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net from collections import deque N, M, V = list(map(int, input().split())) matrix = [[0 for i in range(N+1)] for i in range(N+1)] dfs_answer = [] bfs_answer = [] visited = [False for i in range(N +..

탐색 알고리즘 (DFS) DFS의 정의 Depth-First Search : 깊이 우선 알고리즘, 그래프의 깊은 노드를 우선적으로 탐색하는 알고리즘이다. 때문에 DFS를 이해하려면 그래프와 그래프 탐색에 관한 부분을 알아야한다. + 스택(stack) 흔히 미로 탐색으로 비유한다. 막다른 길에 도달할때 까지 한쪽방향을 탐색하다가, 끝을 보면 다시 갈림길로 돌아와서 다른 길을 탐색하는 방법이다. 완전탐색의 일종이다. DFS의 장점 현재 탐색중인 노드들만 기억하기 때문에 메모리 사용이 적고, 당연한 이야기지만 찾으려는 노드가 깊을 경우에 BFS보다 빠르게 찾을 수 있다. DFS 단점 해가 없는 경로를 탐색하는 경우에도 경로가 끝날때 까지 탐색한다. (이를 방지하기 위해 조건을 지정하고 원래 위치로 되돌아오는 ..

스택(Stack) 선입후출의 특징을 가진 알고리즘이다. (흔히 박스쌓기에 비유) 컴퓨터 내부에서 재귀함수의 구현은 스택으로 이루어진다. Python에서 스택을 사용할때는 특별한 구현 필요없이, .append() 함수와 .pop() 만을 사용하면 그대로 스택을 구현할 수 있다. Python - stack stack = [] stack.append(3) stack.append(4) stack.pop() 큐(Queue) 선입선출의 특징을 가졌다. (흔히 줄서기에 비유) 삽입되는 곳을 front 제거되는곳을 back 이라고 한다. BFS(너비 우선 탐색) 에 유용하게 사용된다. deque을 append 함수만 추가하고, popleft()로만 삭제하면 큐이다. 덱(Deque) 스택과 큐의 장점을 모두 갖고있다. ..

그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘은 "매 선택에서 당장 좋은것만을 선택해 나가는 방법"을 뜻한다. 특정 기준에 따라서 좋은 것을 선택해야하는 알고리즘이기 때문에 문제에서 어느정도 제시해준다. 그리고 좋다, 나쁘다의 기준을 세워야하기 때문에 정렬 알고리즘과 섞여서 나오는 문제들이 많다. 간단한 예제 (거스름 돈) 그리디 알고리즘을 대표하는 문제로 '거스름 돈' 문제가 있다. 자판기에 거스름돈을 배출해야 하는데 , 자판기에는 500, 100, 50, 10원짜리가 무수히 존재한다. 이때 거슬러줄 최소 동전의 개수를 구하라. (단, 거스름 돈은 항상 10의 배수이다.) 이러한 문제가 있다면, 무조건 큰 단위의 동전(500원)으로 최대한 거슬러주고, 그 다음 가능한 큰 단위의 동전(..