Hello, Freakin world!

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;..

https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 간단하면서도 꽤 유익한 문제였습니다. 종종 정규표현식을 쓸 때 괄호를 이용한 그룹화를 이용하곤 했습니다. 하지만 대부분 패턴에서 특정 문자를 참조하기 위한 목적으로만 사용했는데, 수량 문자(+)와 괄호들을 조건을 조합해( | ) 이런 식으로 문자열을 매칭할 수 있다는건 처음 알았네요. import java.io.BufferedReader; import java.io.FileReader;..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 고전적인 dfs 문제입니다. 배추의 위치가 주어지므로 입력받은 배추의 위치를 기반으로 상하좌우 인접한 배추들을 방문하면 됩니다. 방문하면서 boolean 타입의 배열인 visited에 체크하면서 다시 방문하는 일이 없도록 합니다. import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.i..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net N의 첫번째 요소를 배정하는 위치하고 나서 나머지 N-1와 M-1에 대해서 부분구조를 발견할 수 있다. 점화식은 dp[n][m] = dp[n-1][1] + dp[n-1][2] ... + dp[n-1][m-1] 이다. 재귀 ver package backjoon.p1010; import java.io.BufferedReader; import java.io.IOException; import java...