[문제]https://www.acmicpc.net/problem/2212문제 난이도에 비해, 설명이 시원하게 와닿지 않은 문제였습니다.[초기화] def __init__(self): self.n = int(input()) self.k = int(input()) self.sensor = list(map(int, input().split()))[풀이] def solve(self): self.sensor.sort() distance = sorted(list(map(lambda i: self.sensor[i + 1] - self.sensor[i], range(self.n - 1)))) print(sum(distance[:self..
분류 전체보기
[문제]https://www.acmicpc.net/problem/2169 처음에는 다익스트라를 생각하고 문제에 접근했으나, 모든 정점을 확인할 수 없어 dp로 풀어낸 문제입니다. dp 문제답게 풀이가 길지 않습니다. 또한 코드트리에서 연습했던 dp 빈출 유형과 유사한 문제였습니다.[초기화] static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int n, m; static int[][] map; public static void main(String[] args) throws IOException { st = new StringTokenizer(br..
[문제]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.codetree.ai/training-field/frequent-problems/problems/battle-ground/description?page=3&pageSize=5 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai문제를 따라 읽으며 그대로 구현하면 되는 문제입니다. 크게 어려운 테크닉은 없으며, 반대 방향 및 회전에 대해서만 주의하시면 되겠습니다.[초기화] def __init__(self): self.n, self.m, self.k = map(int, input().split()) sel..
