개발자 지망생의 끄적끄적 개발기록

백준 13460번 : 구슬 탈출 2 등급 : Gold I 13460번: 구슬 탈출 2 (acmicpc.net) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 사용 알고리즘 : BFS 사용 자료구조 : Vector, Queue BFS를 이용해 최단 거리, 4차원 Visit 배열(빨간 공, 파란 공 각각의 좌표)을 이용하여 해결. 고려해야 할 요인이 꽤 많은 문제였다. 공이 굴러간 위치를 어떻게 지정할까 고민하다 같이 끝까지 굴리고 이후에 겹칠 경우 위치를 다시 ..

백준 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..

KMP 알고리즘 (Knuth-Morris-Pratt Algorithm) KMP 알고리즘 (수행시간 : O(N)) : 문자열 탐색에 있어 겹치는 부분을 미리 탐색해 불필요한 검색을 하지 않도록 점프시키는 알고리즘. 일반적인 문자열 탐색 알고리즘을 사용하는 경우, 글의 길이가 M, 패턴의 길이가 N이라고 하면 수행시간은 O(MN)이 된다. 이때 어떻게 하면 이러한 중복 문자열 탐색을 줄일 수 있을까 하여 나온 방법이 KMP 알고리즘이다. 수행 원리 문자열을 탐색할 때 겹치는 부분이 있는데, 일반적인 탐색의 경우 이를 무시하고 다시 처음부터 탐색을 진행하게 된다. KMP는 미리 탐색한 이러한 겹치는 문자열을 어떻게 활용할지를 고안하여 만들어낸 알고리즘이다. 우리는 접두사(Prefix)와 접미사(Suffix)의..

백준 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..