시간 날 때, 끄적끄적

그래프와 탐색 알고리즘 그래프는 대상들의 관계를 나타낼 때 적합한 자료구조로 대상 나타내는 node 또는 vertex들과 그들의 연결 관계를 나타내는 Edge로 표현할 수 있다. 그래프는 edge가 탐색할 수 있는 방향의 존재 여부와 가중치의 여부에 따라 크게 네 가지 종류로 구분할 수 있다. 무향 그래프 : edge의 방향이 없는 그래프 유향 그래프 : edge에 방향이 있는 그래프 가중치 무향 그래프 : edge에 방향은 없으나 가중치가 있는 그래프 가중치 유향 그래프 : edge에 방향과 가중치가 있는 그래프 행렬의 행은 출발하는 node의 숫자, 열을 도착하는 node의 숫자로 그래프를 표현할 수 있다. 아래의 예는 유향 그래프를 행렬로 표현한 것을 나타낸 예시이다. 1번 node는 2와 3으로 ..

문제 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 설명 짝수 N명의 사람들을 두개의 팀으로 나누어 각 팀의 능력치를 계산해 비교해 차이가 최소인 팀 구성을 구하는 문제 팀이 구성되면 구성원 끼리 순서가 없기 때문에 조합을 찾는 문제로 생각해 풀 수 있음 고민한 부분 python의 내장 라이브러리인 itertools의 combinations함수를 사용할 수 있을지 확인해보고 싶었다 백트래킹 문제가 조금 까다롭게 나오는 경우 중간에 탐색할 필요 없는 조건을 찾아 가지치기를 해주어야 하는데 이 문제에서는 가지치기 할 필요 ..

문제 링크 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 설명 빈 공간, 벽, 바이러스로 구성된 2차원 array를 입력받아 빈 공간 세 곳에 벽을 세운 후 바이러스가 퍼질 수 없는 영역의 수를 세는 문제 구현해야 하는 내용은 빈 공간에 $^{1)}$세 개의 벽을 세우는 것, $^{2)}$바이러스가 퍼질 수 있는 영역을 BFS로 탐색하는 것, $^{3)}$감염되지 않은 영역을 세는 것 고민한 부분 아직 순열이나 조합을 응용하는 문제에 익숙하지 않아 긴 시간동안 고민을 했음 재귀 방식으로 3개의 블럭을 쌓은 후 BFS..

문제 링크 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 설명 순서가 있는 N개의 숫자를 받고 그 숫자 사이에 N-1개의 연산자를 삽입하는 문제 중복을 허용하고, 4종류의 연산자로 이루어진 N-1 길이의 순열을 모두 탐색하는 방법으로 접근 고민 한 부분 DFS 방식으로 탐색을 하며 이미 탐색한 순열은 다시 탐색하지 않도록 가지치기할 방법 (line 39) 더보기 N-1 x 4 크기의 visited 배열을 활용해 depth 번째에 삽입 될 연산자가 이..