Hello, Freakin world!

www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; /* 경로 찾기 */ public class Main { static int n; static int[][] adj; public static void main(String[] args) throws IOException { /..

www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0� www.acmicpc.net 물론 언어에서 제공하는 우선순위 큐를 이용할 수도 있겠지만... 그닥 재미는 없어보인다. 구현 방식에 특별하게 추가하는 건 없다. 기존의 전형적인 힙 구현 코드에 요소가 같을 경우 작은 수를 반환한다는 조건을 추가하면 된다. (그럼에도 불구하고 8번 틀렸다 ㅋㅋㅋㅋㅋ. >= 와 > 차이로 인한 차이였는데 왠만한 테스트케이스가 다 맞게 나와서 더 애를 먹었다. 테스트 케이스 찾기는 포기하고..

www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색시 종결 조건에 대해서 정리하려고 합니다. 우선 위의 상황을 간단하게 설명하겠습니다. 우리는 이 문제와 같이 어떤 특정 값(max)에 최대한 근접하는 최대값을 찾고 싶습니다. 위 사진은 이분 탐색을 통해 범위를 2개까지 좁힌 상태이고 a < max < b 이므로 답은 a가 나와야 합니다. 범위를 이분하는 방식은 (low + high)/2 에서 계산한 값을 기준으로 max보다 클 경우 왼쪽 범위, ..

www.acmicpc.net/problem/17827 17827번: 달팽이 리스트 첫째 줄에 노드의 개수 N(2 ≤ N ≤ 200,000), 질문의 횟수 M(1 ≤ M ≤ 200,000), N번 노드가 가리키는 노드의 번호 V(2 ≤ V ≤ N)가 공백으로 구분되어 주어진다. 둘째 줄에 N개의 정수 C1, C2, …, CN이 공백 www.acmicpc.net 전체 배열에서 어느 부분만 순환하는 부분 구조를 지니는 부분에서 K번째 요소를 찾으려고 합니다. 순환하는 크기만큼만 나머지 연산을 해주고 순환하지 않는 부분만큼 자리 이동해주면 해당 요소를 찾을 수 있습니다. 자세한 건 코드 주석을 확인하세용 팁) 개인적으로 배열에 나머지 연산을 할 때, 처음 인덱스를 1로 하는것보다 0으로 하는게 더 편했습니다. ..

www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net V-A 거리에 대해 자면서 이동한 날을 구해 범위를 좁힌 다음, 이동한 날을 계산합니다. 코드의 주석을 참고하세요. import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; /* 달팽이는 올라가고 싶다 https://www.acmicpc.net/problem/2869 */ public class Main { static long a,b,v; p..

www.acmicpc.net/problem/1959 1959번: 달팽이3 첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다. 둘째 줄에 끝나는 점의 좌표를 출력한다. 왼쪽 위 칸의 좌표를 (1, 1), 오른쪽 아래 칸의 좌표를 (M, N)이라고 하자. www.acmicpc.net 입력의 크기가 어마어마하기 때문에 직접 그리면서 화살표가 꺾이는 부분을 일일이 체크할 수 없다(꺾이는 부분을 curve point라고 부르기로 하자). 이럴 경우 규칙을 찾아내 복잡도를 줄이든지 답을 내는 식을 찾든지 해야 된다. 자, 이제 다음과 같은 M,N 크기의 사각형이 있다고 하자. 사각형의 가장 자리를 다 돌고 이제 빨간색 사각형으로 순회를 시작하려고 한다. 위 그림처럼 내부에 빨간색 사각형처럼 내..

www.acmicpc.net/problem/1952 1952번: 달팽이2 M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다. 위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 www.acmicpc.net 달팽이 시리즈 문제입니다. 이전 달팽이 문제에서는 순회할 때 세야하는 칸의 개수를 유지했는데, 이번엔 이차원 boolean 배열을 이용해 방문한 곳을 체크하고 방문하지 않은 곳까지만 방문하는 방식으로 구현해봤습니다. 개인적으로 이 방법이 더 간단한 듯 하네요. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import j..

www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 문제 풀이 2차원 배열을 달팽이 방향으로 순회하면서 숫자를 기입하는 문제입니다. 시계 방향으로 순회하기 때문에 방향은 상,우,하,좌 이렇게 1차원 배열에 넣고 순환시키면 될 것 같습니다. 그리고 이 문제의 경우 한 쪽 방향으로 숫자 개수가 점점 커지기 때문에 이 점도 고려해야 합니다. 찬찬히 살펴보면 어느 방향이든 (한쪽 행, 한쪽 열)이 사이클이 되며 이 때마다 필요한 숫자 개수가 하나씩 늘어납니다. 주의할 점..

www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net 위에서 a값(인턴에 참가하는 남학생 수)를 구할 때, 정수가 아닌 값이 나올 수가 있다. a값은 팀의 수가 최대일 때의 값이므로 이 값에 최대한 가까운 정수값을 써야 한다. 간단하게 이 값을 반올림해주면 된다. (값이 범위를 넘어가는 경우에는 0 또는 k값을 반환하도록 처리해줘야 한다.) 그 다음은 남자, 여자 총원에서 a, k-a를 각각 빼주고 팀을 카운트하면 끝~ import java.io.*; import java.util.ArrayList; import java.util...

www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 풀이를 둘러보니 상태를 저장하는 방법이 꽤 여러 가지였습니다. 각 요소의 값이 모두 1자리기 때문에 문자열이나 그냥 정수로 상태를 표현한 풀이도 가능합니다. 하지만 값이 한 자리를 넘어가는 순간 값들을 분리해야 되기 때문에 다른 방법이 필요할겁니다. 비트마스킹은 입력의 범위가 크지 않다면 일반적인 대안이 될 수 있습니다. 이 문제의 경우 0~9까지의 수를 표현하기 위해 4자리의 비트가 필요합니다. 수를 모두 9개이므로 36비트가 필요하겠네요. 자바 int 자료형은 32비트라서 안되고 lo..