백준

[문제]https://www.acmicpc.net/problem/2234그래프 탐색에 비트마스킹이 합쳐진 독특한 문제였습니다. 문제에서 비트에 대한 언급이 있어서 쉽게 풀 수 있었지, 없었다면 쉽게 감을 잡지 못했을 것입니다. 오랜만에 시간을 재고 풀어본 문제로, 구조화 30분, 풀이 및 디버깅 1시간 소요했습니다.[초기화] def __init__(self): self.n, self.m = map(int, input().split()) self.origin = [list(map(int, input().split())) for _ in range(self.m)] self.grid = [[0] * self.n for _ in range(self.m)] ..

[문제]https://www.acmicpc.net/problem/14503주어진 조건을 순서대로 그대로 구현하면 되는 문제입니다.[초기화] def __init__(self): self.n, self.m = map(int, input().split()) self.r, self.c, self.d = map(int, input().split()) self.grid = [list(map(int, input().split())) for _ in range(self.n)] self.answer = 0[풀이] def solve(self): directions = [[-1, 0], [0, 1], [1, 0], [0, -1]] whil..

[문제]https://www.acmicpc.net/problem/14442조건에 따라 최단 경로가 달리지는 문제입니다. 벽 부수고 이동하기와의 차이점은 벽을 부수는 횟수 차이입니다. 최근에 봤던 기업의 코딩테스트에서 유사한 유형의 문제가 출제되었습니다. 조건에 따라 다르게 이동하는 테크닉을 익혀두는 것도 좋을 거 같습니다. https://www.acmicpc.net/problem/1600위 문제도 해당 문제와 풀이 방식이 유사합니다.[초기화] static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int n, m, k; static char[][] map;..

[문제]https://www.acmicpc.net/problem/14002기본적으로 LIS 문제에 수열을 이루는 값을 기록하는 조건이 추가된 문제입니다.[초기화] def __init__(self): self.n = int(input()) self.arr = list(map(int, input().split())) self.answer = [][풀이] def solve(self): dp = [1] * self.n prev = [-1] * self.n # 이전 인덱스 추적을 위한 배열 max_length = 0 max_index = 0 for i in range(1, self.n): # dp 계..

[문제]https://www.acmicpc.net/problem/2295처음에는 세 용액 문제처럼 기준을 잡고 나머지 두 수에 대해 투 포인터로 탐색을 진행하려고 했습니다. 하지만 최대에 대한 기준이 없기 때문에 적용하지 못했고, 집합 자료구조를 이용해 만들어낼 수 있는 수를 체크하는 방식으로 문제를 풀이했습니다.[초기화] static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int n; static int[] u; static int answer = 0; public static void main(String[] args) throws IOException { n = Integer.parseInt(..

[문제]https://www.acmicpc.net/problem/13913일반적인 그래프 형태의 BFS가 아닌 특이한 형태의 BFS입니다.  해당 시리즈 문제를 풀어본 경험이 있어서 풀 수 있었고, 처음 해당 유형의 문제를 풀 때는 정답을 보고 이해했었습니다. 해당 문제는 BFS + 경로 역추적을 수행하는 문제로 보면 되겠습니다.[초기화] static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int n, k; static int[] time; public static void main(String[] args) throws IOException { s..

[문제]https://www.acmicpc.net/problem/2582solved.ac에서 시뮬레이션 문제를 풀려고 검색하다가 재밌는 유형을 발견했습니다. Simulated Annealing은 전역 최적화 알고리즘으로, 제가 석사 과정 시절 진화형 알고리즘 수업에서 배웠던 알고리즘입니다. 그 당시 배우기를 Hill-Climbing Search의 문제점을 해결하기 위해 고안된 알고리즘이라고 배웠습니다. Hill-Climbing Search는 AI에 대해 학습하다 보면 한 번쯤은 접하게 되는 알고리즘입니다. Hill-Climbing Search는 경사(기울기)를 따라가며 최적해를 찾습니다. 하지만 시작점에 따라 Local optima에 빠질 확률이 높다는 문제점을 가집니다. 위 그림처럼 Current st..

[문제]https://www.acmicpc.net/problem/12100오랜만에 높은 난이도의 문제를 풀어보았는데, 전혀 Easy하지 않았습니다. 풀이 방식 자체는 어렵지 않게 떠올렸는데, 보드를 조작하는 과정에서 원상 복귀하는 것을 고려하지 않아 디버깅에 3시간을 헤맨 문제입니다. 또한 생각한 풀이가 너무나도 삼성스럽길래 찾아보니 기출문제가 맞았습니다.https://www.acmicpc.net/problem/15683이 문제와 유사한 거 같습니다.[초기화]public class BOJ_12100_2048Easy { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer s..

[문제]https://www.acmicpc.net/problem/2638시뮬레이션이 포함된 그래프 탐색 문제입니다. 주요 전략은 치즈의 외부와 내부 공간을 분리하여, 치즈의 외부를 지속적으로 탐색하는 것입니다.[초기화] def __init__(self): self.n, self.m = map(int, input().split()) self.grid = [list(map(int, input().split())) for _ in range(self.n)] self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] self.answer = 0탐색은 BFS, DFS 둘 다 가능하지만, BFS가 더 빠른 속도를 보장할 수 ..

[문제]https://www.acmicpc.net/problem/9466문제를 단순하게 표현하면, 형성된 그래프에서 사이클에 속하지 않는 노드의 수를 찾으면 되는 문제입니다. 여기서 노드는 학생을 의미합니다.12345673137346문제의 예시를 그래프로 나타내면 다음과 같은 모습을 나타내게 됩니다. 여기서 사이클에 속하지 않는 노드는 1, 2, 5 총 3개가 됩니다. 위와 같이 그래프로 표현해 보고, 문제에서 제시하는 바가 사이클에 속하지 않는 노드를 찾아야 한다는 것을 알 수 있었습니다. 문제 자체는, BFS와 DFS 모두 수행가능하지만, 최단 경로를 찾는 문제도 아니고 탐색 과정을 추적하는 과정에서 별도의 비용일 발생하는 BFS보다 DFS가 적합하기 때문에, 해당 방식으로 문제를 풀어냈습니다. 제 ..