알고리즘 풀이
-
백준(BOJ) 1806번 부분합알고리즘 풀이/백준(Boj) 2020. 4. 15. 03:07
문제 : https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net 풀이 : 완전 탐색을 이용 시 n이 크기에 시간 내에 처리하지 못하고 투 포인터를 이용해서 처리해보자 lo와 hi는 인덱스를 가리..
-
백준(BOJ) 1022번 소용돌이 예쁘게 출력하기알고리즘 풀이/백준(Boj) 2020. 4. 14. 12:40
문제 : https://www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 r1, c1, r2, c2가 주어진다. 모두 절댓값이 5000보다 작거나 같은 정수이고, r2-r1은 0보다 크거나 같고, 49보다 작거나 같으며, c2-c1은 0보다 크거나 같고, 4보다 작거나 같다. www.acmicpc.net 풀이 : 1.r2-r1은 0보다 크거나 같고, 49보다 작거나 같으며, c2-c1은 0보다 크거나 같고, 4보다 작거나 같으니 board배열은 [50][5]로 처리하자. 2.while문은 네 꼭짓점이 모두 0이 아닐 때까지 계속된다. 3. y 에다 r1를 빼고 x에다 c1을 뺀 것을 처음 값으로 두자. 예제와 같이 (0-(-3), 0-(-3))으로 (3,..
-
프로그래머스 - 종이접기알고리즘 풀이/프로그래머스 2020. 4. 11. 19:13
문제 : https://programmers.co.kr/learn/courses/30/lessons/62049 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 : 종이를 반으로 접기 때문에 n이 증가할수록 (n-1)은 그대로 쓰이게 되고 ( 왼쪽 ) 반으로 접기 때문에 가운데 부분에 0이 생기고 (가운데) 데칼코마니 형태로 오른쪽이 생기기 때문에 이전 종이(n-1)를 접었던 것에 순서를 뒤집고 1은 0으로 0은 1로 바꾸어서 처리해주었다. ( 오른쪽 ) 코드 ( C++ )
-
백준(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) 1726번 로봇알고리즘 풀이/백준(Boj) 2020. 4. 8. 17:14
문제 : https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다. 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다. 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다. 공장 내 궤도가 설치되 www.acmicpc.net 풀이: BFS를 통해 처음 부분과 좌표를 넣은 후에 1,2,3만큼 가는 경우와 방향을 바꾸는 경우를 큐에 넣어주어야 한다. 이때 주..
-
백준(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()를 돌린다..