[문제]https://www.acmicpc.net/problem/17141바이러스 조합을 찾아서 BFS를 수행하는 문제입니다. 바이러스 조합을 찾는 이유는, 어느 위치의 바이러스를 선택했을 때 최소 시간으로 퍼뜨릴 수 있을지 모르기 때문입니다.[초기화] 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 = float('inf')[풀이] def ch..
Python
[문제]https://www.acmicpc.net/problem/7453시간제한이 무려 12초인 문제입니다. 대놓고 최적화를 요구하는 문제라는 것을 알 수 있습니다. 특정 값을 만들 수 있는 조합의 수를 찾는 것이 목표입니다. 이러한 문제 유형의 경우, 전부 계산하지 않고 부분으로 쪼개 해시에 저장해 값을 비교하는 것이 일반적입니다. 부르트포스하게 풀면 O(n^4)이지만 해시를 사용하면 O(n^2)에 풀 수 있습니다.[초기화] def __init__(self): self.n = int(input()) self.arr = [list(map(int, input().split())) for _ in range(self.n)] self.a, self.b, self.c,..
[문제]https://www.acmicpc.net/problem/16946이전 벽 부수고 이동하기 시리즈와는 상관없는 문제입니다. 처음에는 1인 위치마다 BFS를 사용하여 부르트포스하게 풀었습니다. 그 결과 시간 초과가 발생했고 최적화를 고민해야했습니다. 부르트포스하게 접근하는 방법을 생각했을 때를 생각하면, 공통되는 빈 공간을 지속적으로 탐색하는 상황이 발생하게 됩니다. 빈 공간은 유동적으로 바뀌는 것이 아니므로, 한 번 계산하면 해당 빈 공간과 인접한 다른 곳에서 탐색할 때 재탐색할 필요 없이 결과를 합산하면 됩니다.즉 위와 같이 첫 1에서 출발해 0인 빈 공간을 탐색한 뒤에는, 나머지 인접한 1에서 해당 빈 공간을 탐색할 필요가 없다는 것입니다. 어디서 출발하는 탐색할 빈 공간의 크기는 3이 자명하..
[문제]https://www.acmicpc.net/problem/4179동시에 발생하는 상황을 시뮬레이션해야 하는 문제입니다. 동시 시뮬레이션이라고 특별한 기법이 필요한 것은 아니고 진행 상황을 처리해두기만 하면 됩니다. 그렇기 때문에 코드 상에서, 불이 먼저 번지든, 지훈이가 먼저 이동하든 상관없습니다.[초기화] def __init__(self): self.r, self.c = map(int, input().split()) self.grid = [list(input()) for _ in range(self.r)][풀이] def search_jihoon(self): for i in range(self.r): for j in range(s..
[문제]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/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/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/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..
