알고리즘
[백준 - 1946] 실버1 신입 사원 (그리디)
www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성�� www.acmicpc.net 1. 유형 그리디 2. 풀이 문제를 이해하는데 오래 걸렸다. 서류 순으로 오름차순 정렬한다. 그 다음 면접 성적 순으로 우선순위 큐에 넣는다. 그러면 서류 성적은 더 낮지만 면접 성적은 더 높은 사람이 들어올 수 있다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRea..
[백준 - 2531] 실버1 회전 초밥 (투포인터)
www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 1. 유형 투 포인터 2. 풀이 이중 for문을 쓰면 시간 초과가 나기 때문에, 슬라이딩 윈도우를 써야한다 3. 코드 import java.util.Scanner; public class back_2531회전초밥 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc..
[백준 - 3274] 실버4 두 수의합 (투포인터)
www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 1. 유형 두 포인터 2. 풀이법 단순히 이중for문을 사용하면 시간 초과가 난다 그렇기 때문에 정렬후, 이분탐색을 사용해야한다 3. 코드 import java.util.Arrays; import java.util.Scanner; public class back_3273두수의합 { public static void main(String[] args) { S..
[백준 - 17135] 골드4 캐슬디팬스 (구현)
www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 1. 유형 조합, bfs, 시뮬레이션 2. 풀이 조합을 이용해서 궁수의 위치를 정해준다. 궁수의 위치마다 bfs를 돌려준다. 적을 찾았으면 동시에 적을 죽여야한다. 3. 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class back_17135캐슬디펜스 { static int M,N,map[][], D, an..
![[백준 - 11497] 실버2 통나무 건너뛰기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F7LEew%2FbtqJZm5zNmd%2FKQZrTQJNStKSk43Au8VfZk%2Fimg.png)
[백준 - 11497] 실버2 통나무 건너뛰기
www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 1. 유형 그리디 2. 풀이 입력값을 정렬한 후에 아래 그림처럼 나올 수 있도록 +2만큼 건너 뛰면서 탐색한다. 3. 코드 import java.util.Arrays; import java.util.Scanner; public class back_11497통나무건너뛰기 { public static void main(String[] args) { Scanner sc = new Scanner(System.in);..
[백준 - 19539] 실버1 사과나무 (그리디)
www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 1. 유형 그리디 2. 풀이법 사과나무 크기의 합이 3의 배수이다 홀수의 갯수가 전체합/3보다 작아야한다. 예를 들어 {1 2 1 2}는 가능하다. 하지만 {3 1 1 1}는 불가능하다. 한 턴에 물뿌리게를 다 써야하니깐.... 그래서 두번째 조건이 들어가야 한다 3. 코드 import java.util.Scanner; public class back_19539사과나무 { public static void main(String[] args) { Scann..
[백준 - 2668] 골드5 숫자고르기
www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절� www.acmicpc.net 1. 유형 dfs 2. 풀이 싸이클 발생 여부를 판단한다. 처음 입력값을 보고 그래프를 생각 해야한다 3. 코드 처음 풀이 -> 조합 이용, N이 100개나 되기 때문에 잘못된 방법이다. import java.util.Scanner; public class Test { static int N, map[][], answer=0,ans[]; static boolean visit[][]; static ..
[백준 - 17780] 골드2 - 새로운 게임
www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net 풀이시간: 1시간 50분 1. 유형 시뮬레이션 2. 풀이법 ArrayList로 이차원 배열을 만드는 발상이 중요하다. 또한 파란색을 밟았을 때, 뒤돌아 가는 것이 중요하다. static int side[] = {0, 2, 1, 4, 3}; 처럼 반대 방향을 따로 저장 3.코드 package 나혼자푸는문제; import java.io.BufferedReader; import java.io.IOException;..
다익스트라 알고리즘
1. 개념 두 노드를 연결할 때, 가중치가 최소인 것을 구하는 알고리즘 2. 설명 1부터 시작할 때, minEdge[] 배열을 나타냈다. 각 노드를 탐색하면서 minEdge에 가중치를 누적 시킨다. 3. 문제 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net for문을 전부 탐색해서 최소 누적치를 찾는 풀이 -> 시간초과 때문에, 노드 수가 많으면 못 푼다. import java.util.ArrayList; import java.ut..
[백준 17471] 골드5 - 게리맨더링
www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이시간 : 1시간 1. 유형 BFS, 조합 2. 풀이 노드가 10개 밖에 되지 않으니깐, 조합으로 레드팀과 블루팀으로 나눈다. 그 후, BFS를 돌려서 판단 3. 코드 import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class back_17471게리맨더링 { static Arr..
[백준 15558] 실버1 - 점프 게임
www.acmicpc.net/problem/15558 15558번: 점프 게임 첫째 줄에 N과 k가 주어진다. (1 ≤ N, k ≤ 100,000) 둘째 줄에는 왼쪽 줄의 정보가 주어진다. i번째 문자가 0인 경우에는 위험한 칸이고, 1인 경우에는 안전한 칸이다. 셋째 줄에는 오른쪽 줄의 정보�� www.acmicpc.net 풀이시간: 50분 1. 개념 BFS 2. 풀이법 (0,0)에서 bfs를 돌린다. 큐 안에 x,y, 시간을 배열로 집어넣는다 3. 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class back_15558점프게임 { static int n,k; static int map[..
[백준 17086] 실버1 -아기 상어 2
www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 풀이시간: 50분 1. 개념 BFS 2. 풀이 큐에 x, y, d를 넣고나서 bfs를 돌린다 3. 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class back_아기상어217086 { static int n, m, map[][]; static int dr[] = { -..
[백준 11403] 실버1 - 경로 찾기
www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이시간: 1시간 1. 개념 인접 행렬, 그래프 탐색 2. 풀이법 인접 행렬을 만든다. 시작 지점부터 연결된 지점을 재귀를 이용하여 계속 탐색한다. 만약 타깃을 찾으면 true를 리턴하고 재귀를 빠져나온다. 3. 코드 import java.util.ArrayList; import java.util.Scanner; public class back_11403경로찾기 { static int n; static int list[][]; static boolean..
[백준 2116] 골드5 - 주사위 쌓기
www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 � www.acmicpc.net 1. 개념 시뮬레이션 2. 풀이법 주사위의 반대편 면을 배열로 만들어서 체크하는게 중요하다. 3. 코드 import java.util.Scanner; public class back_2116주사위쌓기 { static int side_idx[] = {5,3,4,1,2,0}; static int box[][]; public static void main(String[] args) { Scanner sc = new S..
투 포인터
1. 투 포인터 포인터를 2개 사용하여 더 빠르게 배열을 탐색할 수 있다. 2. 예시문제 www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 3. 설명 문제의 N의 크기가 100000이기 때문에 이중for문을 쓰면 시간 초과가 난다. 그렇기 때문에 투 포인터를 사용해야한다. k개를 탐색한 경우 가장 마지막에 더한 값을 빼주고, 현재 값을 더하는 식으로 해결 가능 import java.util.Scanner; public class back_2559수..
[백준 14002] 골드4 - 가장 긴 증가하는 부분수열4
1. 개념 2. 난이도 3. 코드 www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.uti..
LIS 최장 증가 부분수열
1. 개념 2. 예시 swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com O(N^2) 풀이법 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Scanner; public class swea_3307최장증가부분수열 { public static void main(String[] args) { Scanner sc = new Sc..
SWEA level3 - 3282 0/1 knapsack
swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJAVpqrzQDFAWr&categoryId=AWBJAVpqrzQDFAWr&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 종류 동적프로그래밍 2. 풀이 dp의 특징을 잘 나타낸 문제다. 고려해야할 변수가 2개(부피, 가치)이기 때문에 2차원 배열을 사용해야 한다. 3. 코드 import java.util.Arrays; import java.util.Scanner; public class swea3282_knapsack { public static..
![[백준 10157] 자리배정](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcQWG0u%2FbtqI6N4Ru5o%2F5MF82enzXhgkhp72AErJH0%2Fimg.png)
[백준 10157] 자리배정
www.acmicpc.net/problem/10157 10157번: 자리배정 첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. www.acmicpc.net 1. 유형 : 구현 2. 설명 : 흔한 달팽이 문제다. 시작좌표를 설정하고, 동서남북의 바운더리를 설정해준다. 밑에 그림처럼 처음엔 파랑색, 노랑색, 녹색, 보라색 순으로 한 사이클을 탐색한다. 저것을 target을 찾을 때까지 반복한다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStr..
순열과 조합 뿌시기
1. 순열 1) 순열이란? {1,2,3}이 주어졌을 때, {1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}처럼 순서를 바꿔서 나타낼수 있는 모든 경우를 말한다 2) 코드 크기가 3인 배열의 순열을 구했다. public class 순열 { static String fruits[] = {"사과", "바나나", "딸기"}; static boolean check[]= new boolean[3]; static String[] sel = new String[3]; public static void main(String[] args) { perm(0); } static void perm(int select_idx) { if(select_idx == fruits.length) { S..