개발하는 고라니

18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net [비트마스킹] 입력으로 N개의 단어가 문자열 형태로 주어지는데, 이를 문자열로 저장하는 것 보다, 어떤 알파벳이 있는지를 알고있으면 단어 전체를 보지 않더라도 이 단어를 알 수 있다. 따라서 String[ ]이 아닌, int[ ]에 저장하는 것이 바람직 할 것이다. 비트마스킹에 대해 잘 모른다면 간단하게 정리해둔 포스팅을 참고하자. [알고리즘] 비트 마스킹(Bit Masking) 비트 마스킹은 알고리즘이라기 보다는 비트의 연산을 이용한 테크닉이라고 볼 수 있다..

1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net [DFS + 백트래킹 + 비트마스킹] DFS를 이용해 백트래킹을 구현했고, 알파벳 'a' ~ 'z'까지 어떤 알파벳을 알고 있는지에 대한 정보를 비트마스킹으로 표현했다. 즉, 'a', 'b'를 알고있다면 0b00 0000 0000 0000 0000 0000 0011로 나타낼 수 있다. 그런데 남극의 단어는 "anta"로 시작해서 "tica"로 끝난다고 했으니, 'a', 'c', 'n', 't', 'i'는 반드시 알고있어야 한다. 그래서 check를 다음과..

1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net [비트마스킹] 정수형 배열을 하나 준비한다. 사이즈는 대충 16이상이면 된다. 배열의 0 번째 원소에 1 x라면 idx를 감소시킨다. 이제 비트 연산자를 이용해 arr[idx] = (arr[idx-1] >> 1); arr[idx-1] = (arr[idx-1] >> 1); idx번 째와 idx-1번째 원소를 idx-1번째에 있는 원소를 반으로 나눈 값으로 설정한다. sum == x일 때 까지 반복 # Code import java.io.BufferedReade..

2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net [비트마스킹 + DP] 처음에 문제를 보고 최소 스패닝 트리 문제인 줄 알았다. 그래서 크루스칼 알고리즘을 사용해서 풀 수 있겠다 싶었지만, 최소 스패닝 트리와 완전히 달랐다. 최소 스패닝 트리는 한 정점이 2개 이상의 간선을 가질 수 있지만, 외판원 순회의 경우 한 정점은 2개만 갖을 수 있다. 그리고 반드시 출발점 -> ... -> 출발점이 되어야한다. 이때의 최소값을 구하는 문제였던 것이다. DP와 DFS에 취약한 내 ..

9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net [BFS + 비트마스킹] 정말 맞왜틀? 이 질문이 여러번 나왔던 문제. 뜻밖의 반례를 찾아서 다행히 AC를 받았다. 1 6 6 .***** .A$B$* ****** .C$D$* ****** **ac** 0 answer : 2 기존 코드는 위의 반례에서 무한루프를 돌았다. 그 이유는 망각해버렸으나 어떤 열쇠를 갖고있는지에 대한 정보 (key)를 전역변수로 두어 BFS내에서 공유하게 했더니 TLE를 피했다. 그리고 "상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 빈 공..

1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net [BFS + Bit Masking(비트마스킹)] 우선, 열쇠가 a, b, c, d, e, f 6개이므로 6자리 이진수의 최대값인 111111만큼의 visit 배열이 필요하다. 111111 = 63이다. 그러나 배열의 Index에 적용하기 위해선 +1을 해주어야 하므로 visit[64]개 만큼의 공간이 필요하다. 그럼 visit은 다음과 같이 정의될 수 있다. boolean[][][] visit = new boolean[64][51]..