고양멍멍이

[문제링크] 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 0. j ~ j+i 까지의 수가 팰린드롬 수가 되려면 - j, j+1번 자리의 수가 같아야하며 - j+1 ~ j+i-1 까지의 수가 팰린드롬 수여야 한다 1. 1, 2자리 수에 대해 팰린드롬 수 여부를 계산한다 - 1자리의 수는 전부 다 팰린드롬 수 - 두 자리의 수가 연속이라면 팰린드롬 수 2. isP[x][y] 배열은 y번째 수부터, x개의 수를 고려했을때 해당 수가 팰린드롬인지 여부를 판단한다 - isP[10][5] - 5~14의 수가 팰린드롬인지 정보 저장 3. 3자리부터 n자리까지..

[문제링크] 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 0. A칸에서 이동해 B칸으로 갈 경우, A와 B는 같은 집합에 속한다 - 이러한 이동-집합에 대해, 각 집합당 1개의 SAFE-ZONE이 필요하게 된다 - disjoint-set으로 집합 관리 1. n*m개의 각 칸을 set으로 만들고, set의 갯수 또한 n*m으로 초기화한다 2. 모든 칸을 순회하며 각 칸의 이동에 따라 도착지점의 set과 결합한다 3. 최종적으로 남아있는 set의 갯수가 필요한 SAFE-ZON..

[문제링크] 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 0. treeNode 자료구조는 부모 index, 자기 value, 자식 index의 List로 구성됨 - treeNode의 배열로서 tree를 표현한다 1. 문제의 입력은 0-base지만, 편의상 1-base로 변경. 0은 가상의 head node로서 사용한다 2. 입력을 받으며 자신의 parent에 등록 + parent의 child에 등록해 tree 완성 3. 0번을 parent로 가지는, tree의 root노드로부터 bfs 탐색한다 - c..

[문제링크] 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 0. 사방 처리를 위해 외곽을 1로 감쌌다 1. 전체를 탐색하면서 0, 빈공간을 만날 경우 BFS 진행 - BFS에서 거쳐가는 모든 칸을 index로 칠해 재탐색 방지 + 추후 이용 - BFS의 결과로 반환된 size를 ArrayList에 저장한다 - ( 0은 빈칸, 1은 벽이므로 area index는 2부터 시작, index 유지를 위해 0 2개 삽입) 2. 전체를 탐색하면서 벽을 만날 경우 4방향에 대해 - 1이 아니면 빈 공..

[문제링크] 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 0. disjoint set 문제 1. A에서 B로 선분을 그으려 할 때, 이미 A와 B가 같은 집합에 속한다면 사이클이 생성된다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static void main(String[] args)throws Exception { Buf..

[문제링크] 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 0. 알파벳은 26자이므로, 32bit int를 사용해 bit-masking으로 등장 정보를 저장한다 1. chk변수에는 모든 알파벳 정보를 저장해, 등장하는 알파벳들에 대해서만 검사하도록 한다 2. a,n,t,i,c 5자는 반드시 등장하므로, 기본적으로 지워두고 시작한다 3. m이 5보다 작으면, 위 5자를 지울수 없으므로 즉시 실패, 아니라면 남은 알파벳의 모든 조합을 구한다 4. 모든 가능한 조합에 대해 알파벳을 지워보면, 모든 알파벳이..

[문제링크] 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 0. 1번집의 색 != N번집의 색이어야 한다 1. 1번집을 단색으로 제한한 후 RGB값을 각각 구한다 - 1번집을 R로 설정 -> N번집이 G/B로 끝나는 최솟값 구하기 - 1번집을 G로 설정 -> N번집이 R/B로 끝나는 최솟값 구하기 - 1번집을 B로 설정 -> N번집이 R/G로 끝나는 최솟값 구하기 2. 전체 결과 6가지 중 최솟값이 정답 import java.io.BufferedReader; import java...

[문제링크] 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 0. 비행기가 1~n의 게이트 중 하나에 들어가야한다면, 가능한 게이트 중 가장 큰 게이트에 들어가야한다 (그리디) - 1~n이 가능한 비행기가 1번에 들어가버리면, 1~1밖에 안되는 비행기가 다음에 들어오면 즉시 종료된다 1. 비행기가 가능한 가장 큰 게이트에 들어가므로, 게이트들은 연속으로 차지되게 된다 - 1~n인 비행기만 5대 들어왔다면 n, n-1, n-2, n-3, n-4 게이트가 순서대로 사용될 것 2. ..

[문제링크] 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 0. 다익스트라나 프림에서 사용하는 방식을 사용했다. 1. 시작지점의 초기값은 MAX, 나머지 지점의 초기값은 0 2. 아직 가보지 못한 지점중, 가장 많은 짐을 지고 갈수있는 지점 X를 탐색한다 3. X로부터 갈수있는 지점들을, X를 거치는 경우 / 기존 최댓값을 비교해 갱신한다 4. 이를 n번 반복하면, n개의 노드 전체를 탐색한 것이다. 5. 종료된 후 end지점에 있는 값이 해당 지점에 들고갈 ..

[문제링크] 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 0. disjoint set 문제 1. 기존에 존재하는 학생들의 관계를 따라 set들을 합친다 2. 학생들을 친구비에 따라 정렬한다 3. 친구비가 낮은 순서로 친구맺기를 시도한다. - 해당 학생이 속한 집합의 root를 구해 이미 친구인 집합인지, 아닌지 판단한다 4. 모든 집단과 친구가 된 후, 금액이 k보다 크다면 실패 import java.io.BufferedReader; import java.io...