https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 어려웠습니다. 2개의 알고리즘을 혼합해서 사용하는 것에 익숙하지 않아서 애를 먹었습니다. 문제를 보면 stones의 길이가 20만이기 때문에 부르트포스로는 풀 수 없다는 것을 알 수 있습니다. 그렇기 때문에 이를 선형 시간이나 로그 시간 안에 풀어내야 합니다. 문제의 핵심은 얼마나 많은 사람을 건너게 할 수 있느냐인데, 이를 확인하는 방법은 연속된 k개의 돌 중, 내구도가 최대 중에 최소인 돌을 찾는 것입니다. 연속된 k개를 보는 이유는 특정 ..
분류 전체보기
[문제]https://www.acmicpc.net/problem/32620그래프를 탐색하는 데 있어서, 이웃 노드를 하나 이상 점령한다는 점에서 BFS 탐색을 떠올렸습니다. 또한 i번 노드로 이동하는 데 있어, 현재 기력이 요구하는 기력 이상이라면 이동할 수 있다는 점에서 그리디 접근 법을 떠올렸습니다. 즉 이동하고자 하는 노드와 인접한 노드를 방문한 상태이고, 요구하는 기력이 현재 기력 이하라면 모든 노드를 탐색할 수 있다는 점에서 최대한 많은 노드를 탐색해야 얻을 수 있는 기력을 최대로 만들 수 있습니다. 그렇기 때문에 BFS 탐색에 사용하는 자료구조로 일반적인 큐를 사용하지 않고 우선순위 큐를 사용해, 인접하면서 요구하는 기력이 작은 순으로 탐색하는 것입니다. 요약하자면다음 노드를 방문하기 위해서는..
[문제]https://www.acmicpc.net/problem/21608기본적인 구현문제로, 주어진 조건대로 착실하게 수행하면 되는 문제입니다.[초기화] def __init__(self): self.n = int(input()) self.student_info = [tuple(map(int, input().split())) for _ in range(self.n**2)] self.score = {0: 0, 1: 1, 2: 10, 3: 100, 4: 1000} self.grid = [[0] * self.n for _ in range(self.n)] self.friends_list = defaultdict(set) self.a..
[문제]https://www.acmicpc.net/problem/1937 전체적인 탐색을 진행하는 문제로, 이동에 제약이 걸려있는 것이 특징입니다. 시작점이 정해져 있다면, 주어진 대로 탐색을 진행하면 되지만 이동하는 칸을 최대로 만들어야 하기 때문에 시작점을 특정할 수 없습니다. 러프하게 생각하면 주어진 격자를 전부 탐색하면서 DFS를 수행하면 되겠지만, 시간 초과가 발생하므로 이동한 내역을 따로 기록해서 불필요한 이동을 막아줘야 합니다. 이때 사용되는 개념이 DP로, 해당 문제는 DFS + DP가 혼합된 문제입니다.[초기화] def __init__(self): self.n = int(input()) self.graph = [list(map(int, input().spl..
[문제]https://www.acmicpc.net/problem/1599요즘 코테를 보면 문자열 문제가 많이 출제되고 있는 거 같습니다. 특정 유형이 정해진 문제가 아니라면 아이디어로 구현하는 느낌이라 개인적으로 어렵게 다가오는 유형 중 하나입니다. 문제의 요지는 새로운 문자 체계를 기준에 맞게 정렬하는 문제입니다. 문자 정렬은 문자 하나하나의 아스키 값을 바탕으로 정렬하기 때문에, 새로운 문자 체계에 맞는 키 값을 매핑하는 방식으로 문제를 해결했습니다.[초기화] def __init__(self): self.n = int(input()) self.words = [input() for _ in range(self.n)] self.answer = [](키, 값) 형..
[문제]https://www.acmicpc.net/problem/14499주사위를 굴릴 때마다 주사위가 어떻게 변화하는지 시뮬레이션하는 문제입니다. 주사위를 "굴린다." 라는 표현에서 값들이 회전한다는 느낌을 받았고, 자연스럽게 Deque 자료구조를 떠올릴 수 있었습니다.[초기화] def __init__(self): self.n, self.m, self.y, self.x, self.k = map(int, input().split()) self.grid = [list(map(int, input().split())) for _ in range(self.n)] self.commands = list(map(lambda x: int(x) - 1, input().split..
[문제]https://www.acmicpc.net/problem/2458처음에는 어떻게 풀어야 할지 고민했습니다. 그런데 그래프 이미지 하단에 설명을 보고 연결된 그리고 연결한 노드의 수가 n - 1일 때 등수를 알 수 있다는 것을 알게 됐고, 진입 노드의 수 + 진출 노드의 수를 계산하면 답을 구할 수 있겠다고 생각했습니다. 이를 위해 진입 그래프와 진출 그래프를 만들고 두 번의 DFS를 수행했습니다. 굉장히 부르트포스한 방법인데, Python 기준 3000ms대로 풀이가 통과됐고, 입력을 sys를 받았을 때 위와 같은 시간대로 통과됐습니다.[초기화] def __init__(self): self.n, self.m = map(int, input().split()) self...
[문제]https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai으레 구현문제가 그렇듯이, 아이디어를 떠올리냐 못하냐의 싸움인 거 같습니다. 베이스캠프를 선정하는 방법을 떠올리지 못하면 그저 어려운 문제가 되는데, 방법을 떠올리는 순간 간단하게 풀 수 있습니다. 또한 해당 아이디어가 특출 난 것이 아니라 매우 간단한 것이라, 사람에 따라 허탈할 수도..
[문제]https://www.acmicpc.net/problem/7490 단순한 백트래킹에 공백이라는 조건을 추가해서 약간의 생각을 하게 만드는 문제였습니다.[초기화] static ArrayList results; static int n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int tc = Integer.parseInt(br.readLine()); for (int t = 0; t (); search("1", 1, 1, 1)..
[문제]https://www.acmicpc.net/problem/2109그리디하게 매 순간 가장 큰 강의료를 받을 수 있는지 확인하면 되는 문제입니다.[초기화] def __init__(self): self.n = int(input()) self.schedule = [list(map(int, input().split())) for _ in range(self.n)] self.visited = [False] * 10001 self.answer = 0강의는 특정 일자에 진행하는 것이 아닌, 제안받은 시점으로부터 d일 안에만 가서 강의를 진행하면 됩니다. visited는 이를 위해 어느 시점에 방문했는지 확인하기 위한 용도로 사용될 것입니다.[풀이] ..
