Algorithm

문제 링크 # https://www.acmicpc.net/problem/1389 문제 해설 # Idea # BFS 1부터 N까지의 번호에 대해 매번 BFS를 수행하면서 다른 모든 노드와의 거리를 파악 가장 작은 거리의 합을 가진 노드의 인덱스 번호를 출력 Time Complexity # O(N^2+NM) = 510,000 Data Size # N: 2 …

문제 링크 # https://www.acmicpc.net/problem/5430 문제 해설 # Idea # Implementation, Deque 문제에서 주어진대로 매번 배열을 뒤집으면 O(N^2)의 시간 복잡도로 시간 초과가 발생 배열에 영향을 주지 않으면서 R 함수를 처리하기 위해 상태 변수를 정의하고, D 함수가 호출될 경우 배열의 상태에 따라 첫 …

문제 링크 # https://www.acmicpc.net/problem/1463 문제 해설 # Idea # Dynamic Programming N에 대해 조건을 만족하는 경우에서 3으로 나누기, 2로 나누기, 1 …

문제 링크 # https://www.acmicpc.net/problem/1697 문제 해설 # Idea # BFS N에서 시작해 K에 도달할 때까지 x-1, x+1, x*2에 대한 최단거리를 탐색 두 점이 위치할 수 있는 범위 내에서 가까운 거리의 점부터 탐색을 수행 K에 대한 거리를 출력 N이 K보다 클 경우 x-1 외에는 이동수단이 없기 때문에 시간 단 …

문제 링크 # https://www.acmicpc.net/problem/20922 문제 해설 # Idea # Two Pointer 수열의 시작과 끝 지점에 대한 두 개의 포인터 지정 끝 지점에 대한 포인터를 확장하면서 탐색되는 원소의 수를 카운트 원소의 수가 K개와 같아지는 시점부터 시작 지점에 대한 포인터를 확장하여 범위 축소 최종적으로 두 포인터 간 거 …

문제 링크 # https://www.acmicpc.net/problem/22859 문제 해설 # Idea # Implementation, String , , 태그 등을 구분 의 attribute인 title을 우선 출력하고 안에 있는 를 한 줄씩 출력 안에 있는 태그와 시작과 끝에 있는 공백을 지우고 2개 이상의 공백을 하나로 변경 제목은 무조건 존재하고 …

문제 링크 # https://school.programmers.co.kr/learn/courses/30/lessons/43238 문제 해설 # Idea # Binary Search answer에 대한 이진탐색 수행 (1 <= answer <= max(times)*n) 매 탐색마다 answer …

문제 링크 # https://school.programmers.co.kr/learn/courses/30/lessons/42895 문제 해설 # Idea # Dynamic Programming S[1] = {N} S[2] = {NN, N+N, N-N, N*N, N/N} S[3] = {NNN, S[2][x] (+,-,*,/) S[1][y], …} …

문제 링크 # https://www.acmicpc.net/problem/21318 문제 해설 # Idea # Prefix Sum 실수한 곡에 대한 누적합을 구하고 인덱싱을 통해 특정 구간에 대한 누적합 출력 마지막 곡은 항상 성공하기 때문에 y에 대한 누적합과 y-1에 대한 누적합이 다르면 1 감소 Time Complexity # Prefix Sum: …

문제 링크 # https://www.acmicpc.net/problem/16987 문제 해설 # Idea # Backtracking 0번째 계란부터 마지막 계란까지의 모든 경우의 수를 탐색 시간 단축을 위해 현재 계란이 깨진 경우 또는 나머지 모든 계란이 깨진 경우를 예외로 처리 한 번에 두 개 이상의 계란을 치는 경우를 방지하기 위해 계란을 친 후 원상복 …