전체 글

[알고리즘] 트라이(Trie) 트라이(TRIE) 트라이(TRIE)retrieval 문자열의 집합을 표현하는 트리를 말한다모든 문자열은 다른 문자열의 접두어가 아니라고 가정 부분 문자열 검사ba가 abac의 부분 문자열인가?두개 접두사의 최장 공통 접두어 찾기abac와 ac의 최장 공통 접두어는?사전적 순서로 정렬된 k번째 접미사 찾기abac의 3번째 접미사는? : abac, ac, bac, c (정답 : bac) 각 간선은 하나의 문자에 대응한다같은 노드에 나오는 간선들은 같은 레벨을 갖지 않음각 문자열은 단말 노드에 대응한다 Compressed Trie노드들과 간선들을 부분 문자열로 압축(= 접미어 트리(Suffix Tree)) 문자열 S = {xabxac}에 대한 접미어 트리 발생하는 문제점 해결책하..

[알고리즘] 다익스트라(Dijkstra) 다익스트라(Dijkstra) : 하나의 선택한 정점에서 각 정점까지 갈 수 있는 최단거리를 구하는 알고리즘 경로를 찾을 때 가중치가 있으면 사용하자 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657import java.util.Arrays; /** * Dijkstra : 하나의 선택한 정점에서 각 정점까지 갈 수 있는 최단거리를 구하는 알고리즘 * * Greedy 방식, 음이 아닌 가중치일 경우만 사용가능 * 음의 가중치가 있는 경우 => 벨만포드 알고리즘을 통해서 구해야 한다 * 시간복잡도 O[n^2] */ public cl..

어댑터 패턴용도 : 클래스를 바로 사용할 수 없는 경우가 있음 (다른 곳에서 개발했다거나, 수정할 수 없을 때) 중간에서 변환 역할을 해주는 클래스가 필요 → 어댑터 패턴사용 방법 : 상속호환되지 않은 인터페이스를 사용하는 클라이언트 그대로 활용 가능향후 인터페이스가 바뀌더라도, 변경 내역은 어댑터에 캡슐화 되므로 클라이언트 바뀔 필요X 클래스 다이어그램 아이폰의 이어폰을 생각해보자가장 흔한 이어폰 잭을 아이폰에 사용하려면, 잭 자체가 맞지 않는다.따라서 우리는 어댑터를 따로 구매해서 연결해야 이런 이어폰들을 사용할 수 있다 이처럼 어댑터는 필요로 하는 인터페이스로 바꿔주는 역할을 한다 이처럼 업체에서 제공한 클래스가 기존 시스템에 맞지 않으면?기존 시스템을 수정할 것이 아니라, 어댑터를 활용해 유연하게..

디자인 패턴유형 분류Cretional Pattern객체 생성에 관련객체 생성 시, 유연성 높이고 코드의 유지보수에 도움Structural Pattern프로그램 구조 관련자료구조 or 인터페이스 등 프로그램 구조 설계에 활용Behavioral Pattern반복적으로 사용되는 객체들의 상호작용 패턴화 학습할 패턴어댑터(Adapter) 패턴프로토 타입(Prototype) 패턴싱글톤(Singleton) 패턴컴포지트(Composite) 패턴데코레이터(Decorator) 패턴퍼사드(Facade) 패턴프록시(Proxy) 패턴옵저버(Observer) 패턴커맨드(Command) 패턴책임 연쇄(Chain of Responsibility) 패턴중재자(Mediator) 패턴방문자(Visitor) 패턴팩토리 메소드(Factor..

[알고리즘] 동적 계획법(Dynamic Programming) & 메모이제이션(Memoization) 동적 계획법이란? 주어진 문제를 세분화시키고, 최적의 해법을 찾아내기 위한 방법 DP를 이용하면 중복된 부분을 제거하여 다시 계산하지 않아도 되는 장점이 있다. 이는 연산의 효율을 높여주는데 큰 역할을 한다. 이를 알아보기 위해서는 '피보나치 수열'로 알아보기 쉽다 피보나치 수열은 위와 같은 구조로 '재귀 함수'를 통해 구현된다. 즉, index 0과 1을 제외하고 f(n) = f(n-1) + f(n-2)로 정의가 가능하다. 하지만, index의 값이 커질수록 호출되는 재귀함수가 무궁무진하게 커지는 문제가 발생한다. 지금처럼 빨간 원으로 묶인 부분은, 완전히 똑같은 부분을 다시 불러오는 모습을 볼 수 있..

[백준 9663] N-Queen 문제 출처 : 링크 백트래킹을 활용하는 가장 유명한 백준 문제가 N-Queen이다. 체스에서 존재하는 '퀸'이 서로 공격할 수 없도록 체스판에 둘 수 있는 방법의 수를 구해야 한다. 퀸은 체스에서 가장 강력한 존재로, 자신이 위치한 곳에서 가로 줄, 세로 줄, 대각선을 모두 움직일 수 있다. N * N 체스판에서 퀸들이 서로 공격하지 못하는 위치를 찾는 것이 문제의 핵심이다. 체스판이라 2차원 배열로 접근해야 된다고 생각할 수 있지만, 이 문제는 1차원으로 해결이 가능하다.왜냐하면, 어차피 하나의 열에 퀸 하나를 두면, 해당 열에는 추가로 더 놓을 수 없기 때문이다.(즉, 하나의 열마다 하나의 퀸만 놓으면 됨) 우선 Queen에 대한 Class를 만들자 123456789c..

[알고리즘] 백트래킹(Backtracking) [알고리즘] 백트래킹(Backtracking) 백트래킹이란?모든 경우의 수를 검색하는 알고리즘'특정조건'을 만족하는 모든 경우의 수를 찾고 싶을 때 유용DFS(깊이 우선 탐색)을 기반으로 하는 알고리즘 후보해 집합에서 최적해 집합을 찾아내는 문제에 적용 가능!후보해 : 정답이 될 가능성이 있는 모든 조합최적해 : 문제의 답으로 기준을 만족하는 해 DFS는 Brute Force 알고리즘으로, 재귀함수를 통해 그냥 모두 다 검사해서 찾음 DFS와 백트래킹의 차이점은 '가지치기'가지치기를 이용하기 때문에 DFS처럼 모든 경우의 수를 확인하는 알고리즘은 아님! 가지치기는 어렵게 생각하지말고 반복문에서 break나 return에 해당한다고 생각하자 백트래킹 대표 문제..

[Java] GUI를 활용한 직원 관리 프로그램 해당 프로젝트 정보(Github) : 링크 목표 - Singleton 디자인 패턴을 활용한 안정적인 객체 생성- Client와 Server 사이에서 IP/Port 연결을 통해 원활한 소켓 통신 구현- 소켓 통신 시, 객체 단위 전달을 위한 직렬화(Serializable) 구현- Client 생성 시 Thread를 활용한 구현- 프로그램 시각화를 위한 GUI의 JFrame 활용 클래스 다이어그램 Employee직원 정보 객채 : 번호, 이름, 직책, 거주지 정보 CRUD를 위한 getter와 setter 생성 및 서버 출력에 필요한 toString 메소드 오버라이드 소켓에서 객체 단위 전송을 위한 직렬화(Serializable) 적용 IEmpMgr구현이 필요..

[백준 1931] 회의실 배정 문제 출처 : 링크 그리디 알고리즘에 해당하는 문제다. 즉, 최적의 해를 찾기 위한 알고리즘을 짜야하는데, 반례를 잘 찾아가면서 풀어야 한다. 작년에 풀었던 문제였지만, 다시 풀어봐도 반례를 다 생각하지 못해서 상당히 고생했다ㅠ 가장 많은 회의를 진행할 수 있도록 하려면, 가장 빨리 끝나는 회의를 찾아야 한다는 걸 알아내야 한다. 이런 문제는 그냥 많이 풀어보면서 어느정도 감을 익히는게 제일 좋지 않은가 싶다... 나는 우선 class를 하나 만들어 회의에 대한 시작 시간과 종료 시간을 저장했다. 그리고 각 회의 정보를 하나의 리스트에 저장했고, 회의 종료 시간이 빠른 순으로 보기 위해서 Comparator를 활용해 종료시간 오름차순으로 정렬했다. (이때 int값을 활용해서..

[swexpert 2819] 격자판의 숫자 이어 붙이기 문제 출처 : 링크 4x4 말판에 0~9까지 임의의 수가 작성된다. 지나온 말판도 다시 지나갈 수 있는 것이 포인트. dfs로 접근하는데 방문하는 부분을 따로 지정하지 않으면 될 것 같다. 말판에서 총 6번 움직이면서 (처음에 시작하는 지점 포함) 총 7자리의 수가 만들어지면 저장한다 이때 모든 경우의 수를 진행하면서, 중복되는 부분은 없애고 총 몇 가지 수를 만들 수 있는 지 구해야하는 문제다. 숫자를 int로 만들지 않고, 그냥 문자열로 받아서 저장하는 방식으로 접근했다. HashSet에 저장하면, 중복되는 부분은 추가로 저장하지 않으므로 이 문제에서 사용하면 좋을 것 같아서 적용해봤다. 만약 ArrayList나 배열을 사용한다면, 저장 전에 조..