개발하는 고라니

14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net [최소 스패닝 트리(Minimum Spanning Tree, MST), 크루스칼] 남초와 여초만을 이어주는 경로만 존재한다고 생각하면 쉽다. 문제에서 2번째 줄에 M W W W M 이런 식으로 주어지는데, 이를 boolean[ ]에 저장을 한다. 예를 들어 1번 째 학교가 M(남초) 이면 true, 2번 째 학교가 W(여초)이면 false 이런 식으로. 그럼 간선 정보가 주어질 때 선별적으로 간선을 저장할 수 있다. for..

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를 다음과..

6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 DFS 탐색 -> 방문 취소 가 이뤄져야 한다. # Code import java.io.BufferedReader; import java.io.IOException; i..

9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net [문자열 / Stack(Array)] # 풀이 요약 1. 문자열(origin)을 받아 char[ ] arr로 변환한다. 2. 폭발 문자열을 받아 char[ ] bomb으로 변환한다. 3. char[ ] stack을 준비한다. 이때 top = -1 4. arr의 한 문자씩 stack에 넣는다. 5. 만약 stack에 넣은게 bomb의 마지막 문자라면 bomb의 크기만큼 stack의 뒤로 가며 문자 비교 6 비교 결과 bomb을 동일하게 포함하고 있다..

4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net [문자열, Stack] 이 문제를 풀기 전 아스키 코드를 알면 좋다. 아스키 코드 표를 참고하면 '(' : 40 ')' : 41 '[' : 91 ']' : 93 위와 같다. 따라서 ')' - '(' = 1이고, ']' - '[' = 2이다. 이 규칙만 잘 활용하면 쉽게 풀 수 있다. 먼저 스택을 준비하는데, 동적의 크기를 갖는 컬렉션 또는 자료구조로 할 수 있지만, 배열로도 충분하기 때문에 배열로 스택을 구현해주었다. 그리고 타겟의 문자를 저장하는..

14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [BFS] BFS를 이용해서 풀었다. 일반적인 BFS와 다른 점은, 보통 BFS는 현재 정점에서 탐색할 수 있는 모든 정점을 Queue에 넣지만, 이 문제는 현재 정점에서 한 개의 정점만 큐에 넣을 수 있다. 큐에 들어갈 원소는 y좌표, x좌표 그리고 방향이다. static class Point{ int y, x, dir; public Point(int yy, int xx, int d){ y=yy; x=xx; dir = d; } } 현재 방향에 따라 다음 방향이..

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

16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net [BFS] 문제의 난이도는 그렇게 높진 않으나 접근하기가 까다로웠다. 각 층은 4방향을 가질 수 있고, 1~5층에 어떤 것을 넣든지 사용자의 결정이다. 사실상 브루트포스로 풀었다. 먼저 입력을 받을 때 원 방향, 90도, 180도, -90도 회전시킨 판의 모양을 저장한다. for(int i=1; i