문제 https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 접근 방법 무작정 구현을 시작했는데 해결하지 못했다. 이후 검색을 해보며 힌트를 얻었다. 비트마스킹을 이용한 풀이방법밖에 찾지 못했다. 나는 비트마스킹을 잘 모르기에 비트마스킹을 사용하지 않고 그냥 빡세게 구현했다. 원리는 이렇다. 같은 스위치를 여러 번 누르지 않는다. 같은 행위를 반복하면 최적의 해를 구할 수 없다. 완전 탐색으로 100개의 전구를 켜고 끄는 경우를 찾으면 O(..
문제 https://www.acmicpc.net/problem/2671 2671번: 잠수함식별 입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고 www.acmicpc.net 접근 방법 비슷한 유형의 문제를 풀었던 기억이 있다. 처음에는 무지성으로 구현을 시도했고 실패했다. 이후 나름의 규칙으로 구현을 시도했으나 실패했다. 마지막으로, 이전에 정규식을 이용했던 것이 생각나 적용했더니 너무 간단하게 풀렸다. 풀이 문자열.matches() 내장 함수를 사용한다. matches의 인자로 정규식을 넣는다. "(100+1+|01)+"를 사용했다. A+ "반복"을 표현하며 ..
문제 1802번: 종이 접기 1802번: 종이 접기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1 www.acmicpc.net 접근 방법 분할 정복 문제 모음집을 따라 풀던 중 만난 문제다. 인덱스를 잘 구분하면 쉬운 문제다. 중간 값은 어느 방향으로 접어도 상관이 없다. 문자열의 길이 = 1 일 경우도 마찬가지 중간값을 기준으로 대칭되는 좌, 우의 값이 달라야 한다. 접었을 때 포개지는 곳은 다음 차례에 각각 서로 다른 방향으로 접히게 된다. 재귀 함수를 이용한다. 풀이 규칙을 만족하는지 판단하는 boolean 함수 check 선언 인자 : 문자열의 시..
문제 https://www.acmicpc.net/problem/2412 접근 방법 이분 탐색 문제집을 따라 풀던 중 만난 문제다. '알고리즘 분류' 란에 이분 탐색과 너비 우선 탐색이 있어 두 가지의 풀이가 존재한다고 생각했다. 그러나, 이분 탐색 방식으로 해결하지 못했다. 너비 우선 탐색을 사용하되, 다음 방문 노드를 찾을 때 이분 탐색을 이용하는 문제로 이해했다. (이 풀이는 이분탐색을 제대로 이용하지 못했다) 풀이 (0,0) 을 포함한 n + 1개 홈의 좌표를 저장할 Node[] graph 초기화 n + 1개의 홈에 대한 방문 횟수를 저장할 int[] visited 초기화 graph 배열을 정렬한다 (y를 기준으로 오름차순, 이후 동일한 y에 대해 x를 기준으로 오름차순) BFS 알고리즘 적용 (기..
