알고리즘/백준

알고리즘/백준
[백준 - 1405] 골드5 - 미친 로봇
www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 1. 유형 dfs, 백트래킹 2. 풀이 구현기능: 중복 탐색, 완전탐색, 확률계산 자료구조: 배열 단순할 조건 - 왔던 좌표를 다시 방문하지 않는 경우 즉, dfs 사용해서 4방향에 대한 완전 탐색을 해야함. 이떄, 방문한 좌표를 만날 경우 백트래킹을 한다. 주의 할점은 좌표를 0,0 부터 시작하면 인덱스 에러가 나기 때문에, 14, 14 부터 시작하고 배열 크기는 [29][29]로 잡음. 3. 코드 imp..
→2020.12.11
알고리즘/백준
[백준 - 20055] 실버1 - 컨베이어 벨트 위의 로봇
www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 1. 유형 구현 2. 풀이 로봇 배열, 내구도 배열 지정 규칙 순서대로 진행 규칙에는 안나와 있는거 같은데, 상식적으로 처음에 컨베이어 벨트 한칸 이동시 벨트 위에 있는 로봇 또한 같이 움직이는 걸 생각해 주자. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; i..
→2020.12.03
알고리즘/백준
[백준 - 20166] 골드5 - 문자열 지옥에 빠진 호석
www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 1. 유형 시뮬레이션, bfs, 해쉬맵 2. 풀이 시간 복잡도는 10*10* 8^5 이다 한 칸당 8방향으로 최대 5의 길이만큼 이동 할 수 있어서이다. 해쉬맵을 사용 맨 마지막으로 주의할 점은 신이 좋아하는 문자열은 중복될 수도 있다 부분이다. 이 조건을 못 읽고 풀어서 시간 낭비를 많이 했다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.u..
→2020.12.01
알고리즘/백준
[백준 - 19952] 골드4 - 인성 문제 있어??
www.acmicpc.net/problem/19952 19952번: 인성 문제 있어?? 인성이는 인싸가 되기 위해서 인싸트 특별과정에 참가했다. 훈련 첫날 인성이는 험난한 미로에서 목적지에 도달해야 하는 훈련을 받고 있다. 제한 시간 안에 미로를 통과하지 못하면 명기 교관 www.acmicpc.net 1. 유형 시뮬레이션 2. 풀이 이 문제의 핵심은 3차원 배열을 사용해서 bfs를 사용할 수 있는가 이다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util...
→2020.11.30
알고리즘/백준
[백준 - 20165] 골드5 - 인내의 도미노 장인 호석(java)
www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 1. 유형 시뮬레이션 2. 풀이 푼 시간: 1시간 00분 1. 도미노 높이를 저장한 map, 도미노 상태를 저장한 map 설정 2. 주어진 조건대로 풀이 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; publ..
→2020.11.30
알고리즘/백준
[백준 - 19640] 골드5 - 화장실의 규칙
www.acmicpc.net/problem/19640 19640번: 화장실의 규칙 위와 같이 줄을 선 경우를 생각해보자. (x, y) 는 사원의 근무 일수가 x, 화장실이 급한 정도가 y임을 나타낸다. [x, y]는 해당 사원이 데카임을 의미한다. 즉, 위의 그림에서 데카는 3번 사원이다. www.acmicpc.net 1. 유형 우선순위큐 2. 풀이 우선순위큐에 들어갈 클래스를 만든다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Que..
→2020.11.28
알고리즘/백준
[백준 - 2841] 실버2- 외계인의 기타 연주
www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 1. 유형 스택 2. 풀이 위의 조건 처럼 입력을 받을때 기존의 스택의 peek()보다 더큰 플랫을 입력 받을 경우 추가를 해준다. 하지만 더 작은 플랫을 입력 받을 시, 스택에서 입력값보다 더 큰 플랫이 나올 때까지 pop을 해야한다. 위와 같은 경우가 나오면 3, 2를 빼고 마지막에 1은 이미 존재 하기 때문에 push를 하면 안된다 그렇기 때문에 while문을 빠져나..
→2020.11.27
알고리즘/백준
[백준 - 1238] 골드3 - 파티
www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. 유형 다익스트라, 그래프 2. 풀이 1) 모든 점에서 다익스트라를 돌려서 X까지의 거리를 구한다. 2) X에서 다익스트라를 돌려서 각 마을까지의 최단거리를 구한다. 3) X까지 간거리와 본인 마을로 돌아온 거리를 더한 후, 최대값을 구한다 자료구조: 인접리스트, 우선순위큐 인접리스트 구한다 우선순위큐 사용을 위해 클래스 구현 X마을 까지의 최단거리를 구한다 3. 코드 pack..
→2020.11.14
알고리즘/백준
[백준 - 14698] 골드4 - 전생했더니 슬라임 연구자였던 건에 대하여(Hard)
www.acmicpc.net/problem/14698 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net 1. 유형 그리디, 우선순위큐 2. 풀이 문제에서 요구하는 값이 가장 작으려면 매 상황마다 가장 작은 슬라임 2개를 합성하면 가장 작은 결과를 얻는게 가능하다. 이때 사용하는 자료구조가 우선순위큐이다. 문제에서 가장 어려운 부분은 숫자의 범위 초과이다. 아래처럼 mod연산을 통해서 long타입을 넘길거 같으면 나머지 연산을 해야한다. java를 쓰면 시간초과가 날 수 있..
→2020.11.12
알고리즘/백준
[백준 - 15922] 골드5 - 아우으 우아으이야!!
1. 유형 구현 2. 풀이 visit배열을 써서 방문한 곳과 방문 안 한 곳을 나눠서 풀 수도 있지만, 그랬다간 시간초과가 날것이다. 때문에 가능한 경우를 나누어서 생각 해야한다. 아래처럼 나오는 숫자가 3가지의 경우가 있다. 즉, 겹치는 부분이 있기때문에 끝 점을 계속 갱신 하면서, (끝점 - 처음점)을 빼는 식으로 총 길이를 구해야 한다. 3. 코드 package 구현; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Beak_15922아우으우아으이야 { public static void main(St..
→2020.11.10
알고리즘/백준
[백준 - 2931] 골드3 - 가스관 (구현)
1. 유형 구현, dfs 2. 풀이 1) M부터 4방 탐색 2) 가스관 별로 방향을 바꾼다 3) '.' 이 나왔을 때, 7가지의 가스관을 다 넣어본다 4) 탐색한 가스관의 갯수가 필요한 가스관의 수하고 같다면 종료한다 M부터 4방향을 탐색해서 시작 방향을 정한다. 현재 좌표에서 가스관의 종류별로 방향을 바꿔줘야 한다. 다음 좌표가 '.'이면 7가지의 가스관을 넣어서 완전 탐색한다 예외적으로 생각해야할 점은, 밑에 파란색 칸은 두번 세어주면 안된다. 그렇기 때문에 아래와 같은 코드가 필요하다. 방문한 지점이라면 cnt증가가 없다. 미방문 지점은 cnt+1을 한다 3. 코드 package 구현; import java.io.BufferedReader; import java.io.IOException; impo..
→2020.11.08
알고리즘/백준
[백준 - 17281] 골드4 - ⚾ (구현)
1. 유형 구현, 순열 2. 풀이 타자의 순서를 정해줘야 한다. 그러기 위해서 순열을 이용한다. 9번째의 타자의 순서를 정해줄 때, 1번 선수는 무조건 4번째에 놓아야한다. 그러기 위해 아래 네모칸 코드를 넣어줬다. 게임을 진행 할때의 예외 처리는, 9번 타자까지 다 쳤을때, 다시 1번 타자로 넘어와야한다 그리고 아웃이 3번인 경우 베이스를 초기화 하고, out카운트를 0으로 만든다. 베이스를 끝 부터 탐색해서, 몇루타를 쳤는지 만큼 뛴다. 베이스는 3번까지만 있으니깐 3번을 초과하면 arr[4]에 초과한 횟수를 저장한다. 베이스를 3번부터 0번까지 탐색후 arr[4]에 저장된 값이, 방금 선수의 득점이 된다. 예를들어서 초기 베이스가 아래의 상태였다면, 위에서 2루타를 쳤다면 아래처럼 베이스가 그려지는..
→2020.11.07
알고리즘/백준
[백준 - 15685] 골드4 - 드래곤 커브
1. 유형 그리디, 시뮬레이션 2. 풀이법 예를 들어서 0 1 2 1 방향으로 움직일 때, 다음 세대의 방향은 전 방향(0 1 2 1) + (2 3 2 1)가 된다 2 3 2 1 구하는 방법은 0 1 2 1의 끝부터 반대방향-1을 해주면 된다 1 -> 3(반대방향) -> 2(-1을 해줌) 2 -> 0(반대방향) -> 3(-1을 해줌, -1은 3으로 치환) 이런 식으로 시뮬레이션을 돌린다. 아래는 이와 관련된 코드이다 그런 다음 visit 배열에 방문 처리를 한다음 4개의 꼭지점이 true인 것의 갯수를 세주면 된다. 3. 코드 package 삼성역태; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..
→2020.11.07
알고리즘/백준
[백준 - 2457] 골드4 - 공주님의 정원(그리디)
www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1
→2020.11.01
알고리즘/백준
[백준 - 1276] 골드5 - 교각 놓기
www.acmicpc.net/problem/1276 1276번: 교각 놓기 첫째 줄에 다리의 개수를 나타내는 정수 N(1≤N≤100)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 다리의 위치를 나타내는 세 정수 Y, X1, X2가 주어지는 이는 (X1, Y)부터 (X2, Y)까지 다리가 놓여 www.acmicpc.net 1. 유형 그리디, 정렬 2. 풀이 입력값 전처리 높이가 낮은 순으로 우선순위 정렬 메모리제이션 전처리 과정 문제를 풀기 위해서 입력값을 한번 전처리 과정을 거쳐야 합니다. 1 5 10 값이 들어오면 배열의 index로는 5 ~ 9 까지만 차지합니다 3 1 5 값이 들어오면 index로는 1 ~ 4 까지만 들어옵니다. 즉, 입력값을 배열로 전처리 하고 싶으면 끝값(10, 5 등....
→2020.10.31
알고리즘/백준
[백준 - 17828] 골드5 - 문자열 화폐 (그리디)
www.acmicpc.net/problem/17828 17828번: 문자열 화폐 첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다. www.acmicpc.net 1. 유형 그리디 2. 풀이 배열을 전부다 A로 초기화 한다 끝부터 탐색하며 25보다 값이 크면 빼주면서 초기화 java로 풀 경우 시간이 타이트 해서, StringBuilder를 사용해서 출력 시간을 줄여야 한다. 3. 코드 package 그리디; import java.util.Scanner; public class back_17828문자열화폐 { public static void main(String[] args) { Sca..
→2020.10.30
알고리즘/백준
[백준 - 14711] 골드4 - 타일 뒤집기( easy) (문자열)
www.acmicpc.net/problem/14711 14711번: 타일 뒤집기 (Easy) 지구이는 신기한 게임판을 가지고 있다. 이 게임판에는 한 면은 검은색, 한 면은 흰색으로 칠해진 타일이 N행 N열으로 배치되어 있다. 각 타일은 제자리에서 뒤집을 수 있는데, 타일 하나를 뒤집 www.acmicpc.net 1. 유형 문자열 2. 풀이 검은색을 뒤집을때 오른쪽, 왼쪽, 아래쪽을 뒤집어야 한다. 이때 뒤집은 횟수를 check배열에 저장한다 check배열을 탐색하면서 값이 홀수이면 칸을 바꾸고, 짝수이면 칸을 뒤집지 않는다 java로 풀 경우 입출력에 시간을 많이 써서 시간초과가 난다. 이때 BufferdReader와 StringBuilder를 써야한다. 3. 코드 package 문자열; import ..
→2020.10.29
알고리즘/백준
[백준 - 2638] 골드4 - 치즈 (bfs)
www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 1. 유형 bfs 2. 풀이 왼쪽 귀퉁이 부터 시작해서 bfs를 돌린다. 1인 부분을 만나면 check배열을 1 증가 시킨다 bfs가 끝난 후, check배열에서 값이 2 이상이면 map을 갱신한다. 3. 코드 package bfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; im..
→2020.10.29
알고리즘/백준
[백준 - 3190] 골드5 - 뱀
www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 1. 유형 시뮬 2. 풀이 리스트를 사용해서 머리부분은 인덱스가 끝 부분이고, 꼬리는 인덱스가 0 일 때이다. 방향은 시계방향과 반시계 방향을 구분해서 결정한다. 3. 코드 package 구현.삼성역태; import java.util.ArrayList; import java.util.Scanner; public class back_3190뱀 { static int dr[] = {-1,0,1,0}; static int ..
→2020.10.29
알고리즘/백준
[백준 - 14890] 골드3 - 경사로
www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 1. 유형 시뮬 2. 풀이 완전탐색을 할 때, 몇가지 예외를 생각해야한다. 평평한 경우 오르막길 내리막길 이 3가지 경우를 구현해야 한다 이걸 구분하기 위해 plat 변수를 핸들링한다. 3. 코드 package 구현.삼성역태; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringT..
→2020.10.29

• 이전
• 1
• ···
• 3
• 4
• 5
• 6
• 7
• 8
• 다음