전체 글

[알고리즘] 최단 경로 구하기 - 3. 플로이드-워셜 알고리즘

| 플로이드-워셜 알고리즘 - 모든 노드의 최단 경로를 구하는 알고리즘으로 전체 간선을 인접 행렬로 표현하고 dp를 통해 최단 경로를 구하는 방식 핵심 : 전체 경로의 최단 경로 = 부분 경로의 최단 경로의 조합 - 기능 : 모든 노드 간에 최단 경로 탐색 - 특징 : 음수 가중치 Ok, 동적 계획법의 원리를 사용 - 시간복잡도 : O(V3) | 플로이드-워셜 구현하기 1 배열을 선언하고 초기화 2 노드의 각 인접 노드 경로 입력 3 점화식으로 배열 업데이트 4 음수사이클 확인 [1] 배열을 선언하고 초기화 - 각각의 노드를 Start지점으로 두고 모든 Start지점에 대한 최단 거리를 구할 예정 1 2 3 4 5 1 0 ∞ ∞ ∞ ∞ 2 ∞ 0 ∞ ∞ ∞ 3 ∞ ∞ 0 ∞ ∞ 4 ∞ ∞ ∞ 0 ∞ 5 ..

[알고리즘] 최단 경로 구하기 - 2. 벨만 - 포드

| 벨만-포드 - 가중치가 양수만 있을 때에 다익스트라를 사용했다면, - 가중치에 음수가 있을 때엔 벨만-포드를 사용한다. - 기능 : 특정 출발 노드에서 도착 노드까지의 최단 경로 탐색 - 특징 : 가중치 음수 OK, 음수 사이클 여부 판단 - 시간 복잡도 : O(VE) | 벨만-포드 구현하기 - 지난번에 구현했던 다익스트라의 우선순위 큐 버전으로 쓰면 음수도 커버가 가능한데 - 벨만-포드를 사용하게 되면 음수 사이클 여부까지 커버할 수 있다. - 구현의 순서 1 에지 배열 & 최단 경로 dp 배열 초기화 2 모든 에지를 하나씩 확인하여 최단 경로 업데이트 3 음수 사이클 여부 확인 [1] 에지 배열(또는 리스트) & 최단 경로 dp 배열 초기화 - 이 부분은 다익스트라의 노드 클래스가 간선 클래스로 ..

[알고리즘] 최단 경로 구하기 - 1. 다익스트라

| 다익스트라 - 가중치가 있는 그래프에서, 최단 경로를 구하는 알고리즘 - 핵심 : 그래프의 인접리스트와 DP를 이용 - 기능 : 출발 노드와 모든 노드 간의 최단 거리 탐색 - 특징 : 간선은 모두 양수 - 시간 복잡도 : O(ElogV) * E : 간선수, V : 정점수 | 다익스트라 구현 - 배열을 사용하는 것도 좋지만 배열 크기가 너무 클 경우를 대비해 인접 리스트를 사용 - (1),(2) 모두 기본적으로 동일하게 아래를 세팅 (1) 간선 정보 리스트 : 인접 리스트에 Node(연결된 노드, 가중치) 타입으로 저장 (2) 임시 거리 배열 : 출발지부터 노드 X까지의 현재 최소 거리를 업데이트할 배열 ㄴ start 위치는 자기 자신이므로 0으로 세팅한다. class Node{ int to; int..

[알고리즘] 백트래킹

| 백트래킹 - 모든 가능한 경우의 수 중에서 유망하지 않은 쪽은 제외하고 최적해를 구하는 방법 - 주로 재귀를 사용해서 구현한다. 유망(Promising) 가능성 있다. 가지치기(Pruning) 가능성 없는 것 제외하기 백트래킹(Backtracking) 유망하지 않은 쪽으로는 가지 않고 Back한다. | N-Queen 을 통한 백트래킹 이해 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net - N x N의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치한다고..

[스프링] OOP의 SOLID 원칙과 스프링

| 자바 웹 프로그래밍 - 동적인 웹사이트를 만들기 위해서 과거부터 지금까지 아래와 같은 역사를 거쳐왔다. CGI (Common Gateway Integerface) Servlet EJB (Enterprise Java Beans) 스프링 프로세스 단위 쓰레드 단위 비즈니스 로직을 포함 자바 기반 프레임워크 - CGI는 프로세스단위로 동적 페이지를 생성하기 때문에 자원의 효율성이 떨어졌기에 - Servlet을 통해 쓰레드단위로 동적 페이지를 생성하여 극복하고자 하였다. - EJB는 여기에 데이터의 저장 및 수정 시의 안정성을 높이고 트랜잭션 처리 기능을 추가 한 것으로 안정적인 코딩을 가능해졌지만, 코드가 너무 복잡해서 테스트 코드를 생성하는 것도 어려웠다고 한다. - 이때, Rod Johnson이라는 사..

SOLID 원칙

| OOP의 핵심 [ 지난 번 OOP 관련 포스팅 내용 요약 ] - OOP는 객체 간 상호 관계에 포커스를 맞춘 방법론으로, 추상화, 상속, 다형성, 캡슐화 4가지의 주요 특징이 있다. - 추상화는 모델링이고, 상속은 확장과 재사용성이며, 다형성은 사용 편의, 캡슐화는 정보 은닉에 해당된다. - 추상화 단계에서는 클래스 내 응집도를 높이는 게 필요하고, 상속 시에는 클래스 간 결합도에 주의해야 한다. - OOP는 풀면 참 복잡했는데, 오늘 배운 수업에서는 분류와 교체라는 단어로 그 핵심을 단순화해 설명했다. * 현업에 오래 종사했던 강사분은 스파게티 소스에 대해 언급하며, 소프트웨어를 유연하게 만들려면 객체지향 방식이 유용하다 얘기주셨다. 분류한다 코드를 적절히 잘 분류한다. -> 클래스 교체한다 필요에..

[네트워크] 네트워크의 기초 정리

보호되어 있는 글입니다.

[웹 프로그래밍] 톰캣 설치 및 이클립스 환경 설정(+톰캣 구조)

| 개요 📌 톰캣 설치하기 📌 이클립스 환경 설정하기 📌 톰캣 구조 | 톰캣 설치 순서 1️⃣ 사전에 준비할 사항 ✔️ JDK 설치 ✔️ 시스템 환경변수 JAVA_HOME 및 JDK 경로 등록 변수 값 JAVA_HOME JDK경로 Path %JAVA_HOME%\bin * 톰캣은 OS에게 JAVA_HOME 라는 변수명으로 JDK 경로를 읽어오라고 호출한다. * 이건 약속이므로 JAVA_HOME으로 미리 시스템 환경변수를 등록해주는 게 좋다. 2️⃣ 톰캣 버전 확인 후 다운로드 ✔️ 버전확인 https://tomcat.apache.org/whichversion.html Apache Tomcat® - Which Version Do I Want? Apache Tomcat® is an open source sof..

[웹 프로그래밍] 서버와 웹 서버, WAS

| 서버란? 서버란, 데이터를 저장하고, 앱 또는 앱 사이트를 구동하는데에 특화된 고성능 컴퓨터를 말한다. - 다시말해 서버란, 네트워크를 통해서 서비스를 제공하는 컴퓨터이다. - 제공하는 서비스가 무엇이냐에 따라, 아래와 같이 종류가 다양할 수 있으며, 늘 상시 전원이 켜져 있다. - 종류 : 웹 서버, HTTP 서버, 인증 서버, 그룹웨어 서버, 메일 서버, DNS서버 등등등 - 데이터 센터는 이러한 서버 컴퓨터를 관리하는 센터로, 서버가 꺼지지 않도록 쿨링 시스템을 쓰는 등의 관리를 한다. - 각 회사마다 상황에 따라 자체 서버 컴퓨터가 따로 있거나(ON-PREMISE), 클라우드 서버를 렌탈해 쓰기도 한다. ON-PREMISE CLOUD 회사 내에 데이터 센터를 구축하는 것 클라우드 서비스 제공자..

[데이터베이스 설계] Exerd를 통해 설계해보기

| Exerd를 사용해 설계해보기 - 부트캠프 실습 후 간단하게 배운 내용을 복습하고자 사용법만 간략히 정리하려고 한다. * 참고로 Exerd를 설치하는 방법은 이전 포스팅에서 다루었다. 1. 도구 설명 no 설명 비고 0 Logical / Physical 토글 버튼 1 테이블 생성 칼럼 추가 : [Alt] + [Enter] 2 - 점선 : 비식별 관계 >> pk를 추가하여 연결 - 실선 : 식별 관계 >> fk로 추가하여 연결 3 마우스 우측 클릭 후, [논리/물리 같이 보기] 버튼 터치하면 함께 보기 가능 4 도메인 및 데이터 타입 등에 대한 설명 보기 2. 데이터 타입 및 제약 조건 지정하기 (1) 하단의 데이터 타입 끌어오기 - 하단에 보면 샘플로 만들어진 데이터타입이 이미 있는데 이걸 끌어오는 ..