전체

백준 9019 DSLR(시간복잡도, BFS)

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제를 이해하기에는 어렵지 않았다. D,S,L,R에 따른 연산을 하고 연산결과가 B랑 같으면 어떤 연산을 했는지 출력한다 최소한의 연산을 해야하기 때문에 그리디, BFS적으로 접근을 했고 한 경우가 계속 4가지로 나가는 완전 트리의 형태를 생각해서 그래프 문제라고 생각하고 BFS적으로 접근했다. 여기까지의 생각은 어렵지 않았는데 python으로 풀다보니 시간초과에서 많이 애를 먹었다...

백준 7569 토마토(3차원배열, BFS)

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 상자에 있는 토마토가 근접해있는 다른 토마토에 영향이 가게 하는 것이니까 BFS로 접근하면 좋겠다는 생각을 했다. 여기서 첫번째 고려할점은 2차원이 아닌 3차원 방향이기 때문에 dx,dy,dz를 설정해줘야 한다는 것 dx = [-1, 1, 0, 0, 0, 0] dy = [0, 0, -1, 1, 0, 0] dz = [0, 0, 0, 0, -1, 1] 그 후 그래프를 돌면서 토..

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

Coding Test(Priority Queue, Heap)

우선순위 큐(Priority Queue) 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 - list를 이용한 구현 - heap을 이용한 구현 단순히 N개의 데이터를 heap에 넣었다가 모두 깨내는 작업은 정렬과 동일 == Heap Sort =>O(NlogN) Heap - Max value or Min value을 찾아내는 연산을 빠르게 하기위해 완전 이진 트리를 기본으로한 자료구조 - heap에서는 항상 root node를 제거 최소 힙(min heap) - root node가 가장 작은 값을 가진다 - 값이 작은 데이터가 우선적으로 제거 최대 힙(max heap) - root node가 가장 큰 값을 가진다 - 값이 큰 데이터가우선적으로 제거 완전 이진 트리(Complete Binary T..