Hello, Freakin world!

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄�� www.acmicpc.net 구간 트리의 개념과 기분 구현을 할 수 있는지 묻는 문제입니다. 구간 트리에 대한 설명은 아래 글을 참고하세용 javachoi.tistory.com/292 구간 트리(Segment Tree) 구간 트리란? 구간 트리의 정체는 이진 트리입니다. 구간 트리 라는 이름은 그저 특정 용도로 사용되는 이진 트리의 한 형태를 나타낼 뿐입니다. 대..

구간 트리란? 구간 트리의 정체는 이진 트리입니다. 구간 트리 라는 이름은 그저 특정 용도로 사용되는 이진 트리의 한 형태를 나타낼 뿐입니다. 대게 구간 트리는 일차원 배열 상의 특정 구간에 대한 요청에 빠르게 대답하기 위해 사용합니다. 예를 들어, 1 2 3 4 5 라는 숫자 배열이 있다고 하겠습니다. 이 배열의 특정 구간의 합을 구한다고 할 때, 가장 간단한 방법은 그 특정 구간을 순회하면서 값을 더해나가는 겁니다. 이 경우 시간 복잡도는 O(n)이 됩니다. 만약 배열의 길이가 10억쯤 된다면 어떨까요? 컴퓨터가 1초에 1억번 정도의 루프를 돌린다고 하면 10초가 걸리겠네요. 그리고 또 이 합연산이 여러번 호출될 가능성이 있다면 어떨까요? 이 연산은 매번 합을 새로 구하기 때문에 문제가 됩니다. 구간..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 오랜만에 bfs 문제를 만나게 됐네요 ㅎㅎㅎ 처음에 낸 풀이는 메모리 초과가 떴습니다. 문제는 방문한 노드들을 체크하는 시점 때문에 발생한 문제였는데요. 예를 들면 dfs에서는 노드를 방문하고 나서야 현재 노드에 방문 체크를 하게 됩니다. 하지만 bfs는 방문 이전 시점, 즉 이전 노드에 의해 큐에 추가 될때 이미 방문 체크를 해버립니다. 왜 이렇게 하는가? 라는건 조금만 생각해..

www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제는 이해했지만 어떻게 구현할지 굉장히 막막했던 문제였습니다. 주어지는 입력 자체도 굉장히 까다로웠습니다. 경과된 시간을 주고 그 때 방향이 주어지는데 어떻게 구현하고 이 입력을 해석 해야 하는지 감이 잡히지 않았습니다. 풀이를 참고해보니, 데큐를 이용해서 뱀을 구현했더군요. !!! 굉장히 편리한 방식이었습니다. 경과된 시간이 주어지는 입력에 대한 접근 방식에도 꽤 도움이 됐던 문제였습니다. ... /* 백준 319..

www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 값이 정렬된 배열에서 중복된 값이 있을 때, 이분 탐색으로 중복된 영역의 하한, 상한 경계를 찾아낼 수 있으면 쉽게 풀 수 있는 문제입니다. lower, upper 두 경우에 범위 설정이 살짝 달라집니다. lower에서는 왼쪽 범위가 start~mid 가 되고 오른쪽 범위는 mid+1~end가 되지만 upper에서는 왼쪽 범위가 start~mid-1, 오른쪽은 mid~end가 ..

www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 www.acmicpc.net 문제 풀이 자를 수 있는 나무의 높이는 1 ~ 최대 나무 길이(L) 입니다. 이 범위에서 '높이의 중간값을 지정해 잘라가면서 얻는 나무 토막의 길이'를 이용해 이분탐색을 시행하면 답을 얻을 수 있습니다. ... /* 백준 2805번 - 나무 자르기 https://www.acmicpc.net/problem/2805 */ public class Main { static int..

https://www.acmicpc.net/problem/2446 2446번: 별 찍기 - 9 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 공백이 아닌 각 행의 문자열의 처음(head)과 끝(tail)을 추척하면서 구현했습니다. /* 백준 2446번 - 별 찍기9 https://www.acmicpc.net/problem/2446 */ public class Main { static int n; static int length; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in));..

www.acmicpc.net/problem/11376 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, � www.acmicpc.net 열혈강호1의 풀이를 두번씩 반복해주면 된다. 허무할 수도 있는 문제지만 정답을 보지 않고 이를 유추하기는 꽤 어려운듯하다.(적어도 나한테는...) 재귀함수 정의 자체를 수정해서 문제를 해결하려해서 문제가 상당히 복잡해졌었다. 결국 해답을 보고 허무하기도 했지만, 이를 발견하지 못했던 것 역시 진정으로 이분 매칭 알고리즘을 이해하지 못했기 때문이었다는걸 느꼈다. 이번 문제는 시간 여유가 있어 이분 ..

www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각�� www.acmicpc.net package backjoon.networkflow.bipartitematching.p11375; import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.InputStreamReader; import java.util.Arrays; import java.uti..

www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해� www.acmicpc.net 이분 매칭 알고리즘을 구현하기만 하면 통과하는 문제라 문제 풀이보단 이분 매칭에 대한 고찰 몇 가지를 남기려 합니다. 아래는 정답 코드입니다. ... /* 백준 2188번 - 축사 배정 https://www.acmicpc.net/problem/2188 */ public class Main { static int[][] edges; // 간선 [cow][barn] static int[] aMatch, bMatch;..