티스토리

JJUN_0

검색하기

블로그 홈

JJUN_0

dlwnsdud205.tistory.com/m

https://medium.com/@develxb

구독자: 19

방명록 방문하기

주요 글 목록

[백준 / BOJ] 2310 어드벤처 게임 (Rust) 문제 출처 : https://www.acmicpc.net/problem/2310 2310번: 어드벤처 게임 입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타 www.acmicpc.net 1부터 n까지의 번호가 붙은 방이 있다. 각 방은 E,L,T로 이루어져 있는데, 각각이 의미는 아래와 같다. E : 비어있는 방 -> 아무런 동작도 하지 않음. L : 레프리컨의 방 -> 이 방에 진입했을때, 내가 갖고있는돈이 방의 돈 보다 작다면, 방의 돈으로 내 돈이 맞춰짐. T : 트롤의 방 -> 이 방에 진입하려면, 이 방의 돈 만큼 내가 돈을 갖고있어야 한다.. 공감수 0 댓글수 1 2023. 4. 30.
[백준 / BOJ] 2251 물통 (cpp) 문제 출처 : https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 각각 부피가 A, B, C인 물통이 있고 A, B는 비어있으며 C는 꽉 차있다. 물을 이동 시킬때는 항상 하나의 물통이 꽉차거나 빌때까지만 옮길 수 있다. 이때, 물통 A가 비어있을때, 물통 C에 있을수 있는 물의 양을 모두 구하는 문제다. 풀이 DFS로 풀어도 풀리는 문제다. A, B, C의 최대 용량이 각각 200이므로, 3차원 체크 배열로 이미 방문한 상태를.. 공감수 0 댓글수 0 2023. 2. 10.
[백준 / BOJ] 18809 Gaaaaaaaaaarden (Java) 문제 출처 : https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net N*M크기의 정원에 빨간색 배양액 R개 초록색 배양액 G개를 뿌린다. 배양액을 뿌릴 수 있는 위치는 R+G곳 이며, 배양액을 뿌린 위치는 매 초마다 인접한 영역으로 퍼져나간다. 서로 다른 색의 배양액이 동시에 만나면 꽃이 피며, 배양액은 사라진다. 이때, 피울 수 있는 최대 꽃의 개수를 구하는 문제다 풀이 조합과 BFS로 풀.. 공감수 0 댓글수 0 2022. 6. 3.
[백준 / BOJ] 14442 벽 부수고 이동하기 2 (Java) 문제 출처 : https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net N*M크기의 맵이 있고, 이 맵은 벽과 땅으로 이루어져있다. 벽을 부술수있는 횟수 K가 주어질때, K번 이하로 벽을 부수면서 (N,K)지점에 도착하는 최소 거리를 구하는 문제다. 풀이 BFS에 3차원 체크배열로 재방문을 잡아내며푸는 문제였다. 체크배열을 3차원으로 지정해야하는 이유는, (y,x)지점에 도달했을때, 벽을 A+1번 부순횟수보다 A번 부.. 공감수 0 댓글수 0 2022. 5. 15.
[백준 / BOJ] 1765 닭싸움 팀 정하기 (Java) 문제 출처 : https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net n명의 학생, m개의 학생들 사이의 관계가 주어졌을때, n명의 학생들로 최대 몇개의 팀을 만들수있는지 알아내는 프로그램을 만드는 문제다. 풀이 문제 해석이 정말 어려운 문제였다. 문제에서 인간관계를 다음과 같이 정리할 수 있다고 한다. 내 친구의 친구는 내 친구이다. 내 원수의 원수도 내 친구이다. 처음에 이걸보고 가능한 인간관계 경우의 수를 다음과 같이 생각했다.(재귀적으로) 내 친구의 친구는 내 친구이다. 내 친구의 원수의 원수는 내 친구이다. 내 친구.. 공감수 0 댓글수 0 2021. 8. 30.
[백준 / BOJ] 5827 What's Up With Gravity 문제 출처 : https://www.acmicpc.net/problem/5827 5827번: What's Up With Gravity Output Details The captain starts at position (4, 2). She flips gravity and falls to position (2, 2) and then moves right twice to arrive at (2, 4). She flips gravity again and falls to position (4, 4) and then moves right once to position (4, 5). Finally www.acmicpc.net 캡틴 보비디안은 그녀의 선원 닥터 비팔로를 찾으러 모험을떠난다. 캡틴 보비디안이 도착한 세계.. 공감수 0 댓글수 0 2021. 5. 14.
[백준 / BOJ] 14466 소가 길을 건너간 이유 6 (Java) 문제 출처 : https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net N*N그리드에 K마리의 소가있고, R개의 길이있다. 각 소들이 상하좌우로 움직일수있을때, 길을 건너지않고 만날수없는 소들의 쌍을 구하는 문제다. 풀이 알고리즘 보다는, 문제 해석과 적절한 자료구조를 생각해 내는게 핵심인 문제였다. 처음에 문제를 봤을때 문제가 무엇을 원하는지 파악을 못했는데, 문제를 쉽게 축약해보면, "길을 지나가지않고는 서.. 공감수 0 댓글수 0 2021. 5. 12.
[백준 / BOJ] 2644 촌수계산 (Java) 문제 출처 : https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 입력받은 두 사람의 촌수를 계산하는 문제다. 풀이 매우 기초적인 그래프 문제다. 연결거리가 1 늘어날수록 촌수또한 1 늘어난다. 깊이우선탐색으로 입력받은 사람의 촌수를 계산해주면된다. (이때, 자손은 항상 한명의 부모만 가질수있으므로, 이 그래프는 항상 트리구조이다.) 소스코드 https://github.com/devxb/JJUNalgo/blob/master/2644%.. 공감수 0 댓글수 0 2021. 5. 2.
[백준 / BOJ] 1039 교환 문제 출처 : https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 0으로 시작하지않는 정수 N이 주어진다. 정수 N의 자릿수 M에 대해 다음과 같은 연산을 K번 수행했을때, 나올수있는 최댓값을 계산하는 프로그램이다. 1 13 -> 31 과 같은 루트로 이동해 최댓값을 찾을수도 있기때문이다. 따라서, 체크배열을 map check; 와 같이 선언한다. (cnt번 이동해서 vector 형태가 되었을때, 이동횟수) 위 정보들을 갖고 구현하면된다. -1 출력은 1. N이 한자릿수 인경우 2. N이 두자릿수면서 일의자리가 0인경.. 공감수 0 댓글수 0 2021. 4. 20.
[백준 / BOJ] 14502 연구소 문제 출처 : www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net N*M그리드가 주어지고, 그리드의 상태가 주어진다. 0 : 빈칸 1 : 벽 2 : 바이러스 바이러스는 매초 상하좌우 빈칸으로 확산될수있다. 바이러스가 모두 확산된후 남아있는 빈칸의 수를 안전영역이라 한다. N*M그리드에 벽 3개를 적절히 설치했을때, 안전영역의 최대 크기를 구하는 문제다. 풀이 N과 M의 범위가 크지않아, 완전탐색으로 풀리는문제다. 시간복잡도는 1. N*M그리드 에서 3개의 빈칸을 선택하는 경.. 공감수 0 댓글수 0 2021. 1. 21.
[백준 / BOJ] 16953 A -> B 문제 출처 : www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 정수 A와 B가 주어진다. A에 *2연산과, A*10+1연산을 할수있을때, A를 B로 바꾸는데 필요한 최소연산횟수를 구하는 문제다. 이때, A를 B로 바꾸지 못한다면, -1을 출력하면 된다. 풀이 전형적인 BFS문제다. BFS알고리즘은 자기와 가까운 위치부터 탐색하기때문에, 항상 최소연산으로 A를 B로 바꿀수있다. A와 B의 범위가 최대 10억이기때문에, check배열로는 같은숫자방문을 체크해줄수없다. 하지만, 연산의 증가폭이 넓기때문에, 모든경우를 다 봐줘도 시간초과가 나지않는다. 예시로, 1. *2 연산은 32번만 반.. 공감수 0 댓글수 0 2021. 1. 17.
[백준 / BOJ] 16724 피리 부는 사나이 문제 출처 : www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net N*M지도가 있고, 그 위에 영과일 회원들이 있다. 지도의 각 칸에는 U,D,L,R 이 쓰여있는데, (순서대로 위, 아래, 왼쪽, 오른쪽) 성우가 피리를 불기 시작하면, 영과일 회원은 자기 발 아래의 방향에 맞게 이동한다. 재훈이는 영과일 회원의 안전을 위해 SAFE ZONE을 설치할려고한다. 영과일 회원이 어디에 있던지 항상 SAFE ZONE으로 들어갈수있도록.. 공감수 0 댓글수 1 2021. 1. 6.
[백준 / BOJ] 2342 Dance Dance Revolution 문제 출처 : www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 승환이는 DDR게임을 할려고한다. 중앙, 위, 왼쪽, 아래, 오른쪽 순서로 0, 1, 2, 3, 4 라고 할때, 승환이가 눌러야할 방향이 순서대로 주어진다. 한 위치에서 다른 위치로 발을 이동시킬때드는 힘의 크기가 다를때, 모든 방향을 누를때 드는 최소힘의 크기를 구하는 문제다. 풀이 BFS나 DP로 풀리는 문제다. 왼쪽발을 움직여서 해당 숫자를 누르는게 당장은 .. 공감수 0 댓글수 0 2021. 1. 5.
[백준 / BOJ] 12852 1로 만들기 2 문제 출처 : www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 숫자 N이 주어졌을때, 1. 나누기 2 2. 나누기 3 3. 빼기 1 을 적절히 사용하여 최소한의 연산으로 1을 만드는 문제다. 풀이 너비우선 탐색이기때문에, 항상 최소경로가 가장 먼저나오는 BFS를 사용해 최소 연산을 찾아주면된다. 경로는, 의 check배열에 {연산횟수, 이전 숫자}형태로 저장해준다. 이전숫자가 없을경우(처음숫자) 이전숫자 위치에 -1을 저장해놓는다. (연산횟수보다 작은 연산횟수가 나오지않는다면 check배열이 업데이트 되지않으므로 항상 성립한다) 배열을 따라 1부터 올라가며 경로를.. 공감수 0 댓글수 0 2021. 1. 3.
[백준 / BOJ] 17071 숨바꼭질 5 (1~5) 문제 출처 : www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이 문제는 다른 숨바꼭질 문제들과는 달리, 동생이 매 시간마다 +1 +2 +3 +4 +5 ... 의 속력으로 앞으로 질주한다. 이때, 수빈이가 동생을 찾는 가장 빠른 시간을 출력하는 문제다. 풀이 BFS로 풀리는 문제다. 우선 BFS로 수빈이가 해당 정점에 도달하는 최솟값들을 전부 갱신해주고 동생을 움직이며, 서로가 만날수있는지 봐줬다. (동생이 수빈이를 찾는.. 공감수 0 댓글수 0 2020. 12. 28.
[백준 / BOJ] 5427 불 문제 출처 : www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 상근이가 빌딩을 탈출하려고한다. 이때, 벽이있는곳이나 불이 붙은곳으로는 이동할수없다. 불은 1초마다 상하좌우로 번지며 벽으로는 번지지못한다. 상근이는 1초마다 상하좌우로 움직이며, 벽으로 이동하지 못한다. 가장빠르게 빌딩 밖으로 나가는 경우를 찾는 문제다. 풀이 BFS두번으로 풀리는 구현문제였다. 1. 우선, 불의 위치를 전부 저장해놓은다음, 각각의 위치를 기준으로 BFS를 돌린다. 이때 해당(y,x)지점에 .. 공감수 0 댓글수 0 2020. 11. 23.
[백준 / BOJ] 1405미친로봇 문제 출처 : www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자�� www.acmicpc.net 로봇이 동, 서, 남, 북 4방향으로 N번 이동한다. N번 이동했을때, 방문한 지점을 한번 더 방문했다면 경로가 복잡하다고 하고, 아니라면 경로가 간단하다고 한다. 각 방향에 대한 확률과 이동하는 횟수가 주어졌을때, 로봇의 이동경로가 간단할 확률을 구하는 문제다. 풀이 DFS와 백트래킹으로 풀었다. 처음에는 입력받은 동, 서, 남, 북 만큼 전부 저장해주고 (25 25 25 25를 입력받으.. 공감수 0 댓글수 0 2020. 10. 7.
[백준 / BOJ] 6146 신아를 만나러 문제 출처 : www.acmicpc.net/problem/6146 6146번: 신아를 만나러 키파는 신아를 만나러 아침 일찍(무려 6시에!) 일어났다. 간밤에 거센 비가 내려서 새로 산 장화를 신고 (0, 0)에 있는 집을 나선 키파는 무려 N(1 ≤ N ≤ 104)개의 웅덩이가 있는 것을 보고 놀랐다. www.acmicpc.net 키파는 신아에게 가야한다. 키파와 신아 사이에는 웅덩이가있고, 키파는 웅덩이를 피해서 가야한다.(키파가 신아에게 못가는경우는없다.) 키파의 위치는 항상 (0,0이고) 신아는 (-500~500, -500~500) 사이에 있다 키파는 상하좌우로만 움직일수있다. 풀이 BFS로 풀리는 문제였다. -500~500까지 가능하므로 전체 칸의 갯수는 1000 * 1000 = 1000000개.. 공감수 0 댓글수 0 2020. 9. 25.
[백준 / BOJ] 13931 숨바꼭질 4 문제 출처 : www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 수빈이와 동생은 숨바꼭질을 한다. 수빈는 자신의 위치에서 -1, +1, *2만큼 이동할수있다. 수빈이가 동생을 가장빨리 찾는 시간을 구하는 문제다. 풀이 BFS를 통해 푸는 문제였다. 배열을 이용해 자신의 전 위치를 체크해줘야하는데, 예를들어, 배열이 par[100005]로 선언되어있고 수빈이가 동생에게 가는 경로가 5 10 20 40 이라면, par[40].. 공감수 0 댓글수 0 2020. 9. 9.
[백준 / BOJ] 1194 달이 차오른다, 가자. 제목 출처 : www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 민식이는 달이 차오르는 기회를 놓치지 않기 위해서 미로를 탈출하려고 한다. 한번 움직일때마다 수평 혹은 수직으로 한칸 움직일수있다. 민식이가 미로를 탈출하는데 걸리는 최소한의 이동횟수를 구하는 문제다. 미로에는 문이있고, 미로는 다음과 같이 구성되어있다. 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨) 벽 : 절대 이동할 수 없다. (‘#’) 열쇠 : 언제나 .. 공감수 0 댓글수 0 2020. 9. 6.
[백준 / BOJ] 1113 수영장 만들기 문제 출처 : www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net N*M크기의 칸에 수영장을 만들려고 한다. 각 칸에 그 땅이 갖고있는 높이가 주어졌을때, 수영장에 물을 얼만큼 넣을수있는지 구하는 문제이다. 만약 수영장이 다음과 같다면, 16661 61116 16661 가운데 3개의칸에 5씩 넣어서 총 15만큼의 물을 넣을수있다. 만약 5보다 더 많이 넣는다면 수영장 벽의 높이인 6보다 커져서 물이 넘친다. 풀이 한달전에 풀었던 문제였다... 공감수 0 댓글수 0 2020. 8. 28.
[백준 / BOJ] 2206 벽 부수고 이동하기 문제 출처 : www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net N*M행렬이 주어진다. 이때, 이동할수있는곳은 0 벽이있어서 이동할수 없는곳은 1로 표시된다. 이동할때 벽을 최대 1회 부수고 이동할수있는데, 1,1에서 시작해서 N,M에 도달했을때 최단경로를 구하는 문제다. 풀이 BFS문제다. 일반적인 BFS와 check배열을 선언하는게 다른데, 3차원 체크배열을 선언해서 해당 지점에 벽을 부수고 이동한 경로와 최솟값과 벽을 부수지 .. 공감수 0 댓글수 0 2020. 8. 27.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.