0. 문제 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. 문제 이해 위상 정렬 BFS 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Queue; import java.util.StringTokenizer; public class BOJ2252 { st..

1. 그래프 정점 간의 관계를 간선으로 표현한 것. 간선의 방향에 따라서 무향 그래프(양방향 그래프), 유향 그래프로 나뉠 수 있다. 밀집도에 따라서 완전 그래프, 밀집 그래프 그리고 희소 그래프로 나뉜다. 이 외에도 가중치 그래프, 사이클 없는 그래프 등 다양한 그래프가 존재한다. 그래프를 표현하는 방식은 크게 3가지 있다. 그래프 표현 방식 설명 시간 복잡도 (연결 여부 확인) 공간 복잡도 특징 인접 행렬 그래프의 노드들을 2차원 배열에 저장. 배열의 행과 열은 각각 그래프의 노드를 의미하며, 배열의 값은 두 노드 간의 간선 유무(또는 가중치)를 의미함. O(1) O(V^2) -구현이 쉽다. -진입 차수를 구하기 쉽다. -밀집 그래프에 유리한다. 인접 리스트 각 노드에 연결된 노드들을 리스트로 저장...

1. 16435. 스네이크버드 그리디 알고리즘 - 정렬 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 2. 2839. 설탕 배달 그리디 알고리즘 - 동전 자판기 변형 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 3. 1860. 진기의 최고급 붕어빵 시뮬레이션 SW Exp..

0. 문제 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1. 문제 이해 그래프 BFS 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; public class BOJ7576 { static int n, m, ret; static int[][] map; stati..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 백트래킹 순열 DP 2. 제출 가. 순열 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class SWEA1247 { static int n, ret; static boolean[] vis; static Point work, home; static Point[] custs; public static void main(String[] args) throw..

0. 문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 이해 백트래킹 2. 시간 초과 n이 14일 때 10초 이내로 통과해야 함. 가. 시간 초과 import java.util.Scanner; public class BOJ9663 { static int[] map; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 체스판을 1차원 배열로 표현 // y행 x열 -> map[y*n ..

0. 문제 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 1. 문제 이해 분할 정복 알고리즘 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ1074 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new ..

1. 분할 정복 Divide and Conquer 해결할 문제를 여러 작은 부분 문제로 나눈다. 나눈 작은 문제를 각각 해결한다. 접근법 Top-down approach bottom-up approach // Power 함수 import java.util.Scanner; // x^n을 O(logN) 시간복잡도로 구하는 분할 정복 알고리즘 public class SquareNumberTest { static int callCnt1; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); int n = sc.nextInt(); // 최대 10억 System.out.println(exp1..