전체 글65 [ 최단경로 알고리즘 ] 다익스트라 & 플로이드 워셜 오늘은 최근 다시 공부한 다익스트라 알고리즘과 플로이드 워셜 알고리즘을 정리해보려합니다. 정리해놓지 않고..오랜만에 보니 헷갈리는 부분들이 생겨 오늘은 꼭 정리하고 넘어가고자 합니다. 먼저 다익스트라 알고리즘입니다. 다익스트라 알고리즘은 특정 노드에서 다른 모든 노드로 가는 최단 경로를 구할 수 있는 알고리즘입니다. * 단 음수의 가중치를 가지는 간선이 포함된 경우에는 구할 수 없습니다 * 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문입니다. 기본적인 다익스트라 알고리즘의 원리는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 것 입니다. 다익스트라 알고리즘의 동작 원리는 다음과 같습니다. 1. 출발 노드.. 2023. 1. 15. 디자인 패턴 ( 팩토리 & 전략 & 옵저버 ) ** 이 글은 ' 면접을 위한 cs 전공지식 노트 ' 책을 기반으로 정리한 글 입니다 ** 🙋🏻♀️ 팩토리 패턴 - 객체를 사용하는 코드에서 객체 생성 부분을 떼어내 추상화한 패턴 - 상속관계에 있는 두 클래스에서 상위 클래스가 중요한 뼈대를 결정 & 하위 클래스가 객체 생성에 관한 구체적 내용 결정 /* Online Java Compiler and Editor */ abstract class Coffee{ /*상위 추상 클래스*/ public abstract int getPrice(); @Override public String toString(){ return "Hi this coffee is " + this.getPrice(); } } class CoffeeFactory{ /* 객체 생성 클래스 .. 2023. 1. 13. [ 다이나믹 프로그래밍 = 동적계획법 ] 알고리즘 내용 정리 😃 동적계획법 ( Dynamic Programming ) - 전체 문제를 작은 부분 문제로 나누어 푸는 방법 - 한 번 계산한 결과를 재활용하는 알고리즘 ( 중복되는 부분을 한번만 계산하도록 ) 😃 동적 계획법 조건 1. 최적 부분 구조 : 부분 문제의 최적을 이용해 지존의 답을 구하는 구조! 더보기 2. 중복되는 부분 문제 더보기 😃 동적 문제 방식 1. Memoization - 하향식 - 중복되는 계산을 한번한 뒤 메모해두는 방식 - cache에 저장하고 보통 재귀함수 사용 - 배열 값을 -1로 모두 초기화, 배열 값이 음수이면 계산한 후 저장, 양수이면 그대로 활용 2. Tabulation - 상향식 - 반복문 기반으로 해결하는 방식 ( 누적시켜 전체 큰 문제를 해결 ) 😃 동적 계획법 문제 접근방.. 2023. 1. 12. [ 완전탐색 ] 알고리즘 내용 정리 ✅ 완전탐색 - 모든 경우의 수를 다 고려해야 하는 경우를 의미 - 시간복잡도가 큰 편! ✅ 완전탐색 문제 판별법 1. 하나의 경우마다 따져야 할 게 명확한 경우 2. 어떤 상태를 구성하고, 그 상태가 특정 조건을 만족하는지 검토해야 하는 등의 문제 3. 나올 수 있는 경우의 수가 모두 탐색할 수 있을 만큼 크기가 적을 때 ✅ 완전 탐색 문제 접근 방식 1. 모든 경우를 생성할 수 있는 방법을 생각 2. 각각의 경우에 대해 그 문제의 조건을 만족하는지 체크 ( 문제에 따라 다름 ) ✅ 완전탐색 방법 1. BruteForce : 반복문과 조건문을 이용하여 처음부터 끝까지 탐색하는 방법 2. 비트마스크 3. 순열 : 순열 시간 복잡도는 O(n!) 4. 재귀를 호출 -> 백트래킹 5. DFS / BFS ✅ 고.. 2023. 1. 12. 디자인 패턴과 프로그래밍 패러다임_싱글톤 패턴 ** 이 글은 ' 면접을 위한 cs 전공지식 노트 ' 책을 기반으로 정리한 글 입니다 ** 🙋🏻♀️ 디자인 패턴 - 프로그램을 설계할 때 발생했던 문제점들을 객체 간의 상호 관계 등을 이용하여 해결할 수 있도록 하나의 규약 형태로 만들어 놓은 것! 🎯 싱글톤 패턴 - 하나의 클래스에 오직 하나의 인스턴스만 가지는 패턴 - 하나의 클래스를 기반으로 여러 개의 개별적 인스턴스 생성이 가능하지만, 그렇게 하지 않고 하나의 클래스 기반 하나의 인스턴스만 만드는 패턴 - 데이터베이스 연결 모듈에 가장 많이 사용 class Singleton{ private static class singleInstanceHolder{ private static final Singleton INSTANCE = new Singlet.. 2023. 1. 4. 오브젝트 _ 코드로 이해하는 객체지향 설계( 3장 ) ** 본 글은 오브젝트(조영호) 책을 읽고 작성자가 정리한 글입니다. ** 3장 : 역할, 책임 협력 🙋🏻♀️ 객체 지향의 본질 - 협력하는 객체들의 공동체를 창조하는 것 1.협력 ( 영화 예매 시스템 참조 ) ✅ - 애플리케이션의 제어 흐름은 어떤 하나의 객체에 의해 통제되지 않고 다양한 객체들 사이에 균형 있게 분배되는 것이 일반적 - 메시지 전송은 객체 사이의 협력을 위해 사용할 수 있는 유일한 커뮤니케이션 수단 더보기 메시지 전송 : 하나의 객체는 메시지를 전송함으로써 다른 객체에 접근한다. 메시지는 메시지 이름과 인자의 두 부분으로 구성된다. EX. 증언하라(어제, 왕국) 메시지 전송은 수신자와 메시지의 조합이다. 메시지는 메시지 이름과 인자의 조합이므로 메시지 전송은 수신자, 메시지 이름, .. 2022. 12. 9. 이전 1 2 3 4 ··· 11 다음
