2024/07 49

[PS/Tip] BFS vs DFS

이 내용에 대해선 앞으로 보완해나갈 예정입니다. 많은 문제를 풀어보면서 최대한 정리해보겠습니다.BFS vs DFSBFSBFS는 시작 정점에서 가까운 정점을 찾는데 적합하다큐를 이용하여 가까운 원소들부터 탐색하기 때문최단 거리 경로를 찾는데 적합하다.BFS에서는 특정 정점을 방문할 경우, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장된다.BFS는 현재 경계에서 인접한 모든 정점을 방문하므로 BFS에 의해 생성된 검색 트리는 짧고 넓은 편이며, 많은 메모리를 필요로 한다DFSDFS는 대체로 시작 정점에서 멀리 있는 정점을 찾을 때 적합하다.재귀적인 풀이 방식에 적합하다 (후입선출의 스택 구조를 사용하기 때문)백트래킹 방식의 PS 풀이에서 적합하다.모든 경우를 하나 하나 다 탐색해야 하는 경우 적합하다..

PS/Tip 2024.07.13

[Algorithm/Graph] 깊이 우선 탐색(DFS, Depth-First scrach)

깊이 우선 탐색(DFS) 깊이 우선 탐색(DFS)는 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다.더 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다. 이러한 그래프 탐색 방법을 백트래킹(backtracking)이라고 한다.DFS 구현BFS에서는 방문하지 않은 정점을 저장하기 위해 큐를 사용했다.큐를 사용하기 때문에 가장 가까이에 있는 정점부터 접근이 가능했다.하지만 DFS는 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하기 때문에, 스택을 사용한다.후입 선출 속성을 갖는 스택을 사용하기 때문에 현재 정점과 인접한 정점들을 재귀적으로 이동하면서 방문할 때 사용하기에 적합하다.PS에서 그래프를 나타내야하는 경우 인접 행렬..

Algorithm/Graph 2024.07.12

[Algorithm/Graph] 너비 우선 탐색(BFS, Breadth-First Scrach)과 구현(에지 리스트, 인접 행렬, 인접 리스트)

그래프 순회 문제그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제EX) 사무실에서 출발하여 주변 거래처를 순회하며 결재를 하는 경우그래프에서 특정 정점을 찾기 위한 용도로 사용될 수 있기 때문에 그래프 탐색 문제라고도 부른다.여러 그래프 탐색 알고리즘이 존재하고, 각각은 서로 다른 순서로 모든 정점을 방문하다.너비 우선 탐색(BFS, Breadth-First Scrach)시작 정점을 경계(frontier)에 추가하는 것으로 시작경계는 이전에 방문했던 정점들에 의해 구성된다그리고 현재 경계에 인접한 정점을 반복적으로 탐색한다같은 거리에 있는 정점들의 방문 순서는 임의로 정해도 되지만, 멀리 있는 정점보다는 가까운 정점을 먼저 방문해야 한다.BFS는 모든 정점에 대해 자식 정점을 손자 정점보..

Algorithm/Graph 2024.07.12

[Spring] 스프링 핵심 원리 이해(1) - 예제 만들기

스프링 핵심 원리 이해1 - 예제 만들기비즈니스 요구사항과 설계회원회원을 가입하고 조회할 수 있다.회원은 일반과 VIP 두 가지 등급이 있다.회원 데이터는 자체 DB를 구축할 수 있고, 외부 시스템과 연동할 수 있다. (미확정)주문과 할인 정책회원은 상품을 주문할 수 있다.회원 등급에 따라 할인 정책을 적용할 수 있다.할인 정책은 모든 VIP는 1000원을 할인해주는 고정 금액 할인을 적용해달라. (나중에 변경 될 수 있다.)할인 정책은 변경 가능성이 높다. 회사의 기본 할인 정책을 아직 정하지 못했고, 오픈 직전까지 고민을 미루고 싶다. 최악의 경우 할인을 적용하지 않을 수 도 있다. (미확정)요구사항을 보면 회원 데이터, 할인 정책 같은 부분은 지금 결정하기 어려운 부분이다. 그렇다고 이런 정책이 결..

[Spring] 객체 지향 설계와 스프링(3) - 좋은 객체 지향 설계의 5가지 원칙(SOLID)

좋은 객체 지향 설계의 5가지 원칙(SOLID)클린코드로 유명한 로버트 마틴이 좋은 객체 지향 설계의 5가지 원칙을 정리SRP: 단일 책임 원칙(single responsibility principle)OCP: 개방-폐쇄 원칙 (Open/closed principle)LSP: 리스코프 치환 원칙 (Liskov substitution principle)ISP: 인터페이스 분리 원칙 (Interface segregation principle)DIP: 의존관계 역전 원칙 (Dependency inversion principle)SRP 단일 책임 원칙(Single responsibility principle)한 클래스는 하나의 책임만 가져야 한다.하나의 책임이라는 것은 모호하다.클 수 있고, 작을 수 있다.문맥..

[Spring] 객체 지향 설계와 스프링(2) - 좋은 객체 지향 프로그래밍이란?

좋은 객체 지향 프로그래밍이란?객체 지향 특징추상화캡슐화상속다형성객체 지향 프로그래밍객체 지향 프로그래밍은 컴퓨터 프로그램을 명령어의 목록으로 보는 시각에서 벗어나 여러개의 독립된 단위, 즉 "객체"들의 모임으로 파악하고자 하는 것이다. 각각의 객체는 메시지를 주고받고, 데이터를 처리할 수 있다. (협력)객체 지향 프로그래밍은 프로그램을 유연하고 변경이 용이하게 만들기 때문에 대규모 소프트웨어 개발에 많이 사용된다.유연하고, 변경이 용이?레고 블럭 조립하듯이키보드, 마우스 갈아 끼우듯이컴퓨터 부품 갈아 끼우듯이컴포넌트를 쉽고 유연하게 변경하면서 개발할 수 있는 방법다형성다형성의 실세계 비유실세계와 객체 지향을 1:1로 매칭X그래도 실세계의 비유로 이해하기에는 좋음역할과 구현으로 세상을 구분운전자 - 자동..

[Spring] 객체지향 설계와 스프링(1) - 스프링 탄생 배경

스프링의 역사과거에 EJB라는 기술이 있었는데, 이 EJB를 대체하는 JPA라는 새로운 표준이 등장했다.로드 존슨이라는 사람이 EJB의 문제점 지적하면서EJB 없이도 충분히 고품질의 확장 가능한 애플리케이션을 개발할 수 있음을 보여주고, 30,000라인 이상의 기반 기술을 예제 코드로 선보임여기에 지금의 스프링 핵심 개념과 기반 코드가 들어가 있음BeanFactory, ApplicationContext, POJO, 제어의 역전, 의존관계 주입책 출간 직후 Juergen Hoeller(유겐 휠러), Yann Caroff(얀 카로프)가 로드 존슨에게 오픈소스 프로젝트를 제안스프링의 핵심 코드의 상당수는 유겐 휠러가 지금도 개발스프링 이름은 전통적인 J2EE(EJB)라는 겨울을 넘어 새로운 시작이라는 뜻으로 ..

[HTTP] HTTP 헤더(1) - 일반 헤더

HTTP 헤더 개요HTTP 헤더(복습)header-field = field-name ":" OWS field-value OWS (OWS:띄어쓰기 허용)field-name은 대소문자 구문 없음HTTP 헤더의 용도HTTP 전송에 필요한 모든 부가정보예) 메시지 바디의 내용, 메시지 바디의 크기, 압축, 인증, 요청 클라이언트, 서버 정보, 캐시 관리 정보...표준 헤더가 너무 많음https://en.wikipedia.org/wiki/List_of_HTTP_header_fields필요시 임의의 헤더 추가 가능helloworld: hihiHTTP 헤더 분류 - RFC2616(과거)General 헤더: 메시지 전체에 적용되는 정보, 예) Connection: close요청 메시지 / 응답 메시지 이런 거에 구분 ..

WEB/HTTP 2024.07.10

[HTTP] HTTP 상태코드 (1XX, 2XX, 3XX, 4XX, 5XX)

HTTP 상태코드HTTP 상태코드란?클라이언트가 보낸 요청의 처리 상태를 응답에서 알려주는 기능1xx (Informational): 요청이 수신되어 처리중2xx (Successful): 요청 정상 처리3xx (Redirection): 요청을 완료하려면 추가 행동이 필요4xx (Client Error): 클라이언트 오류, 잘못된 문법 등으로 서버가 요청을 수행할 수 없음5xx (Server Error): 서버 오류, 서버가 정상 요청을 처리하지 못함만약 미래에 모르는 상태 코드가 나타나면?클라이언트가 인식할 수 없는 상태코드를 서버가 반환하면?클라이언트는 상위 상태코드로 해석해서 처리미래에 새로운 상태 코드가 추가되어도 클라이언트를 변경하지 않아도 됨예)299 ??? -> 2xx (Successful)45..

WEB/HTTP 2024.07.09

[Java] 16. 예외 처리(Exception handling)(5) - 예외 되던지기, 연결된 예외

예외 처리(5) - 예외 되던지기, 연결된 예외예외 되던지기(exception re-throwing)앞서 말했던 것처럼 한 메서드에서 발생할 수 있는 예외가 여럿인 경우 몇 개는 try-catch문을 통해서 자체적으로 처리하고, 나머지는 선언부에 지정하여 호출한 메서드에서 처리하도록 함으로써 양쪽에서 나눠서 처리되도록 할 수 있다.심지어 단 하나의 예외에 대해서도 예외가 발생한 메서드와 호출한 메서드 양쪽에서 처리하도록 할 수 있다.이것은 예외를 처리한 후에 인위적으로 다시 발생시키는 방법을 통해서 가능한데, 이것을 예외 되던지기라고 한다.먼저 예외가 발생할 가능성이 있는 메서드에서 try-catch문을 사용해서 예외를 처리해주고 catch문에서 필요한 작업을 행한 후에 throw문을 사용해서 예외를 다..