구빙그르르르

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 한줄 이해 -가중치가 없는 방향 그래프가 있을 때 각 노드 입장에서 다른 노드를 거쳐서라도 갈 수 있는지 판단하기 생각난 풀이 1번째 방법: 각 노드들이 중간 다리 역할을 해주면서 탐색을 하는 방법이 생각났다. 예제를 그림으로 그리면 위와 같다. 이때 0번 노드 입장에서 1번 노드가 중간다리를 해주면 2번 노드로 갈 수 있다. 따라서 graph[i][k] + graph[k][j]가 2라면 graph[i][j]는 1로 ..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 한줄 이해 -배열에 정수를 넣은 다음 꺼낼때 절대값이 작은 수가 먼저 출력되고 절대값이 같은 경우에는 그 중 작은 값을 꺼내는 절대값 힙 구현하기 생각난 풀이 1번째 방법: 기본적으로 우선순위 큐를 사용 하려했고 기본적으로 파이썬에서 제공하는 heapq는 최소힙으로 제일 작은 값부터 출력이 된다. 이때 나는 힙에 넣어줄때 +라면(x의 절대값, 2), -라면(x의 절대값..

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 문제 한줄 이해 -카잉 제국에서는 해를 계산할때 이번 해 다음 해 이와 같이 1씩 증가시킨다. (단, 이번 해에서 1씩 증가시킬때 왼쪽의 값이 M보다 작으면 +1을 그렇지 않으면 1로 리셋해준다.오른쪽도 동일한 규칙을 가지고 N이 기준) 생각난 풀이 1번째 방법: while 반복문을 통해 단순히 1씩 증가시키고 조건에 걸리면 1로 리셋해주는 방법으로 했다. import sys t = int(sys..

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 문제 한줄 이해 -N이 주어질때 I가 N+1개 O가 N개가 교대로 나오는 P문자열이 있다.(P1 = IOI) 이때 S문자열에 P가 몇개 있는지 파악하기 생각난 풀이 1번째 방법: 배열 슬라이싱을 통해 갯수를 세보려했다. import sys n = int(sys.stdin.readline()) p = [] for i in rang..

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..