백준
-
백준(BOJ) 16638번 괄호 추가하기 2알고리즘 풀이/백준(Boj) 2020. 4. 9. 15:26
문제 : https://www.acmicpc.net/problem/16638 16638번: 괄호 추가하기 2 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계산 해야 한다. 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 41이다. 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, www.acmicpc.net 풀이 : 기존 괄호 추가하기 문제는 단순히 해당하는 괄호 연산 (A 연산자 B) 를 ( A 연산자 B + 0 ) 의..
-
백준(BOJ) 11559번 Puyo Puyo알고리즘 풀이/백준(Boj) 2020. 4. 8. 17:05
문제 : https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 풀이 : 1.BFS를 통해 4 이상이 되는 모든 알파벳들은 v 배열에 담아주게 되고 '.'을 만든다. 2. 알파벳들을 밑으로 내리고 내릴 알파벳이 없다면 종료하고 있다면 1. 을 반복한다. 코드(C ++)
-
백준(BOJ) 17142번 연구소 3알고리즘 풀이/백준(Boj) 2020. 3. 31. 15:51
문제 : https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net 풀이 : cand배열에는 2인 바이러스들을 모두 저장한다. cand배열 중 m개만큼 picked에 담고 bfs()를 돌린다..
-
백준(BOJ) 18809번 Gaaaaaaaaaarden알고리즘 풀이/백준(Boj) 2020. 3. 28. 17:49
문제 : https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두고 주어진다. 그 다음 N개의 줄에는 각 줄마다 정원의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양 www.acmicpc.net 풀이 : loc 배열에는 0과 g에 개수만큼 1이, r에 개수만큼 2가 들어있다. 이 loc 배열을 ne..
-
백준(BOJ) 18808번 스티커 붙이기알고리즘 풀이/백준(Boj) 2020. 3. 28. 17:36
문제 : https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다. 아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다. 반면 아래는 올바 www.acmicpc.net 풀이 : 색종이는 붙일 곳이 없다고 해서 바로 return 하지 않고 일단 색종이를 붙이고 중복된 곳이 있게 된다면 다..
-
백준 BOJ(16637번) 괄호 추가하기알고리즘 풀이/백준(Boj) 2020. 3. 21. 17:06
문제 : https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다. www.acmicpc.net 풀이 : 홀수인 부분은 모두 부호이니 +면 1 *면 2 -면 3으로 바꿔서 풀어주었다. 비트 마스킹을 통해 첫 번째 예제를 예로 들면 index가 1 , 3, 5, 7, 13, 15, 17, 35, 37, 57,..
-
백준 BOJ(1445) 일요일 아침의 데이트알고리즘 풀이/백준(Boj) 2020. 3. 19. 00:45
문제: https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있다. S는 반드시 모서리에 위치해 있고, F는 모서리에 위치해있지 않다. 그리고 S와 F는 반드시 하나만 주어진다. www.acmicpc.net 풀이: 우선 주의할점은 '만약 어떤 칸이 비어있는데, 인접한 칸에 쓰레기가 있으면 쓰레기 옆을 지나는 것이다' 이 부분이다. 칸이 비어있는 경우에만 인접한 칸에 쓰레기를 검사해야 한다. priority queue를 이용해서 { 밟은 쓰레기, 인접 쓰..