집주변이 최고야

문제 철수는 N x M 크기의 직사각형 형태의 미로에 갇혀있다. 미로에는 여러마리의 괴물이 있어 이를 피해 탈출해야 한다. 철수의 위치는(1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 철수가 탈출하기 위해 움직여야하는 최소 칸의 개수를 구하시오. 칸을 셀때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 조건 첫째 줄에 두 정수 N,M (4≤N,M≤200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수 (0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 ..

문제 N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다. 입력 조건 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 ≤ N,M ≤ 1,000) 두 번째 줄부터 N+1 번째 줄까지 얼음 틀의 형태가 주어진다. 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다. 출력 조건 한번에 만들 수 있는 아이스크림의 개수를 출력한다. 입력 예시1 4 5 00110..

DFS Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 설명하기 전에 먼저 그래프의 기본 구조를 알아야 한다. 그래프는 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식 인접 행렬 방식 2차원 배열에 각 노드가 연결된 형태..

재귀 함수란 자기 자신을 다시 호출하는 함수 def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() #출력 재귀 함수를 호출합니다 재귀 함수를 호출합니다 재귀 함수를 호출합니다 재귀 함수를 호출합니다 ...RecursionError : maximum recursion depth exceeded while pickling an object위와 같이 실행하면 문자열을 무한히 출력하다가 재귀의 최대 깊이를 초과했다는 메시지가 뜰 것이다. 재귀 함수는 프랙털(Fractal) 구조와 흡사하다. 위 그림은 시에르핀스키(Sierpinski)의 삼각형이다. 삼각형 안에 또 다른 삼각형이 무한히 존재..

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있는데 이 두 알고리즘의 원리를 제대로 이해해야 코딩 테스트의 탐색 문제 유형을 풀 수 있다. 그런데 DFS, BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 하므로 사전 학습으로 스택과 큐를 간단히 정리해보자. 자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성 삽입(Push) : 데이터를 삽입 삭제(Pop) : 데이터를 삭제 스택 스택은 박스 쌓기에 비유할 수 있다. 흔히 박스는 아래에서부터 ..