코린의 도이의 코딩 공부

1. 얼음 문제 N X M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어 있는 것으로 간주한다. 이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. n, m = map(int, input().split()) graph = [list(map(int, input())) for _ in range(n)] def dfs(x, y): # 범위에 벗어나느 경우 False if x = n or y = m: return False if graph[x][y] == 0: graph[x][y] = 1 dfs(x+1, y..

우선순위 큐(Priority Queue) 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야하는 경우에 우선순위 큐를 이용할 수 있다. Python, C++, Java를 포함한 대부분의 프로그래밍 언어에서 표준 라이브러리 형태로 지원한다. 자료구조 추출되는 데이터 스택(Stack) 가장 나중에 삽입된 데이터 큐(Queue) 가장 먼저 삽입된 데이터 우선순위 큐(Priority Queue) 가장 우선순위가 높은 데이터 힙(Heap) 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나이다. 최소 힙(Min Heap)과 최대 힙(Max Heap)이 있다. 다익스트라 ..

최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요 특정한 노트에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다. 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다. 매 상황에서 가장 비용이 적은 노드를 선택에 임의의 과정을 반복한다. 다익스트라 알고리즘의 ..

Breadth-First Search(너비 우선 탐색) 코드로 짜기 from collections import deque def bfs(graph, start, visited): queue = deque([start]) #queue자료 구조를 사용함 visited[start] = True while queue: v=queue.popleft() print(v,end=' ') for i in graph[v]: if not visited[i]: queue.append(i) visited[i]=True graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]] visited = [False]*9 bfs(graph, 1,visited)

depth-first search(깊이 우선 탐색) 코드 작성하기 def dfs(graph,v,visited): visited[v]=True print(v,end=' ') for i in visited[v]: if not visited[i]: dfs(graph, i, visited) graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]] visited=[False]*9 dfs(graph,1,visited)

BFS 너비 우선 탐색, 가까운 노드부터 우선적으로 탐색하는 알고리즘 큐(queue) 자료 구조를 이용함 은행 대기줄과 비슷 먼저 들어온 데이터가 먼저 나옴 deque를 사용함 popleft: 처음 입력한 원소 삭제 그래프로 보기 1→2→3→8→2을 popleft시키고 2와 인접한 노드 보기→7→3을 leftpop시키고 3과 인접한 노드 보기→4→5→6 코드로 보기 from collections import deque def bfs(graph, start, visited): queue = deque([start]) visited[start] = True while queue: v=queue.popleft() print(v,end=' ') for i in graph[v]: if not visited[i]:..

DFS 깊이 우선 탐색 stack(쌓는 것) 자료구조(재귀함수)를 이용함 stack은 파이썬에서 list를 이용하면 됨 append는 뒤에 붙이기 pop은 가장 최신으로 붙인 값을 빼기 list[::-1]는 최상단(마지막에 append한 순으로) 출력 보통 번호가 낮은 인접 노드부터 방문함 그래프로 보기 그래프 DFS 풀이: 1→2→7→6→6에서 방문하지 않은 인접노드가 없음→다시 7로→8→3→4→5 코드로 해보기! def dfs(graph,v,visited): visited[v]=True print(v,end=' ') for i in graph[v]: if not visited[i]: dfs(graph,i,visited) graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4]..

문제 재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다. 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... , 10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ... 총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라. 입력 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다...

문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 풀이 입력값 N이 5배수일 때 N을 5로 나눈 몫 출력 입력값 N이 5배수가 아닐 때 3을 빼주고 count에 1을 더해줌(..