Algorithm

구간 합 구하는 방법은 합 배열의 개념을 이용해서 해결할 수 있으나 이번 문제와 같은 경우, 중간 중간 수가 자주 변경되는 상황이 일어나기 때문에 합 배열로 풀기에는 시간이 오래 걸린다는 단점이 있다. 그렇기에 이와 같은 문제는 세그먼트 트리를 이용해 풀이하는 것이 권장된다. (세그먼트 트리의 경우, 개념 이해하는게 꽤 오래 걸렸으나 그래도 문제와 예제를 통해 세그먼트 트리 문제임을 알아채기가 편하다고 느껴졌다(?). 풀이 공식같은 것도 딱 정해져 있어서 차라리 그리디, 구현같은 것보다는 상대적으로 낫게 느껴진다..)  문제    예제  접근  트리 초기화하기 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다.트리 배열의 크기 구하는 방법 : 2^k >= N 을 만족하는 k의 최솟..

문제     풀이  4방향으로 탐색하며 인접한 칸 중 방문이 가능한 칸으로 이동하는 것을 보아 백준의 2178 미로찾기 문제와 비슷한 유형이라는 생각이 들었다. (BFS나 DFS로 풀이가 가능할 조짐이 보임.) 그러나 아래와 같은 추가적인 고려 사항이 있다. 1. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는  경우반시계 방향으로 90도 회전바라보는 방향 기준 앞쪽 칸이 청소되지 않은 경우, 한 칸 전진=> 큐에서 받아온 방향을 기준으로 반시계 방향 회전한 방향으로의 좌표를 구해 이동한다 ex) 위 문제에서 주어진 방향값은 0(북), 3(서), 2(남), 1(동) 이다.만약 현재 방향이 0(북)이고, 반시계 방향으로 회전한다면 아래와 같이 반복된다. (순환) 0(북) -> 3(서) -> 2(남)..

문제 https://www.acmicpc.net/problem/14501  다음 문제에서 목표로 하는 최대 수익을 얻으려면 모든 가능한 선택지를 비교하고, 가장 높은 수익을 선택해야 한다.아래 문제를 보면, i일 이후에도 얻을 수 있는 최대 수익을 대략적으로 계산할 수 있다. 이러한 특징을 기반으로 현재를 최적화하는 방식에 적합한 DP 방식으로 풀이해보았다.   점화식 세우기 i번째 날에서 선택될 수 있는 결정은 두 가지로 구분될 수 있다. 오늘 시작되는 상담을 했을 때, 퇴사일까지 끝나지 않는 경우 (상담하지 못한다)오늘 시작되는 상담을 했을 때, 퇴사일 안에 끝나는 경우 (상담한다)   i일에 상담 가능한 경우의 기준상담이 끝나는 날인 i + T[i] -1 일이 N 이하여야 한다.즉, i + T[..

두 노드 사이가 길이가 가장 긴 값을 찾는 문제이다.임의의 지점에서 가장 먼 정점을 찾고, 다시 그정점으로부터 가장 먼 정점을 구하면 트리의 지름이 된다. 문제   임의의 노드 1에서 시작했다고 가정한 다음, 이전 연결 노드의 가중치를 합산해가며 노드 거리의 배열을 저장 한다. 그리고 가장거리가 먼 노드를 찾으면 그 정점에서 BFS를 재실행하는 방식으로 노드 거리 배열을 저장하며 답을 구한다.     BFS 풀이package BFS;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class BOJ1167 { static ArrayList[]..

수열 A에 대해 버블 소트를 수행했을 때, swap이 총 몇 번 발생하는지를 알아내는 문제이다. N의 범위가 최대 500,000이기에 O(n^2)인 버블 소트로 풀이하면 시간 초과가 발생하는 문제가 발생한다. 여기서는 O(NlogN)의 시간복잡도를 가진 병합 정렬을 사용하여 풀이하였다. 두 그룹을 병합하는 과정에서 버블 정렬의 swap이 포함되어 있다는 것을 떠올리는게 포인트였다.  문제    문제 풀이 버블 소트에서 swap이 일어나는 조건 : 배열 앞의 숫자가 뒤의 숫자보다 클 때 (A[i] > A[i+n])result의 자료형을 처음에는 int로 설정했었으나 틀렸다는 결과가 뜨자 long으로 바꾸었더니 통과가 되었다.아마도 최악의 경우, n의 최대 범위에서 모두 swap이 일어나고, 그 swap 횟..

앞서 포스팅한 수 정렬하기2 문제를 풀면서 이해 안가는 부분이 있어 병합 정렬의 개념을 다시 한번 복기하고자 이 문제를 풀이해보았다.재귀를 활용한 Top down 방식으로 풀이하였다.문제   풀이 import java.util.Arrays;import java.util.Scanner;// 배열 A에 K 번째 저장되는 수를 구하는 문제public class BOJ24060 { static int[] arr, tmp; // 저장 횟수 누적 카운트 static int count = 0; // 결과 (실패 시 -1 출력) static int result = -1; // 저장 횟수 static int k; public static void main(String[] arg..

문제     문제 풀이  안일하게 Array.sort() 돌렸다가 시간초과가 났었다.검색해보니 Arrays.sort()는 dual pivot quicksort 알고리즘을 사용하기에 시간 초과가 난 것이라고 한다.dual-pivot Quicksort 알고리즘은 평균 시간복잡도가 O(nlogn) 이고, 최악의 경우 시간복잡도는 O(n2) 이기 때문에..N의 범위가 1,000,000까지로 꽤나 크다 보니 최악의 경우 시간복잡도가 O(nlogn)인 알고리즘을 활용해야 했다.힙 정렬과 병합 정렬이 해당하는데 병합 정렬을 적용하여 풀이하였다.       병합정렬 풀이 import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOExcept..

캡스톤, 기말 등 각종 이벤트들로 인해 그동안 백준을 많이 풀지 못하였는데 쉬운 것부터 다시 복습하고자 정리해보았다.이전 포스트와 같이 인접 행렬, 인접리스트, 그래프 형태로 풀이해보았다. 문제  문제를 통해 탐색을 시작할 정점의 번호가 1번부터 시작한다는 것을 알 수 있다.  입력 예제   문제 풀이 입력 예제를 참고하여 아래와 같이 그래프를 그리고, 그에 따른 인접리스트와 각 노드 별 연결 상태를 나타내는 행렬을 그려보았다.BFS 기준으로 탐색을 진행하였을 때에는 1, 2, 5, 3, 6의 순서로 이동하고, 이 때 바이러스에 걸리게 되는 컴퓨터의 수는 1번 컴퓨터를 제외한 4개이다. 이러한 연결 및 탐색 정보를 통해 BFS로 풀면 간단하게 풀리겠구나를 짐작하고 코드로 옮겨보았다.      인접 리스트..