전체 글 (44) 썸네일형 리스트형 [Java] BOJ1074_Z www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net "만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다." 문제에 분할정복과 재귀의 힌트가 다 주어졌다. 배열의 크기가 최대 2^15 * 2^15 이므로 배열 전체를 탐색하면 당연히 시간초과가 난다. import java.io.*; import java.util.StringTokenizer; public clas.. [Java] BOJ1068_트리 www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 트리에서 어떤 노드를 지웠을 때 남아있는 리프 노드의 수를 출력하는 문제이다. 해당 노드를 지우고 트리를 탐색해 리프 노드의 수만 세어주면 된다. 트리구조를 만들 때 리스트를 사용해서 만들었기 때문에 remove 함수로 해당 노드를 지우고 dfs방식으로 트리를 탐색해 리프 노드의 수를 셌다. 리프 노드는 자식 노드가 없는 노드로, 리스트 크기가 0인 노드를 의미한다. *예제는 각 노드의 부모 번호가 오름차.. [Java] BOJ10282_해킹 www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net "어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다." 이 부분에서 단방향 그래프라는 사실을 알 수 있다. 해킹당한 컴퓨터 번호 C에서부터 시작하여 감염되는 컴퓨터를 찾아 나아가는 다익스트라 알고리즘이다. result의 값이 바뀐 컴퓨터의 수를 세어 총 감염되는 컴퓨터의 수를 구했고 그 컴퓨.. [Java] BOJ2352_반도체 설계 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 연결선이 겹치지 않기 위해서는 연결 포트의 번호가 증가하는 형태여야 한다. 이를 통해 최장 증가 부분 수열(LIS) 문제라는 것을 알 수 있다. import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int[] arr; static int[] dp;.. 이전 1 ··· 3 4 5 6 다음
