백준

https://www.acmicpc.net/problem/9251 ACAYKP CAPCAK 두 문자열에서 일부를 추출하여 부분 수열을 만들 때 가능한 가장 긴 공통 수열은 ACAK이다. 2차원 배열 DP(Dynamic Programming)을 사용하여 풀이할 수

https://www.acmicpc.net/problem/11779 📌 문제에서 요구하는 것은 크게 3가지 이다. 1. 출발 노드에서 도착 노드까지의 최소 비용 2. 최소 비용을 갖는 경로에 포함된 노드의 개수 3. 최소 비용을 갖는 경로의 노드 방문 순서

https://www.acmicpc.net/problem/2104 특정 구간의 합 * 특정 구간의 최소값의 최대값을 구해야한다. 💡 기존 아이디어 두 가지의 세그먼트 트리를 만들어서 최댓값을 구하면 된다고 생각했다. 1. 구간의 합을 담은 세그먼트 트리 2.

https://www.acmicpc.net/problem/6549 히스토그램 그래프에서 찾을 수 있는 가장 큰 직사각형의 넓이를 구하는 문제이다. 해당 문제는 여러 방법으로 생각할 수 있지만, 나는 분할 정복 방식을 선택했다. 💡 아이디어 아...........

https://www.acmicpc.net/problem/16946 BFS활용 문제이다. 벽 타일에서 이동할 수 있는 타일의 수를 구하는 문제이다. 이 때, 각각의 벽에 대해서 BFS를 진행하니 시간 초과가 발생했다. 💡아이디어 각 벽에서 이동할 수 있는 영역

https://www.acmicpc.net/problem/2252 각 학생들에게 우선순위가 부여될 때, 줄을 세울 수 있는 방법을 묻는 문제이다. 💡 아이디어 위상정렬을 이용하는 가장 기본적인 문제이다. 각 노드에 대한 진입차수를 저장하는 배열을 선언하고 BFS

https://www.acmicpc.net/problem/15683 브루트포스 / 백트래킹을 이용한 문제다. 풀이 아이디어를 떠올리기 보다는 구현 중에 실수하지 않는 것에 신경을 많이 써야 했다. 풀고 나니 내 코드가 뭔가.. 아름답다 라는 생각이 들어 남긴다. (잘 푼건 아니고 그냥 코드가 예쁘다는 생각이 들었다)

https://www.acmicpc.net/problem/1520 틀린 아이디어 모든 경우의 수를 구하는 것이 목표이기 때문에 BFS / DFS 방식을 사용해서 풀 수 있을 것 같았다. BFS는 최단거리를 구하는데 최적화 되어 있고, DFS는 경우의 수를 구하는데 최적화 되어 있으므로 DFS를 사용했으나, 시간초과가 발생했다. 지나온 곳을 다시 탐색하지...

https://www.acmicpc.net/problem/10972 수열을 오름차순으로 정렬할 때, 주어진 수열 다음 차례의 수열을 구하는 문제이다. 틀린 아이디어 백트래킹을 이용하여 가능한 수열을 모두 만들어보려고 했으나, N의 크기가 최대 10,000이므로 가능한 수열의 경우의 수만 10000!(팩토리얼) 이었다. 당연히 시간초과가 발생한다. 풀이...

https://www.acmicpc.net/problem/9764 틀린 아이디어 DP 문제라는 것은 쉽게 알 수 있다. 그러나, 중요한 조건이 존재한다. > 서로 다른 자연수 즉, 중복되지 않는 조합의 수를 세어야 한다. 만약, 서로 다른 자연수라는 조건이 없다면 DP 점화식 코드는 다음과 같이 작성된다. 이 코드는 특정 수를 자연수의 합으로 표현해야...

차분 배열 (Difference Array) > 배열의 특정 범위에 값을 더하거나 빼는 연산을 아주 효율적으로 처리하기 위한 알고리즘 기법 https://www.acmicpc.net/problem/19951 위 문제를 풀면서 차분 배열이라는 개념을 처음 알게되었다. 문제에서 길이가 100,000이고 100,000명의 조교가 연병장의 크기만큼 흙을 덮는 ...