차분 배열 (Difference Array)
차분 배열 Difference Array 배열의 특정 범위에 값을 더하거나 빼는 연산을 아주 효율적으로 처리하기 위한 알고리즘 기법 위 문제를 풀면서 차분 배열이라는 개념을 처음 알게되었다. 문제에서 길이가 100,000이고 100,000명의 조교가 연병장의 크기만큼 흙을 덮는 ...
TAG
#알고리즘
23개의 기록
서로 다른 자연수의 합 (백준, Java)
틀린 아이디어 DP 문제라는 것은 쉽게 알 수 있다. 그러나, 중요한 조건이 존재한다. 서로 다른 자연수 즉, 중복되지 않는 조합의 수를 세어야 한다. 만약, 서로 다른 자연수라는 조건이 없다면 DP 점화식 코드는 다음과 같이 작성된다. 이 코드는 특정 수를 자연수의 합으로 표현해야...
다음 순열 (백준, Java)
수열을 오름차순으로 정렬할 때, 주어진 수열 다음 차례의 수열을 구하는 문제이다. 틀린 아이디어 백트래킹을 이용하여 가능한 수열을 모두 만들어보려고 했으나, N의 크기가 최대 10,000이므로 가능한 수열의 경우의 수만 10000! 팩토리얼 이었다. 당연히 시간초과가 발생한다. 풀이...
내리막 길 (백준, Java)
틀린 아이디어 모든 경우의 수를 구하는 것이 목표이기 때문에 BFS / DFS 방식을 사용해서 풀 수 있을 것 같았다. BFS는 최단거리를 구하는데 최적화 되어 있고, DFS는 경우의 수를 구하는데 최적화 되어 있으므로 DFS를 사용했으나, 시간초과가 발생했다. 지나온 곳을 다시 탐색하지...
감시 (백준, Java)
브루트포스 / 백트래킹을 이용한 문제다. 풀이 아이디어를 떠올리기 보다는 구현 중에 실수하지 않는 것에 신경을 많이 써야 했다. 풀고 나니 내 코드가 뭔가.. 아름답다 라는 생각이 들어 남긴다. 잘 푼건 아니고 그냥 코드가 예쁘다는 생각이 들었다
동물원 (백준, Java)
큰 조건은 2가지이다. 가로, 세로에 사자를 연속하여 배치할 수 없다. 사자를 배치하지 않는 경우도 포함한다. 🥲 틀린 풀이 점화식에 대한 아이디어가 떠오르지 않아서 경우의 수를 모두 생각하려고 했다. 사자가 0마리인 경우, 1마리인 경우 n마리인 경우를 구하려 했지만 배열의...
백준 2565번 : 전깃줄 (Java)
🔌 백준 2565번 : 전깃줄 서로 교차하지 않게 전깃줄을 설치할 수 있는 최대 개수를 구하는 문제 🔗 백준 2565번 - 전깃줄 ❌ 아이디어를 떠올리지 못함 내가 제일 자신 없는 DP문제였고, 핵심 아이디어를 떠올리지 못했다. 문제 태그를 확인해 DP를
배낭 문제 (Knapsack Problem)
DP를 잘 하는 사람은 여행 가방도 잘 쌀까?
유니온 파인드 (Union-Find)
노드를 보관하고 있으니, 부모님은 찾아가시길 바랍니다.
벽 부수고 이동하기 4 (백준, Java)
BFS활용 문제이다. 벽 타일에서 이동할 수 있는 타일의 수를 구하는 문제이다. 이 때, 각각의 벽에 대해서 BFS를 진행하니 시간 초과가 발생했다. 💡아이디어 각 벽에서 이동할 수 있는 영역
위상 정렬 (Topological Sort)
기술을 배우고 문제를 해결한 과정을 정리한 기록입니다.
줄 세우기 (백준, Java)
각 학생들에게 우선순위가 부여될 때, 줄을 세울 수 있는 방법을 묻는 문제이다. 💡 아이디어 위상정렬을 이용하는 가장 기본적인 문제이다. 각 노드에 대한 진입차수를 저장하는 배열을 선언하고 BFS
부분배열 고르기 (백준, Java)
특정 구간의 합 특정 구간의 최소값의 최대값을 구해야한다. 💡 기존 아이디어 두 가지의 세그먼트 트리를 만들어서 최댓값을 구하면 된다고 생각했다. 1. 구간의 합을 담은 세그먼트 트리 2.
히스토그램에서 가장 큰 직사각형 (백준, Java)
히스토그램 그래프에서 찾을 수 있는 가장 큰 직사각형의 넓이를 구하는 문제이다. 해당 문제는 여러 방법으로 생각할 수 있지만, 나는 분할 정복 방식을 선택했다. 💡 아이디어 아...........
LCS(Longest Common Subsequence) (백준, JAVA)
ACAYKP CAPCAK 두 문자열에서 일부를 추출하여 부분 수열을 만들 때 가능한 가장 긴 공통 수열은 ACAK이다. 2차원 배열 DP Dynamic Programming 을 사용하여 풀이할 수
가장 긴 증가하는 부분 수열 2 (백준, Java)
문제는 간단하다. 수열에서 오름차순으로 증가하는 부분 수열 중 가장 긴 수열의 길이 수열 요소의 개수 를 구해야 한다. DP를 사용하여 간단한 점화식을 세울 수 있다. 💡 아이디어 각 인덱
다익스트라 알고리즘 Dijkstra algorithm
🚀 다익스트라 알고리즘 Dijkstra Algorithm 출발 노드에서 다른 모든 노드까지의 최단 거리를 찾는 알고리즘 다익스트라는 DFS / BFS와 무엇이 다를까? ✅ 간단하게 생각하면 다익스트라는 노드 간의 이동 비용이 필요할 때 사용할 수 있다.
문자열 폭발 (백준, Java)
❌ 틀린 풀이 코드 난이도에 비해서 문제가 너무 쉽다고 생각했으나, 메모리 초과가 발생했다. 이유는 replace 매서드가 호출될 때마다 새로운 메모리를 생성하기 때문. ✅ StringBuilde
별 찍기 - 11 (백준, JAVA)
재귀 함수 이용 별 찍기 문제이다. ❌ 기존 풀이 작은 삼각형을 하나 출력하는 함수를 만들고, 삼각형이 출력되지 않는 위치의 패턴을 찾으려고 했다. 그림과 같이 각 삼각형의 위치를 숫자로 카운팅하
이진 탐색 (Binary Search)
🚀 이진 탐색 Binary Search 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘으로, 탐색 범위를 절반씩 줄여가며 원하는 값을 찾는다. 📌 이진 탐색 개념 정렬된 배열에서만 사용 가능 탐색 범위를 절반씩 줄여 빠르게 값을 찾음 시간 복잡도: O
최소비용 구하기 2 (백준, JAVA)
📌 문제에서 요구하는 것은 크게 3가지 이다. 1. 출발 노드에서 도착 노드까지의 최소 비용 2. 최소 비용을 갖는 경로에 포함된 노드의 개수 3. 최소 비용을 갖는 경로의 노드 방문 순서
플로이드-워셜 알고리즘 Floyd-Warshall Algorithm
🚀 플로이드-워셜 알고리즘 Floyd-Warshall Algorithm 모든 노드 간 최단 거리를 구하는 알고리즘으로, 동적 계획법 DP 을 활용하여 최적의 경로를 찾는다. 🔎 플로이드 워셜 알고리즘이란? DP 동적 계획법 을 이용하여 모든 노드 간의 최소
DFS / BFS 기본 원리
DFS(Depth First Search) 깊이 우선 탐색 BFS(Breadth First Search) 너비 우선 탐색 계속 헷갈려서 글로 정리한다. DFS : 특정 노드와 연결된 노드를 파고들어 더 이상 연결된 노드가 없을 때 까지 이동한다. BFS : 특정…