Algorithm/Algorithm Problem

백준 5430 AC(Queue)

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제는 간단하다. 주어진 배열에서 R이면 reverse(), D면 pop()을 시키면 되는 문제였다. 주요 요점은 어떤 자료구조를 사용하냐는 건데 함수p와 n의 범위가 100,000이기 때문에 list로 접근하면 안된다는걸 바로 알아차렸다. 따라서 queue로 접근하면 pop에 대한 시간복잡도는 O(1)이기 때문에 queue()로 선택했다. 여기서 가장 시간을 많이 잡아먹는 연산은 당연히 reverse()이다. 그래서 R을 만날때마다 reverse()를..

백준 1107 리모콘(Brute-Force)

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 브루트포스 즉, 완전탐색 문제를 만나면 변수의 범위를 확인해서 전체의 경우를 고려해줄 필요가 있다. 문제를 이해하기에는 크게 어렵지 않았다. 1. 시작 채널이 100번이라고 했으니까 목표 채널 N까지 ++,--만 누르는 abs(100 - N) 경우 2. N을 모두 누를 수 있는 경우 3. N과 가장 가까운 숫자에서 ++,--를 누르는 경우 모든 경우를 확인해야 하기 때문에 2,3을..

백준 11403 경로찾기(DFS,BFS, Floyd-Warshall)

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 지금까지 만난 그래프 문제와는 조금 다른점은 방향그래프라는 것이다 탐색방법은 매우 다양하며 정점끼리 서로 이어진 것만 새로운 행렬에 체크해줘서 출력하면 되는 문제다 DFS #DFS #다차원배열 visited을 넘겨서 확인 #std행을 fix시켜놓고 처리를 해야하기 때문에 std 인자를 넣어줬다 def dfs(std, start): for i in range(n): if visited[std][i] == 0 and board[start][i..

프로그래머스 양궁대회(시뮬레이션, 그리디)

https://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr #시뮬레이션 from itertools import combinations_with_replacement # a가 b보다 더 좋은 배치일 경우 true def cmp(a, b): return a[::-1] > b[::-1] def solution(n, info): # 라이언이 가장 큰 점수 차이로 우승할 수 있는 결과를 저장 # ret[0..10] : 10-i점에서 ..

프로그래머스 쿼드압축 후 개수 새기(분할 정복)

https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 백준 1780 종이의 개수 와 동일한 분할 정복 문제 def solution(arr): import sys sys.setrecursionlimit(10 ** 6) data =..

백준 18243 Small World Network(플로이드-와샬, BFS)

https://www.acmicpc.net/problem/18243 18243번: Small World Network 첫 번째 줄에 지구에 있는 사람의 수 N과 친구 관계의 개수 K가 주어진다. 모든 사람은 1부터 N까지 번호가 매겨져 있다. (1 ≤ N ≤ 100, 0 ≤ K ≤ N×(N-1)/2) 두 번째 줄부터 K+1번째 줄까지 친구 www.acmicpc.net import sys n, k = list(map(int,input().split())) edges = [list(map(int,input().split())) for _ in range(k)] INF = sys.maxsize def make_graph(): graph = [[INF] * n for _ in range(n)] for frm, ..