본문 바로가기

Computer Science/Algorithm

 (117)
[Python 3] BOJ 17452 Christmalo.win 문자열들의 앞과 뒤를 잘라서, 같은 알파벳이 있으면 서로 연결시킬 수 있다.이 때, 자르는 알파벳들의 수가 최소가 되게끔 해야한다. 따라서, christma(s), (h)alloween을 통해 각각 s와 h를 지우면 연결을 할 수 있는 셈이다. 여기서 두 개의 문자열을 보고 하나하나 비교를 하게 되면, 10만개 중에 두개를 고르는, 10만 C 2 개의 연산을 해야하고, 이는 무조건적으로 TLE를 받게 된다. 문제의 포인트는 결국 '알파벳'을 기준으로 연결한다는 점이다.a부터 z까지의 알파벳이 왼쪽에서 언제 제일 빨리 나오는지, 오른쪽에서 언제 제일 빨리 나오는지를 저장한다. (left,right)각 string을 돌면서, string에서 a부터 z까지 각 알파벳이 왼쪽에서 언제 제일 빨리 나오는지, 오른..
[Python 3] BOJ 17720 마약수사대 https://www.acmicpc.net/problem/17220 마약수사대는 마약공급책을 잡고 싶어 한다.마약의 원산지는 '다른 공급책에게 공급 받지 않는' 공급책이다.여기서, 해당 문제는 마약 공급책들 중 마약을 공급받을 수 있는 공급책의 수를 구하는 문제이다. 해당 문제는 DAG (Directed Acyclic Graph)의 일종으로 볼 수 있다. 즉, cycle이 없지만, 방향성이 있는 간선들로 이루어져 있다.따라서, 마약을 공급받지 않는 공급책들을 모두 저장받고, 해당 공급책들에 대해서 BFS를 실시하여 전달이 가능한 공급책들의 수를 세면 된다. 여기서 각 공급책의 이름이 대문자 알파벳으로 주어져 있다.이들을 리스트의 index로 만들기 위해, 'A'의 아스키 코드에서 빼서 번호를 설정한다.또..
[Python 3] BOJ 16973 직사각형 탈출 보통의 bfs와 같은 그래프 탐색 문제는 한 개의 지도를 바탕으로 1x1짜리 정사각형이 좌표를 돌아다니는 느낌인데, 이 문제는 우리가 움직여야 하는 직사각형의 크기가 H by W이다. 따라서, 직사각형을 움직이면서, 도착지점에 갈 수 있는 최소이동을 물어보는 문제였다. BFS로 해결했다. 처음 시작점에 직사각형이 위치할 수 있는지 여부를 확인한다.이후 왼쪽 상단 지점을 기준으로 직사각형의 좌표를 잡고 상하좌우로 이동시킨다.만약 벽이 있거나, 장애물이 있으면 움직일 수 없다.하지만 단순히 이동한 직사각형 안의 모든 좌표를 확인해야하면 시간초과 (TLE)가 발생한다.우리가 이미 검증했던 좌표들은 사실 다시 확인할 필요가 없다.즉, 상하좌우 이동에서 방문하게 되는 새로운 좌표들에서만 장애물 여부를 확인하면 된..
[Python 3] BOJ 14595: 동방 프로젝트 (Large) 1부터 n번까지 방이 있다.여기서 반복적으로 'x부터 y번까지의 방'을 벽을 허물어서 한 개의 방으로 만든다.이후에 총 방의 개수를 세는 문제이다. 처음에는 분리 집합으로 Union-Find를 통해 해결하려고 했다.그러나, 100만개의 방을 5000번 합치게 되면, TLE를 받는다. 여기서 앞 방과 뒤 방만 생각하고, 중간에 있는 방들을 생각하지 않아도 되는 방법을 모색했다.따라서, 검색과 gpt를 통해서 '차분 배열'을 배우게 되었다.누적 합 (Prefix Sum)의 일종으로서, 시작점과 끝점에 더하고 빼주는 것을 이용하는 알고리즘이다. 즉, x번 방과 y번 방 사이의 방은 고려하지 않고,x번째 방에 1을 더해주고, y번재 방에서 1을 뺀다.여기서 1을 더해주는 것은 오른쪽 방의 벽을 허물었다는 뜻이고..
[Python 3] BOJ 19942 다이어트 영양분 (단백질, 탄수화물, 지방, 비타민)이 일정 기준 이상 갖춰지게끔 하는 식재료들의 조합 중 가장 가격이 싼 경우를 정하는 문제였다. 만약 가격이 가장 싼 경우가 한 가지가 아닐 경우, 사전 순으로 가장 빠른 경우를 출력하는 문제였다. Brute Force와 Backtracking을 이용하여 해결하였다. DFS를 이용해 반복적인 backtracking을 통해 모든 경우에 대한 brute force를 할 수 있었다.시간 복잡도는 O(2^n)이지만, n의 크기가 최대 15이기 때문에 파이썬으로도 충분히 시간 제한 내에 들어올 수 있다. flag variable을 이용하여 영양소 최저 기준을 모두 만족하였는지 확인한다.만약 영양소 최저 기준을 만족했다면, 정답으로 들어올 수 있는지 확인한다.여기서 기존 ..
[Python 3] BOJ 1285 동전 뒤집기 비트마스킹과 브루트포스, (그리디)를 이용한 문제였다.먼저, 행을 기준으로 뒤집을 수 있는 모든 경우에 대해서 뒤집기를 실시한다.n이 20인 경우 2의 20제곱 (약 100만번) 정도의 뒤집기를 한다고 생각하면 된다.모든 경우를 다 뒤집기 때문에 브루트 포스이다.또한, 여기서 비트마스킹을 사용한다. 0부터 2^(n-1)-1까지의 숫자를 이용해서, 각 비트에 1이 있으면 뒤집기를, 없으면 뒤집기를 실시하지 않는다. for bit in range(1예컨데, n이 3개짜리인 테이블을 예시로 보자.HHTTHTHTH[표 1: 현재 테이블] 다음과 같은 3행에 뒤집기를 하고 싶다. 그렇다면 ,비트마스킹에서 '100'의 경우일 것이다.즉, 1행과 2행에서는 뒤집지 않고, 3번째 비트인 1에서만 뒤집는다.HHTTHTT..
[Python 3] BOJ 11266: 단절점 https://www.acmicpc.net/problem/11266 Articulation Point (단절점)을 이용해서 풀어야 하는 문제였다.DFS를 응용하여 풀이할 수 있었다. 타 블로그들에서도 잘 설명이 되어 있지만, 간단하게 설명해보겠다. 현재 위치해있는 정점 A 보다 늦게 탐색이 될 예정인 정점들 중에서 정점 A보다 먼저 탐색이 되는 정점으로 가는 경로가 없을 경우에 정점 A를 단절점이라고 할 수 있다.그리고, 예외적인 케이스로서 루트 노드로 시작한 노드의 자식의 수가 2개 이상이면 단절점이라고 할 수 있다. 방문하지 않은 정점으로 이동을 할 경우에는, 반복적으로 dfs를 진행하여, 제일 정점의 방문 순번이 낮은 경우를 visited에 저장한다고 생각하면 된다.import sysinput=sy..
[Python 3] BOJ 15991: 1, 2, 3 더하기 6 https://www.acmicpc.net/problem/15991 일반적인 DP 문제이다.두 개의 list를 정의하였는데, dp[n]는 1,2,3의 합으로 n을 만들 수 있는 모든 경우의 수를 정의하고, answer[n]은 대칭적으로 n을 만들 수 있는 경우의 수, 즉 문제의 정답을 의미한다.예를 들어,1 -> dp[1]= 11+1 , 2 -> dp[2]= 21+1+1, 1+2, 2+1, 3 -> dp[3]=4 와 같이 정의되고,  1 -> answer[1]= 11+1, 2 -> answer[2] =21+1+1, 3 -> answer[3] =21+1+1+1, 2+2, 1+2+1 -> answer[4]=3 와 같이 정의된다. 여기서, dp[i]의 값은 dp[i-1], 1 의 조합, dp[i-2], 2 의..

티스토리툴바