백준 2110번 : 공유기 설치 등급 : Gold III 2473번: 세 용액 (acmicpc.net) 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 사용 알고리즘 : Two_Pointer 사용 자료구조 : Vector 시작값 하나를 고정하고, 나머지는 기존과 같은 투 포인터를 이용한 풀이. 이외에는 본래 투 포인터와 동일하다. #include #include #include using namespace std; #define INF 2e18 #define ll long long vec..
[백준] 14500번 : 테트로미노 - C++
백준 14500번 : 테트로미노 등급 : Gold IV 14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 사용 알고리즘 : Brute-Force, DFS, Backtracking 사용 자료구조 : Vector DFS와 백트래킹, 그리고 예외 케이스에 대한 탐색으로 구현할 수 있다. 위의 사진을 보았을 때, 테트로미노의 5개의 도형 중 마지막 도형만 제외하면 모두 DFS로 탐색이 가능하다. 즉, 5번째 도형 = 예외 케이스. 이 부분만 유의하면 어렵지 않게 구현이 ..
백준 3020번 : 개똥벌레 등급 : Gold V 3020번: 개똥벌레 (acmicpc.net) 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 사용 알고리즘 : - 사용 자료구조 : Vector 이분 탐색이라고 쓰여있지만 딱히 이분 탐색 알고리즘을 사용하지 않아도 되는 문제이다. 첫 접근은 이중 for문으로 각 자리를 계산하는 방식으로 진행하였다. → TLE 때문에 석순과 종유석의 벡터를 각각 구현해주고, 각각의 for문을 누적 합으로 구현했다. Top vector : 종유석 지정 벡터. Bottom vecto..
백준 2110번 : 공유기 설치 등급 : Gold IV 2110번: 공유기 설치 (acmicpc.net) 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 사용 알고리즘 : Binary_Search 사용 자료구조 : Vector 이분탐색의 활용 방법과 이해도를 높여줄 수 있는 문제라고 생각한다. 인접한 두 공유기 사이의 거리를 이분 탐색으로 점점 줄여나가며 탐색하는 문제. Left 지정 : 같은 지점에 공유기가 있을 순 없으므로, 두 공유기 사이의 최소 거리인..
백준 11559번 : Puyo Puyo 등급 : Gold IV 11559번: Puyo Puyo (acmicpc.net) 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 사용 알고리즘 : DFS 사용 자료구조 : Vector, Deque 백준 페이지에는 알고리즘 분류에 BFS로 나와있는 것을 보아 BFS 구현을 권장하는 것 같은데, DFS로 구현하는 방법이 먼저 떠올라 이대로 진행했다. 입력은 12×6의 이차원 행렬로 받는데, 블럭이 깨졌을 때 남은 블럭들이 아래로 내려가는 것을 보아 배..