전체 글
[백준 - 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수..