알고리즘/백준
[백준 - 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;..
[백준 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..
[백준 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..
![[백준 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..
[백준 1405] 미친 로봇
https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자�� www.acmicpc.net 유형 dfs 로직 dfs를 돌린다 -> 재방문 하는 곳은 리턴 -> dfs를 돌리면서 방향에 맞는 확률도 같이 계산해서 파라미터로 넘겨준다 -> 주어진 N 만큼 깊이로 탐색을 했을 시 확률을 더해준다 코드 package 백준; import java.util.Scanner; public class 미친로봇1405 { static int dr[]= {0,0,1,-1}; static int dc..
백준 16234 인구 이동
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net 유형: bfs, 시뮬레이션 나라별로 구분 map을 구분 짓는다. bfs로 알 수 있음 bfs가 끝 났을 때 avg함수를 사용하여 ma..
백준 15686 치킨 배달
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 치킨집을 선택, 재귀를 사용 집에서 선택한 치킨집 중에서 거리가 최소인 것을 선택 위 에서 구한 거리를 모두 더한다 /* 치킨집을 m..
백준 15685 드래곤 커브
https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2, www.acmicpc.net 유형: 시뮬레이션 방향의 규칙성을 먼저 찾는다. 시작점에서 벡터의 정보대로 드레곤 커브를 완성한다 map에 1로 업데이트 한다 주어..
15684 사다리 조작
https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 www.acmicpc.net 유형: 시뮬레이션 재귀를 이용하여 막대기의 조합 만들기. (선택,비선택) check함수를 만들어 col이 원 위치로 오는지 확인 /..
15683 감시
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 www.acmicpc.net 유형: 시뮬레이션 1. 한 방향만 보는 함수를 생성 see함수 생성 2. cctv 갯수만큼 재귀함수를 돌린다 3. cctv타입 마다 볼 수..
14891번 톱니바퀴
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려 www.acmicpc.net 유형: 시뮬레이션 /* sol for 0이상 if 6,2 같으면 break else 방향left = 방향right *-1 for 4미..