본문 바로가기

Develop Study/Algorithm33

(25.03.24) n개에서 k 고르기 : 재귀 백트래킹 VS 비트마스크 OO 사 코딩 테스트를 진행하면서, 기억에 남는 문제를 복기를 해서 알고리즘을 확인했다.최대한 많은 조합을 만드는 문제는 많은 알고리즘에서 발생을 했지만,만약 그 조합 중에 K개 만큼 특정 갯수가 변수로 주어진 경우에는, 불필요하게 모든 조합을 구하고, 그리고 거기서 k개의 요소를 가진 경우의 수를 모두 고르는 방식은 굉장히 비효율 적이다. 따라서 재귀 트백트래킹을 사용할 수 있지만, 이 보다 효율적인 메모리를 사용해서 재귀를 사용하지도 않고도, 순서 -> 비트로 사용하는 비트마스크 방식을 찾아 이를 적용하고 학습했다. [음료수 맛 조합 문제]여러 종류의 음료수가 주어집니다. 각 음료수는 여러 가지 맛을 가지고 있습니다. 4가지 맛이 있을 경우 음료수의 맛은 이진수(1101, 1000, etc) 로 주어.. 2025. 3. 24.
(25.01.28) DFS 알고리즘의 시간 부족 Time Limit Exceeded 해결 : 자료구조의 활용 DFS의 다중 탐색을 여러번 사용하는 경우, 반복문 단위에서 DFS 횟수를 줄여서 Time Limit을 벗어날 수 있었다.(이분탐색) 하지만 어떤 조건에 맞춱가면서 하나의 DFS를 찾아가는 알고리즘에서 발생하는 것은 탐색해야하는 데이터에 비해, 리소스가 (메모리 등)이 한정적일 때 발생할 수도 있다.즉, 하나의 깊이 탐색 자체가 너무 많은 리로스를 사용하기 때문인데,이 때, List 나 Set 처럼 백트래킹이 있는 알고리즘에서 불필요한 사용이 있을 수 있다. 이 때,  백트래킹을 진행하지 않고 조건에 만족하는 방향만 찾아게 하면서 탐색 속도를 줄이려면 어떻게 해야할까.Questionare given a list of airline tickets where tickets[i] = [fromi, toi] r.. 2025. 1. 28.
(25.01.25) DFS 알고리즘의 시간 부족 Time Limit Exceeded 해결 DFS를 통한 깊이 전체 탐색을 진행하는 알고리즘일 경우엔, 조건에 부합하는 경로가 나올때까지, DFS를 계속해서 진행하는 로직이 구현될 수 있다.이런 상황에서 탐색해야하는 구간이 커질 수록 Time Limit 이 발생할 수 있다. 이 때 활용할 수 있는 간단한 방법을 정리하고자한다.QuestionThere is a 1-based binary matrix where 0 represents land and 1 represents water. You are given integers row and col representing the number of rows and columns in the matrix, respectively.Initially on day 0, the entire matrix is la.. 2025. 1. 25.
(25.01.15) BFS 알고리즘의 메모리 부족 Memory Limit 해결 BFS 알고리즘을 활용하면서 bigint 내지는 BigIntegerdml 10^19 정도 크기 그 이상의 과학적 계산의 영역의 큰 규모의 데이터를 다룰 떄는 전체 탐색이라는 알고리즘의 특성상 리소스가 초과적으로 발생할 수 있다. 이 때는 주어진 Resource를 최대한 활용하면서 두개의 BFS를 활용하면서 제한된 리소스에서 BFS를 통해 이상적인 답을 찾아나가는 알고리즘에 대해서 좀 더 찾아보고 공부하면서 기록을 했다. QuestionThere is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are (x, y).We start at the source = [sx, sy] square and wa.. 2025. 1. 15.
(24.11.25) DP(Dynamic Programming) 과 전체탐색(BFS, DFS)에 대한 정리 DP(Dynamic Programming)은 간단하게 부분합을 사용해서 전체 합을 구하는 알고리즘이라고 넘어갔지만, 계속해서 찾아보고 알고리즘 문제를 풀어보면서  BFS와 DFS와의 구분이 애매한 것 같아서 스스로 구분하고적절하게 알고리즘을 사용하기 위해서 정리했다. 예제는 GPT를 활용해서 가장 많이 사용하는 경우를 간단하게 정리했다.DP(Dynamic Programming) & 전체 탐색DP 알고리즘모든 경로에 대해서 계산을 통해서 **“최적의 값”**을 찾기위해서 진행하는 알고리즘아무리 그 경로가 복잡하더라도 그 순서나 관련된 내용은 체크할 필요가 없이 “최적의 값” 을 향해 나가는 방식에 사용메모이제이션(Memoization) & 타뷸레이션(Tabulation)재귀를 통한 값을 캐싱하면서, 표로 .. 2024. 11. 25.
(24.11.18) BFS를 활용한 도현의 외각선 탐색 도형의 외곽선 탐색하기 알고리즘도형의 외곽선을 탐색하면서 가장 짧은 거리를 반환하는 알고리즘내부로 진입 Ximport java.util.*;class Solution { // 방향키 public int[] dx = {-1,1,0,0}; public int[] dy = {0,0,-1,1}; public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) { // 영역 지정 2배 확장 int[][] map = new int[101][101]; // 주어진 사각형 외각선 1 내부 2 설정하기 for(in.. 2024. 11. 18.
(24.11.11) BFS를 활용한 미로 최단 거리 찾기 가중치가 없는 그래프일 경우 Map> 자료구조의 graph로 BFS를 노드 단위, 또는 neighbor 단위로 활용할 수 있다. 하지만, 미로에서는 가중치가 1인 그래프에 특정 조건(막혀있을 경우 해당 경로는 X)이 있기 떄문에복잡할 수 있는 BFS 내지는 아래 비교를 위한 DFS를 좀더 다듬어서 사용할 수 있었다. 이전 DFS BFS 알고리즘에선 그 알고리즘의 플로우에 집중해서 정리를 해서 코드의 양이 길고, 효율적이지 못했기 때문에이번에는 미로에서 BFS 를 이용한 최단 거리 알고리즘을 통해서효율적으로 그래프에서 최단거리를 확인하는 방식을 정리하려고 한다.최단경로 미로찾기“최단경로” 이기 때문에 BFS를 통해서 Queue 를 통해 같은 레벨의 node(neighbors)를 반복하면서 도착지점에 부합할.. 2024. 11. 11.

티스토리툴바