BOJ(5)
-
[백준][JAVA] 1305번: 광고
https://www.acmicpc.net/problem/1305문제해석문자열에서 가장 짧은 패턴의 길이를 찾는 문제KMP 알고리즘과 가장 짧은 패턴은 (문자열길이 - LSP배열에서의 마지막 요소)라는 것을 알면 쉽게 풀 수 있다.풀이LPS 배열이란?LPS(Longest Prefix which is also Suffix) 배열은 주어진 문자열의 접두사(prefix)와 접미사(suffix)가 일치하는 가장 긴 부분 문자열의 길이를 저장한 배열입니다.참고: https://mode-creative.tistory.com/25 [알고리즘] KMP알고리즘 (문자열 검색 알고리즘)KMP 알고리즘 이란주어진 텍스트 문자열에서 특정 패턴 문자열이 등장하는 위치를 효율적으로 찾는 데 사용됩니다. KMP 알고리즘은 패턴 ..
2024.06.17 -
[백준][c++] 2206번: 벽 부수고 이동하기
2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 해석 N*M 배열의 1,1 에서 N,M까지의 최단경로를 찾아내는 문제 0은 벽이 없고 1은 벽이 있는 칸 벽은 최대 한번까지 부술수 있다. 풀이 큐를 이용한 BFS(너비 우선 탐색)으로 최단경로를 찾았습니다. 코드 #include #include #include #include #include using namespace std; //입력부 static int n,m; static int least = INT_MAX; //이동 횟수..
2024.02.19 -
[백준][c++] 12738번: 가장 긴 증가하는 부분 수열 3
문제 해석 주어진 수열 안에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제 입니다. 풀이 먼저, 숫자의 개수 N을 입력받습니다. N개의 숫자를 입력받아 numbers 벡터에 저장합니다. lis라는 벡터를 생성하고 첫번째 숫자를 추가합니다. 이 벡터는 가장 긴 증가하는 부분 수열을 저장하는 데 사용됩니다. numbers 벡터의 두 번째 원소부터 마지막 원소까지 순회하며, 현재 숫자가 lis의 마지막 원소보다 크면 lis에 추가합니다. 이는 현재 숫자가 lis에 포함될 수 있음을 의미합니다. 만약 현재 숫자가 lis의 마지막 원소보다 작다면, 현재 숫자가 들어갈 수 있는 lis 내의 위치를 이진 탐색으로 찾아서 그 위치의 값을 현재 숫자로 업데이트합니다. 이는 lis를 최대한 작은 값으로 유지하면서 길..
2024.01.10 -
[백준][c++] 1918번: 후위표기식
https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 문제 해석 중위 표기식을 후위표기식으로 변환하여 출력하는 문제입니다. 후위 표기식변환은 스택(stack)을 이용합니다. 풀이 각 문자에 대해 다음과 같은 작업을 수행합니다 문자가 문자나 숫자(즉, 피연산자)인 경우, 결과 문자열에 바로 추가합니다. 문자가 여는 괄호 '('인 경우, 이를 스택에 넣습니다. 문자가 닫는 괄호 ')'인 경우, 스택에서 여는 괄호 '('가 나올 때까지 문자를 pop하..
2024.01.08 -
[백준][c++] 11003번: 최솟값 찾기
문제 해석 각 슬라이딩 윈도우 크기 내에서 최소값을 출력하는 문제입니다. 풀이 벡터와 덱을 이용해 해결했습니다. 각 D(i)에 대해 다음을 반복합니다. 현재 추가되는 A(i)와 dq.back(덱에서 가장 큰 수)를 비교하여 A(i)가 더 작다면 dq.back을 pop함 A(i)를 인덱스와 함께 back에 추가 dq.front가 윈도우 크기를 벗어났다면 pop함 dq.front를 출력 코드 #include #include #include using namespace std; int main() { //입출력 최적화 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //입력부 int n,l; cin >> n >> l; vector a(n); ..
2024.01.05