본문 바로가기

전체 글282

[Algorithm] LCS (Longest Common Substring / Subsequence) 알고리즘 LCS란? LCS는 최장 공통 문자열(Lognest Common Substring) 또는 최장 공통 부분 수열(Longest Common Subsequence)을 의미한다. 전자는 연속된 문자열에 대한 것을 뜻하고 후자는 연속되지 않은 문자열이 포함될 수 있다. 최장 공통 문자열 (Longest Common Substring) 최장 공통 문자열을 구하는 과정은 다음과 같다. 문자열 A의 i번째 문자와 문자열 B의 j번째 문자를 비교한다. 두 문자가 같다면 ( A[i] == B[j] ) dp[i][j]에 dp[i-1][j-1] + 1을 대입한다. 두 문자가 다르다면 ( A[i] != B[j] ) dp[i][j]의 값을 0으로 설정한다. 과정중에 구한 최댓값이 최장 공통 문자열의 길이가 된다. 공통 문자열은.. 2022. 5. 1.
2580. 스도쿠 (Python) 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 백트래킹을 사용하여 문제를 해결할 수 있다. 풀이 과정은 다음과 같다. 먼저 입력을 받으면서 0이 들어있는 좌표를 리스트에 담아둔다. 첫 번째 0부터 시작하여 1~9까지의 숫자를 넣어본다. 이때 가로, 세로 그리고 사각형에 해당 숫자가 들어있는지를 체크한다. 숫자를 넣을 수 있다면 이제 다음 0이 들어있는 좌표로 이동하여 똑같은 과정을 반복한다. 0이 들어있는 모든 좌표에 숫자를 넣었다면 출력을 해주고 프로그램을 종료한다. 코드 import sys # 백트.. 2022. 5. 1.
17472. 다리 만들기 2 (Python) 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 다음과 같은 과정을 통해서 문제를 해결한다. 먼저 각 섬에 번호를 붙여주는 작업을 한다. 각 섬에서 위, 아래, 왼쪽, 오른쪽으로 탐색하여 다리를 만들어본다. 섬에서 다른 섬으로 가는 다리 중에서 가장 짧은 거리를 갖고 있는 다리의 정보를 저장한다. 저장한 다리를 다리의 길이를 기준으로 오름차순 정렬한다. 크루스칼 알고리즘을 사용하여 최소 신장 트리를 구성한다. 사용된 다리의 길이들을 합한 값을 출력한다. 코드 import sys imp.. 2022. 4. 30.
2513. 통학버스 (Python) 2513번: 통학버스 첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2 ≤ N ≤ 30,000이다. 두 번째 정수 K는 1 ≤ K ≤ 2,000이며, 통학버스의 정원 www.acmicpc.net 풀이 학교의 위치부터 가장 멀리 떨어져 있는 아파트부터 먼저 방문해서 태울 수 있는 만큼 학생들을 태워가며 버스의 이동거리를 계산해주면 된다. 이때 학교를 기준으로 왼쪽에 있는 아파트와 오른쪽에 있는 아파트로 나누어 왼쪽으로 한 번 작업을 수행하고 오른쪽으로 한 번 작업을 수행해주면 된다. 학교로부터 가장 멀리 떨어져 있는 아파트부터 먼저 방문해야 하므로 왼쪽 아파트의 경우에는 아파트 위치를 기준으로 최소힙으로 구성하였고 오른쪽 아.. 2022. 4. 30.
2550. 전구 (Python) 2550번: 전구 N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은 www.acmicpc.net 풀이 LIS를 사용하여 해결하는 문제다. LIS는 여기를 참고하자. 문제는 여기에서 LIS의 길이뿐만 아니라 LIS에 포함되는 원소까지 구해야 한다. 일단 LIS를 구하는 대상이 되는 배열은 n번의 스위치가 전구 리스트에서 몇 번째에 있는지를 나타내는 인덱스 리스트이다. 문제의 예제를 보면 스위치 리스트 [2, 4, 1, 5, 3]은 각각 전구 리스트에서 [4, 0, 2, 1, 3] 인덱스에 존재한다. 따라서 [4, 0, 2, 1, 3]에 대해서 LIS를 구하고 각각에 .. 2022. 4. 28.
[자료구조] Swift로 구현하는 Queue (큐) 큐의 개념 큐는 아래의 그림과 같이 한 쪽 끝에서는 자료의 삽입 연산만 가능하고 반대쪽 끝에서는 삭제만 가능한 자료구조이다. 이러한 특성을 가리켜 선입선출(FIFO: First In First Out)이라고 한다. 대표적인 예로 마켓에서 계산을 위해 계산대 앞에서 줄을 서서 기다리고 있는 사람들을 떠올리면 된다. 가장 먼저 도착한 사람이 먼저 계산을 할 수 있고 마지막에 도착하는 사람은 제일 끝에서 자신의 차례를 기다린다. 큐에는 선형큐, 원형큐 그리고 우선순위 큐등 여러 종류가 있는데 여기서는 가장 기본적인 선형큐에 대해서 알아본다. 큐에서 사용되는 연산 큐에서 사용되는 연산의 종류는 다음과 같다. count : 큐에 들어있는 자료의 개수 isEmpty : 큐가 비어있는 지를 체크하기 위한 연산 enq.. 2022. 4. 28.
1781. 컵라면 (Python) 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 풀이 그리디하게 현재 시간에서 풀 수 있는 문제의 리스트 중 가장 많은 컵라면 수를 얻을 수 있는 문제를 풀어 컵라면을 얻도록 하면 된다. 이때 현재 시간은 1에서부터가 아닌 제일 큰 데드라인부터 1씩 줄여가면서 풀 수 있는 문제에 대하여 컵라면 수를 우선순위 큐에 넣고 가장 큰 수를 꺼내어 풀면 된다. 문제의 예제를 보면 가장 큰 데드라인은 6이다. 그렇기 때문에 시간은 6부터 시작한다. 현재 시간 6에서 풀 수 있는 문제는 7번이 있다. 7번을 풀고 얻을 수 있는 컵.. 2022. 4. 27.
11054. 가장 긴 바이토닉 부분 수열 (Python) 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 최장 증가 부분 수열(LIS)을 활용하여 해결하는 문제다. LIS는 이 링크를 참고하자. LIS를 구하는 방법에는 dp를 사용하는 방법과 이분 탐색을 사용하는 방법이 있다. 이 문제는 dp를 사용하여 해결하면 된다. A 배열의 각 원소까지 증가 부분 수열을 만들었을 때의 길이를 구한다. 위와 같은 array가 있을 때 dp 배열의 의미는 각 인덱스까지의 증가 부분 수열 중 가장 긴 증가 부분 수열의 길이를 의미한다. 이렇게 한 번 dp를 구하고 이번에는 배열을 뒤집어서 한 번 .. 2022. 4. 26.
7453. 합이 0인 네 정수 (Python) 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 풀이 두 가지 방식으로 풀었는데 기본적으로 적용되는 것은 A, B, C, D 이렇게 4개의 배열을 두고 각각 더하는 것이 아니라, A 배열과 B 배열의 원소를 합한 결과(이하 AB라고 표기) 그리고 C 배열과 D 배열의 원소를 합한 결과(이하 CD라고 표기) 이렇게 두 개로 나누어 구한다. 이때 AB의 원소와 CD의 원소의 합이 0이 되려면 두 값의 부호가 반대여야 한다(ex. AB: 29, CD: -29). (1) Dict를 사용한 풀이 먼저.. 2022. 4. 25.

티스토리툴바