https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 비트마스킹으로 풀어보겠습니다. 사실 이 문제는 다른 분들의 코드를 참고해서 구현했습니다. 비트마스킹을 잘 모르겠어서요^_^ wordsBit라는 배열을 사용했는데 이 부분을 2차원으로 할 수도 있지만 1차원으로도 할 수 있다! 바로, 해당 단어에 사용된 알파벳을 체크해 주는 방식인데, 시프트(shift)와 OR 연산을 사용한다! 시프트는 왼쪽 시프트 1 10100010000000000001 ..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 톱니바퀴가 12시부터 시계방향으로 N/S 값이 배열로 입력된다. 우선 각 톱니바퀴의 방향을 dir 배열에 넣어주고, 톱니바퀴의 각 톱니의 값을 바꿔주는 방식으로 진행했다. 회전하는 톱니바퀴를 기준으로 left와 right 부분을 나눠서 진행했다. 각 방향으로 가던 중 돌아가지 않는다면( 같은 극의 경우 ) 끝낸다. 그 바퀴가 돌아가지 않으면 그 다음(혹은 이전)의 톱니바퀴도 돌아가지 않으므로 ..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 이 문제는 처음에는 쉽게... 문자열 메소드를 사용했다. 그랬더니 45-47에서 시간초과 발생... //시간초과 while word.contains(explosion) && !word.isEmpty { word = word.replacingOccurrences(of: explosion, with: "") } print(word == "" ? "FRULA" : word) 그래서 다시 ..

https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 사실 이 문제는 트리 문제를 풀어보기 위해 푼 문제였다. 그런데 도통 트리로는 어떻게 해야 할지 모르겠고 그냥 완탐으로 풀었다... 입력받은 문자열을 앞에서부터 뒤로 순회하면서 hasPrefix 메소드를 통해 이 단어를 접두사로 사용하는지 체크하고 접두사라면 answer에서 차감해 줬다. 왜냐면 부분 집합의 최대 크기를 구하는 게 목표인데..

https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 모든 정점이 연결되어 있기 때문에 한 지점에서 시작해도 모든 경로를 갈 수 있다. 그래서 나는 DFS로 1에서 시작해서 쭉 이동하도록 했다. 그리고 그 경로(edge)의 개수를 세면 된다. 좀 보니까 답이 (정점 개수 - 1) 인 것을 알 수 있다!ㅋㅋㅋ 하지만 DFS로 탐색해 봤다~ import Foundation //input let t = Int(read..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 이 문제는 2 부분으로 나눌 수 있다. 5 이동 방향 케이스 구하기 이동 구현 처음에는 1번 ~ 5번 움직임을 모두 보려고 했는데 사실 그냥 5번 이동을 봐도 되는 것이다..! 1회 움직이는 것보단 5회 움직이는 게 최댓값이 나올 확률이 높으니까. 그리고 1회에서 최댓값이 나온다고 해도 사실 5회까지 움직이는 건 상관없을 거 같다. 그래서 DFS로 5회를 여러 방향으로..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 맨 뒷자리 수 고정하고 진행! dp 2차원 배열~ 이전에 여러 문제를 풀어본 결과, 공통점을 찾아야 한다. 그래서 이런 수를 가지고 문제를 풀어야 하는 경우 맨 뒤를 공통으로 맞추고 진행하면 좋다. 0 1 2 3 4 5 6 7 8 9 ----------------------- 1 | 0 1 1 1 1 1 1 1 1 1 2 | 1 1 2 2 2 2 2 2 2 1 3 | 1 3 3 4 4 4 4 4 3 2 이렇게 나열해 볼 수 있는데! 위에 표에서 보이는 대로 말하자면, 열은 마지막 수, 행은 자릿수를 나타낸다. ..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net dp [1][i] = i자리가 1인 경우 dp[0][i] = i자리가 0인 경우 1 2 3 4 5 6 ----------------- 0 | 0 1 1 2 3 5 1 | 1 0 1 1 2 3 개수를 세보면서 진행하면 규칙이 보인다! dp[1][i]는 dp[0][i-1]의 값과 동일하고 dp[0][i]는 dp[0][i-1] + dp[1][i-1] 값이다! //input let n = In..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net i번째 열에서 1행 스티커를 선택한 경우, 2행 스티커를 선택한 경우를 나눠서 진행하면 된다. 상하좌우가 붙으면 안 되니까 한 열에 하나의 행만 선택하고, 이전 열 혹은 전전 열의 다른 행을 선택한 경우를 봐야 한다. 전전 열을 봐야 해서 맨 앞에 0을 추가하고 진행해 줬다. 아니면 1열의 전전 행은 -1 이니까... 맨 앞에 원소를 넣어서 1 열부터 스티커가 있다고 가정하고 시작하기...