브루트포스 문제를 풀 때 순열, 조합 등으로 원소 인덱스를 뽑는 과정이 필요하다. 그러면 인덱스가 이차원(x,y)일 경우 어떻게 선택할 수 있을까? 아래의 방법으로 쉽게 선택할 수 있다. 1. 4X3의 배열일경우 (0,0)은 0으로 (3,4)는 11로 표현할 수 있다. 즉 이차원 인덱스(x,y)를 하나의 정수로 표현할 수 있다. 이 정수로부터 컬럼 크기로 나눈 값이 row, 컬럼 크기로 나머지 연산을 한 값이 col이 된다. 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net import java.util.*; im..
난이도 : 실버5 ~ 골드1 유형 : 완전 탐색, DP, 그리디, 구현, 그래프 탐색, 자료구조(큐/스택/덱) 시간 3시간 1. 11725번 트리의 부모 찾기 (난이도 : 실버2, 유형 : 그래프 탐색, 정답 : O) 2. 22860번 폴더 정리 (난이도 : 골드3, 유형 : 구현, 정답 : O) 3. 15661번 링크와 스타트 (난이도 : 실버1, 유형 : 완전 탐색, 정답 : O) 4. 14391번 종이 조각 (난이도 : 골드3, 유형 : 완전 탐색, 정답 : X) 트리의 부모 찾기 그래프 탐색 문제, A 노드에서 B 노드로 탐색할경우 B 노드의 부모는 A 노드가 된다. import java.util.*; import java.lang.*; import java.io.*; public class Ma..
난이도 : 실버3 ~ 골드3 유형 : 완전 탐색, DP, 그리디, 구현, 그래프 탐색, 자료구조(큐/스택/덱) 시간 3시간 1. 2285번 우체국 (난이도 : 골드4, 유형 : 그리디, 정답 : △) 2. 21608번 상어초등학교 (난이도 : 골드5, 유형 : 구현, 정답 : O) 3. 9465번 스티커 (난이도 : 실버1, 유형 : DP, 정답 : △) 4. 11725번 트리의 부모 찾기 (정답 : X) 우체국 좌우 인원의 차가 0에 가까운 마을에 우체국을 지으면 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우게 된다. import java.util.*; import java.lang.*; import java.io.*; public class Main { public static voi..
난이도 : 실버3 ~ 골드3 유형 : 완전 탐색, DP, 그리디, 구현, 그래프 탐색, 자료구조(큐/스택/덱) 시간 3시간 1. 백준 16932번 모양만들기 (난이도 : 골드3, 유형 : 그래프 탐색, 정답 : O) 2. 백준 2800번 괄호제거 (난이도 : 골드5, 유형 : 브루트포스·스택, 정답 : △) 3. 백준 2285번 우체국 (정답 : X) 4. 백준 11725번 트리의 부모 찾기 (정답 : X) 모양만들기 N X M 크기의 배열에서 0인 칸 하나를 1로 만들어서 제일 많이 연결된 1의 수를 구하는 문제이다. 무식한 방법으로 모든 0인 칸을 각각 1로 만들어 그래프 탐색하는 방법이 있지만 그랬다간 시간 초과날게 뻔했다. 한번의 그래프 탐색으로 이 문제를 해결할 순 없을까? 부분 그래프를 그룹으..
문제를 방향 그래프로 만들어 오일러 경로 또는 오일러 트레일을 구하는 문제로 변환할 수 있다. a부터 z를 정점으로 두고 단어의 시작 알파벳에서 단어의 마지막 알파벳으로 가는 간선을 추가한다. 예를 들어 dog 단어가 나온다면 d에서 g로 가는 간선을 추가한다. 그런 다음 방향 그래프에 오일러 경로 혹은 트레일이 존재할 수 있는지 확인 후 오일러 경로 또는 오일러 트레일을 구해 단어를 출력한다. (모든 정점) 진입 차수 = 진출 차수 → 오일러 경로 존재 (시작점) 진출 차수 = 진입 차수 + 1, (끝점) 진출 차수 = 진입 차수 - 1, (나머지 정점) 진입 차수 = 진출 차수 → 오일러 트레일 존재 import java.util.*; import java.io.*; public class Main ..
난이도 : 실버3 ~ 골드3 유형 : 완전 탐색, DP, 그리디, 구현, 그래프 탐색, 자료구조(큐/스택/덱) 시간 : 3시간 1. 백준 1106번 호텔 (난이도 : 골드 5, 유형 : DP, 정답 : O) 2. 백준 14620번 꽃길 (난이도 : 실버 2, 유형 : 완전탐색, 정답 : △) 3. 백준 22944번 죽음의 비 (정답 : X) 4. 백준 22868번 산책 (정답 : X) 호텔 문제를 보고 최적 부분 구조를 파악할 수 있었다. X명을 구하는데 드는 최소 비용은 1명과 X-1명을 구하는데 드는 최소 비용, 2명과 X-2명을 구하는데 드는 최소 비용, ··· 중의 최소값이다. 따라서 DP를 적용했고 구현의 편의성을 위해 Bottom-up 방식으로 1명, 2명, ···, X명을 구하는데 드는 최소..
주어진 단어들을 가지고 DAG를 만들어 위상 정렬 하는 문제이다. 임의의 알파벳 a, b에 대해서 a가 b보다 사전 순으로 앞선다면 a에서 b로 가는 간선이 존재하도록 DAG를 만든다. DFS()가 종료될때마다 리스트에 정점을 넣고 모든 DFS가 끝난 후 리스트를 역순으로 정렬하면 위상 정렬 결과를 얻을 수 있다. DAG에 사이클이 존재한다면 모순이 발생한다. 사이클 발생 여부를 직접 체크할수도 있지만 어차피 위상 정렬을 해야 되기에 간단하게 위상 정렬 후 결과에서 오른쪽에서 왼쪽으로 가는 간선이 있다면 DAG에 사이클이 존재한다는 걸 알 수 있다. import java.util.*; import java.io.*; public class Main { public static void main(Strin..
난이도 : 실버 3 ~ 골드 3 유형 : 브루트포스, DP, 그리디, 구현, BFS/DFS 시간 : 2시간 30분 1. 백준 14719번 빗물 (난이도 : 골드 5, 유형 : 구현, 정답 : O) 2. 백준 8980번 택배 (난이도 : 골드 2, 유형 : 그리디, 정답 : O) 3. 백준 14500번 테트로미노 (난이도 : 골드 5, 유형 : 브루트포스, 정답 : △) 4. 백준 22868번 산책 (정답 : X) 빗물 문제를 보고 구현 문제임을 바로 파악할 수 있었다. 어떤 칸이 빗물에 고일려면 아래의 조건을 만족해야 한다. 아래 칸이 막혀야함 (아래칸이 블록이거나 빗물에 고여있거나 맨밑이어야함) 왼쪽과 오른쪽이 막혀야함 (해당 칸을 기준으로 왼쪽과 오른쪽이 블록이어야함) 아래 칸이 막혔는지는 바로 알 ..
