빈코의 개발일지

오늘은 BFS를 활용하여 미로의 최단 경로를 구해보는 문제를 풀어볼 예정입니다. 이전 포스팅에서 풀어 본 DFS를 활용한 미로 탐색과 풀이법이 유사하기 때문에 참고하면 좋을 듯하네요😊 개요 이 문제의 핵심은 BFS 알고리즘 활용과 Queue의 원리, 지나간 경로는 다시금 못 지나가게 막는 방법, 격자의 상하좌우 확인 총 4가지가 될 것 같아요. 한번 코드로 풀어볼까요? Point📙 class Point { public int x,y; Point(int x, int y) { this.x = x; this.y = y; } } Point 클래스는 격자판에서 x축, y축을 입력할 때 사용합니다. Queue에 지나간 격자를 넣거나 빼서 사용할 때 Point 클래스를 사용하여 현재 위치를 파악할 때 사용합니다. 자..

오늘은 DFS를 활용한 미로 탐색 문제를 풀어보려고 합니다😄 개요 이 문제의 핵심은 DFS 알고리즘 활용과 상하좌우 4방향으로 이동하는 방법이 주가 될 것 같아요. 한번 코드로 풀어볼까요? 📌 사전 지식으로 DFS의 원리와 Stack이 쌓이고 pop 되는 과정을 알아야 합니다. 모르시는 분은 해당 링크를 클릭해서 확인해주세요😀 Setting📙 public class MazeSearch { static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0 ,1, 0, -1}; static int[][] board; static int result = 0; public static void main(String[] args) { MazeSearch T = new MazeSear..

오늘은 DFS 탐색 알고리즘을 사용한 동전 교환 문제를 풀어보려 합니다😊 개요 이 문제의 포인트는 DFS 탐색 알고리즘을 활용, 배열을 내림차순으로 하여 시간을 단축하였는가, 탐색하지 않아도 될 상황을 제한하였는가 총 3가지 인 것 같아요. 바로 코드를 보면서 확인해 볼게요😀 Main📙 public class ExchangeCoins { static int n, m, result = Integer.MAX_VALUE; public static void main(String[] args) { ExchangeCoins T = new ExchangeCoins(); Scanner sc = new Scanner(System.in); n = sc.nextInt(); Integer[] arr = new Integer[..

오늘은 탐색 알고리즘인 DFS를 활용하여 합이 같은 부분집합 구하기, 최대 무게 구하기, 최대 점수 구하기 총 3문제를 풀어보려고 합니다. Stack 활용을 모르신다면 이해하시기 어렵기 때문에, 관련 포스팅을 참고해 주세요😊 개요 하단에서 풀어 볼 3개의 문제는 모두 DFS의 부분 집합을 활용하는 문제입니다. 첫 번째, 합이 같은 부분집합 구하기 문제를 잘 이해하시면 나머지 2개의 문제도 비슷한 맥락이기 때문에 이해하기 쉽습니다😊 합이 같은 부분집합 구하기📙 이 문제의 포인트는 마지막 노드까지 갔을 때(부분 집합)의 총합을 구하는 방법과 각각의 부분 집합이 입력된 자연수 집합의 절반과 같은지 체크하는 것입니다. 예시에서 1, 3, 5, 6, 7, 10 집합이 주어졌고, 이 집합의 총합은 32이며 절반 값..

오늘은 지난 포스팅인 DFS & BFS 기초에 이어서 알고리즘을 활용하여 Tree 말단 노드까지의 가장 짧은 경로를 구하는 간단한 문제를 풀어 볼 예정입니다😄 개요 사실 최단 경로를 구하는 문제는 대게 BFS(넓이 우선 탐색)를 이용하여 문제를 풀지만, DFS로도 풀 수 있는 문제가 왕왕 있기 때문에 2가지 문제 풀이법 모두 진행해보려 합니다. 문제는 위 그림처럼 1번 노드에서 시작해 가장 말단 노드까지 가는 최단 경로를 구하는 문제입니다. 여기서 말단 노드는 하위 노드가 없는 노드를 뜻하며 그림에서는 4, 5, 3에 해당하겠네요! 가장 짧은 간선을 구하기 때문에 한 개의 간선만 필요한 3번 노드가 말단 노드로 지정되고, 정답은 간선의 개수이기 때문에 1이 되겠습니다😊 이전 포스팅과 마찬가지로 Node ..

오늘은 Java 알고리즘에서 빼먹을 수 없는 DFS와 BFS에 대해 알아보려고 합니다. DFS는 Depth First Search의 약자로 깊이 우선 탐색을 말하고, BFS는 Breadth First Search의 약자로 너비 우선 탐색을 말합니다. 이 둘은 그래프 자료구조에서 완전 탐색을 수행하는 탐색 기법입니다😊 개요 앞서 말씀드린 그래프를 탐색하기 위한 대표적인 알고리즘 DFS, BFS를 이해하기 위해서는 스택(Stack), 큐(Queue), 재귀(Recursive)를 먼저 알아야 합니다. 스택과 재귀를 모르신다면 링크를 클릭해서 선수 학습을 해주세요😅 재귀 함수와 스택 프레임 코딩 테스트를 준비하면서 완전탐색, DFS, Back tracking 등의 알고리즘 개념을 접하게 되고, 자연스레 스택 프..

오늘은 알고리즘 단골 문제인 피보나치 수열 풀이법에 대해 알아보려고 합니다. 피보나치 수열은 면접 현장에서 손 코딩으로 배열 또는 재귀 함수로 풀어보고 성능을 물어보기도 하기 때문에, 이번 포스팅을 통해 정확히 알고 가시면 좋을 것 같습니다😄 피보나치(Fibonacci)📘 수학에서 피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 일컫습니다. 예시로 5는 1 1 2 3 5로 표현이 되겠네요. 이런 피보나치 수열을 푸는 방법은 앞서 말씀드린 것처럼 배열로 푸는 방식과 재귀 함수로 푸는 방식으로 나뉩니다. 사실 배열로 푸는 방식이 성능면에서도 좋고 풀이 방법도 간단하지만, 재귀함수로 풀어보라는 회사도 많기 때문에 두 가지 풀이 방법을 모두 숙지하시는 게 좋습니다. 성..

코딩 테스트를 준비하면서 완전탐색, DFS, Back tracking 등의 알고리즘 개념을 접하게 되고, 자연스레 스택 프레임(Stack frame)도 접하게 되었습니다. 스택 프레임은 알고리즘 문제에 자주 출시되기 때문에, 이번 기회에 개념을 정확히 알고 넘어가시면 좋을 것 같아요😊 스택 프레임📗 스택 프레임이란 메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매개 변수가 저장되는 영역입니다. 스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸합니다. 함수가 호출되면 스택에는 함수의 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소 값, 함수에서 선언된 지역 변수 등이 저장됩니다. 이렇게 스택 영역에 차례대로 저장되는 함수의 호출 정보를 스택 프레임(stack fra..

이전 포스팅에서는 JPA의 고급 매핑에 대해 알아보았다. 이번 포스팅에서는 프록시와 즉시 로딩, 지연 로딩 및 영속성 전이에 대해 알아보려고 한다😄 개요 객체는 객체 그래프로 연관된 객체들을 탐색한다. 그런데 객체가 데이터베이스에 저장되어 있으므로 연관된 객체를 마음껏 탐색하기는 어렵다. JPA 구현체들은 이 문제를 해결하려고 프록시라는 기술을 사용한다. 프록시를 사용하면 연관된 객체를 처음부터 데이터베이스에 조회하는 것이 아니라, 실제 사용하는 시점에 데이터베이스에서 조회한다. 하지만 자주 함께 사용하는 객체들을 조인을 사용해서 함께 조회하는 것이 효과적이다. JPA는 즉시 로딩과 지연 로딩이라는 방법으로 둘을 모두 지원한다. 또한, JPA는 연관된 객체를 함께 저장하거나 함께 삭제할 수 있는 영속성 ..

MCMS(Media Content Management System)는 솔루션 사업이기 때문에 이전 프로젝트와 비슷한 프로젝트를 맡게 되었습니다. 내년부터는 새로운 솔루션 사업과 신사업에 투입되는 것으로 얘기하고 있어서 아마 이번 후기가 마지막 MCMS 프로젝트 후기가 되지 않을까 싶습니다😄 개요 지금까지의 MCMS처럼 이번 프로젝트도 시청각 자료들을 관리하는 웹 페이지를 만드는 일이었습니다. 다만, 대부분 혼자 작업에 투입되었는데 이번 프로젝트는 생각보다 새로운 기능들이 많이 추가되어서 그만큼 인원도 많이 충당되었어요. 기존에는 카테고리 별 시청각 리스트와 상세화면에서 다양한 파일들을 확인하고 다운로드하는 그런 시스템이었고, 이번에는 추가적으로 차트와 마이페이지 기능들이 덧붙었습니다. 또한, 빠른 검색을..