구빙그르르르

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제 한줄 이해 -N명의 사람이 주어지고 친구 관계 M개가 주어 졌을때 각 사람이 다른사람을 몇번의 건너건너를 해서 아는지 총합을 구하기(본인과 김사또가 있을때 한번에 아는 사이면 1단계 친구, 내가 아는 친구의 친구(김사또)면 2단계) 생각난 풀이 1번째 방법: 1~N번 사람들을 각각 BFS를 통해 다른 사람들과 몇단계로 이루어져있는지 확인을 하..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제 한줄 이해 -2^N*2^N의 그래프에서 Z 모양을 그리면서 번호 매겨가기. 생각난 풀이 1번째 방법: 분할정복 아이디어를 가지고 접근했다. 재귀함수를 이용해 그래프를 N//2의 크기로 잘라가면서 번호를 매겨 보려했다. import sys N, r, c = map(int, sys.stdin.readline().split()) graph = [[0 for i in range(2**(N)..

https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 문제 한줄 이해 -그래프의 특정 위치에서 이동하면서 친구 만나기 생각난 풀이 1번째 방법: 전형적인 dfs, bfs 문제라 생각이 들어 dfs를 활용해 문제를 풀었다. import sys n, m = map(int,sys.stdin.readline().split()) graph = [] for i in range(n): graph.append(list(map(str, sys.stdin..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 문제 한줄 이해 -주어진 N개의 좌표들을 대소관계를 유지하면서 좌표 압축하기. 생각난 풀이 1번째 방법: 처음에는 단순히 값들의 대소관계를 유지하면서 각 좌표의 값들을 +1,-1 등을 하면서 좌표 사이의 갭을 줄여나가면 된다고 생각했다. 하지만 좌표값의 범위가 컸고 갭차이가 크면 시간복잡도가 커질것이라 생각했고 어떤 좌표를 기준으로 갭을 줄여나가..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 문제 한줄 이해 -노드들이 주어졌을때 이어진 노드들끼리를 한 조라 할때 조의 갯수를 출력하는 문제 생각난 풀이 1번째 방법: 방문 체크 리스트를 만들어서 1번 노드부터 방문을 하면서 연결 돼 있는 노드들은 체크를 해나간다. import sys from collections import deque n,m = map(int,sys.st..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 한줄 이해 -N의 나무가 일자로 서있을때 높이에 따라 싹뚝 잘랐을때 잘려나간 나무의 길이의 합이 적어도 M미터의 나무를 집에 가져가기 위한 높이의 최대값 구하기 생각난 풀이 1번째 방법: 우선 N과 M의 범위가 생각보다 크다고 생각이 들어 이분탐색을 통해 해결해야 겠다고 생각했다. import sys n, m = map(int, sys.stdin.re..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 한줄 이해 -주어진 종이가 모두 같은 색으로 칠해져 있지 않다면 가로 세로로 중간 부분을 잘라 n/2 *n/2 종이를 만들어가면서 모두 같은 색으로 이루어지게 만들기 생각난 풀이 1번째 방법: 같은 격자내에 같은 숫자들만 있어야 한다는 것에 초점을 두고 접근했다. import sys n = int(sys.stdin.readline()) graph = [] for i..