본문 바로가기

Algorithm283

[BOJ]1411번: 비슷한 단어 문제: https://www.acmicpc.net/problem/1411 문제 이해 못해서 멍때렸던 문제입니다. 최대 100개에 대해 2개씩만 비교하면 되니 100 combination 2의 경우의 수로 완전탐색이 가능합니다. 두 개씩 뽑아서 아래 사항들을 비교해주면 됩니다. 1. 길이가 같은지 2. 이미 매칭된 알파벳이 다른 알파벳과 매칭되었는지 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1411.cc 2020. 7. 1.
[코딩테스트 연습] 디스크 컨트롤러 문제: https://programmers.co.kr/learn/courses/30/lessons/42627 문제 조건 중 아래의 조건 때문에 그리디로 해결할 수 없는 문제입니다. 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. 디스크 컨트롤러가 처리해야 할 상황은 두 가지로 나눌 수 있습니다. 1. 현재 디스크 컨트롤러가 위치하는 시간 = 가장 우선처리 해야 할 작업의 시작시간 1번 케이스의 경우 작업을 수행하고 있지 않은 경우이니 그냥 가장 시작시점이 빠른 작업을 수행합니다. 2번의 경우 흔히 말하는 SJF(Shortest Job First)로 해결하면 됩니다. 즉, 현재 디.. 2020. 6. 30.
[BOJ]2668번: 숫자고르기 문제: https://www.acmicpc.net/problem/2668 유형 태그가 다양한 걸 보니 푸는 방법은 다양한 것 같습니다만, 싸이클 찾기 문제로 해결했습니다. N = 100이니 직접 하나씩 뽑아보면서 탐색하면 터지는 건 자명합니다. 문제 예제를 보면 표에서 첫번째 줄에 5번 칸이 -> 5로 가는 걸 볼 수 있습니다. 이걸 보고 자기 자신의 숫자를 가지는 애들이 정답 갯수에 포함된다면, 정답으로 뽑히는 애들은 싸이클 성질을 가지고 있다는 걸 알았습니다. 즉, 이 문제는 가장 큰 싸이클을 구하는 문제입니다. 싸이클을 찾는 방법은 위상정렬을 통해 해결하였습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2668.cc 2020. 6. 26.
[BOJ]13549번: 숨바꼭질 3 문제: https://www.acmicpc.net/problem/13549 다익스트라로 해결하였습니다. 특정 좌표 X에서 수빈이가 움직일 수 있는 위치는 세 가지 입니다. 1. X-1 2. X+1 3. 2X 다익스트라로 해결한 이유는 두 배씩 뛰는 좌표의 경우 시간의 영향을 받지 않습니다. 그러므로 그냥 단순히 방문했다고 visited[] 배열을 true / false로만 표시한다면 더 빠른 시간에 특정 좌표 X에 도착해도 이미 visited[] 이 true라면 다시 탐색할 수 없습니다. 그러므로 큐에서 늦게 나온 값이라도 이미 저장되어있는 visited[] 시간보다 빠르면 갱신해줍니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ13549.. 2020. 6. 20.

티스토리툴바