Gi-Log

문제 링크: https://www.acmicpc.net/problem/9342 9342번: 염색체 상근이는 생명과학 연구소에서 염색체가 특정한 패턴인지를 확인하는 일을 하고 있다. 염색체는 알파벳 대문자 (A, B, C, ..., Z)로만 이루어진 문자열이다. 상근이는 각 염색체가 다음과 같은 규칙 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 구현 및 정규식 어떤 문자열이 입력되었을 때 일련의 규칙을 만족하는 문자열인지 파악하기 위해, 다량의 if-else문으로 문제를 풀이했다. 문자열의 인덱스 0부터 하나씩 증가시키며, 특히 중간에 A, F, C 등이 1개 이상 등장할 수 있을 때는 새로운 문자가 등장할 때까지 인덱스를 증가시키고, 새롭게 등장한 그 문자가 규칙에 맞는 지 확인하는 방식으..

문제 링크: https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 단순 구현 주어진 단어가 그룹 단어인지 체크하는 것이 목적이다. 그룹 단어인 지 파악하기 위해서, 단어 내에서 어떤 철자가 등장한 적이 있는 지를 visited 배열에 기록한다. 단어를 한 글자씩 뜯어보며, 이미 한 번 등장했던 철자가 다시 등장했는데, 이전 철자와의 연속성이 없다면 그룹 단어가 아닌 것으로 판단한다. 문제..

문제 링크: https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 이진 탐색, 파라메트릭 서치 주어진 상황에서 가장 최적의 값을 고르는 문제이므로, 아직 실력이 부족한 나는... 탐욕법을 떠올렸다. 하지만 입력의 크기를 보아하니, 탐색의 범위가 굉장히 크다는 점과 결국 확인해야할 것은 "1회 인출 시 금액"으로 1번째 날부터 n번째 날까지 생활이 가능한 지, 불가능한 지 결정하는 문제 같다고 생각하여 이진 탐색으로 접근하기로..

문제 링크 : https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 모든 행성 간에 플로우를 설치하고 싶지만, 플로우를 설치할 때 사용되는 군대 주둔 비용이 비싸서, 가장 효율적으로 플로우를 설치해야 하는 문제이다. 개인적으로 이런 그래프에서 효율성이나 일의 순서를 파악하는 문제를 보면, 신장 트리와 위상 정렬을 떠올린다. 효율성과 관련된 것은 최소 신장 트리(MST), 일이나 작업 순서를 파악해야하는 문제는 위상 정렬을 이용하며 현재 문제는 최소 ..