본문 바로가기

전체 글533

[알고리즘] 풍선 터트리기 (월간 코드 챌린지 시즌1 - 9월) 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 월간 코드 챌린지 9월에 나온 레벨3 문제다. 9월 10월 둘 다 풀면서 느낀건 브루트 포스 문제보단 아이디어로 시간복잡도를 최소화 해가면서 푸는 방식을 원하는 것 같다. 이 문제 또한 N이 최대 1백만이기에 O(N ^ 2)으론 풀 수가 없다. Solution 먼저 파악해야할 것은 어떤 특정값이 최후까지 살아남는지 알아볼 때, 양쪽에 있는 수들은 서로 만날 수가 없다. 그렇기에 특정값을 기준으로 왼쪽 오른쪽으로 나누어서 살펴봐야 한다. 그리고 양쪽에서 최후까지 살아남을 수 있는 수는 각각 2가지가 되는데 '최소값, 최소값보다 한단계 더 큰 값'이 될 수 있다. 최소값은.. 2020. 10. 9.
[알고리즘] 코딩테스트 전, 알고리즘 문제 유형 정리 ※ 생각 나는 대로 적는 중... (잘못된 부분이 있을 수도 있음) 브루트 포스 (완전 탐색) N의 범위를 잘 파악해서 1초 미만으로 해결이 가능한 경우 10! 이하의 시간복잡도인 경우 (재귀 호출 시 깊이가 10 이하인 경우) 1. 백트랙킹 순열 : 순서 고려 O, 값의 중복 X (시간복잡도 : O(N!) ) 중복 순열 : 순서 고려 O, 값의 중복 O (시간복잡도 : O(n ^ r), 여기서 r은 재귀의 깊이 ) 조합 : 순서 고려 X, 값의 중복 X 중복 조합 : 순서 고려 X, 값의 중복 O 재귀 호출 시 깊이를 보고 시간복잡도 파악 가능하다. 2. BFS 출발값이 존재 도착값까지 '최소' 시간 or 거리 or 횟수 만에 도착해야하는 경우 간선의 가중치(노드 간 거리)가 전부 같은 경우 (무가중 .. 2020. 10. 7.
[알고리즘] 색종이 만들기 (백준 2630번) 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 첨에 문제를 제대로 안 읽고 풀다가 끙끙거렸는데 다시 제대로 읽어보니 분할 정복 문제였다. 시키는 대로 재귀호출로 종이를 4조각씩 잘라나가서 최종적으로 잘려지는 종이들의 수를 세면 된다. Solution import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter impo.. 2020. 10. 7.
[알고리즘] 파티 (백준 1238번) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어� www.acmicpc.net 최단 시간만에 X번까지 왕복하는 시간을 구해야한다. 즉 각 마을에서 X번까지의 최단 시간, X번에서 각 마을까지의 최단 시간을 둘 다 구해야한다. 가장 쉽게 생각할 수 있는 방법은 플로이드 와샬로 모든 구간의 최단 시간을 구하는 것이다. 시간이 오래 걸리지만 풀긴 풀 수 있는 것 같다. (사실 1000의 3제곱이면 10억인데 못 풀 거라 생각했는데 풀긴 풀더라...) 하지만 X번까지의 왕복 정보 외에는 다른 정보들은 필요가 없다... 2020. 10. 7.

티스토리툴바