Spring Boot 외부 API 테스트 코드를 짜보자! [MockWebServer vs WireMock]

❓ Mock 서버를 사용하는 이유 Spring Boot Github 소셜 로그인 구현하기 [ RestTemplate · WebClient · FeignClient 를 비교해보자 ] Github OAuth 인증 흐름과 사전 준비 Github 인증 흐름은 다음과 같다. 1. https://github.com/login/oauth/authorize?client_id={발급받은 client_id} 로 이동하는 링크를 사용자가 클릭한다. 2. 사용자는 아래와 같은 화 yinq.tistory.com REST API 요청을 할 수 있도록 하는 RestTemplate · WebClient · FeignClient 클래스를 활용하여 외부 API 요청을 통해 기능을 구현했었다. 테스트 코드를 짜기 위한 방법을 찾아보니, ..

Spring Boot Github 소셜 로그인 구현하기 [ RestTemplate · WebClient · FeignClient 를 비교해보자 ]

Github OAuth 인증 흐름과 사전 준비 Github 인증 흐름은 다음과 같다. 1. https://github.com/login/oauth/authorize?client_id={발급받은 client_id} 로 이동하는 링크를 사용자가 클릭한다. 2. 사용자는 아래와 같은 화면이 나타나는 화면으로 이동하고, Github 인증을 한다. 3. 인증을 성공하면 {설정한 콜백 URL}?code={인증코드} 로 code 값을 쿼리 파라미터 형태로 보내준다. 4. 쿼리 파라미터로 전달된 code를 서버에서 받고, https://github.com/login/oauth/access_token 으로 {client_ID, client_Secret, code}를 담아 POST 요청을 한다. 5. 깃허브 측에서 acc..

Dispatcher Servlet은 어떻게 동작할까?

DispatcherServlet 은 Servlet 인터페이스를 구현한, HTTP 프로토콜로 들어오는 모든 요청을 먼저 받아 처리하는 Front Controller 이다. Servlet 이란? Java 언어를 기반으로, 클라이언트가 보내는 HTTP 요청을 처리하고 응답하는 역할을 담당하는 인터페이스 이다. public interface Servlet { void init(ServletConfig config) throws ServletException; ServletConfig getServletConfig(); void service(ServletRequest req, ServletResponse res) throws ServletException, IOException; String getServlet..

Swagger API 적용 시, Controller 코드가 너무 더러워진다.. 분리해보자

Swagger 를 사용하면, API 문서를 자동으로 구성해주며 엔드포인트를 테스트 할 수 있다는 장점이 있다. @Tag , @Operation , @ApiResponses 어노테이션을 사용하면 스웨거 문서에 부가적인 설명을 추가적으로 넣을 수 있어서 API 문서를 이해하는데 도움을 줄 수 있다. @RestController @RequestMapping("/api/v1/posts") @RequiredArgsConstructor public class PostApiController { private final PostService postService; @Tag(name = "Post", description = "게시글 관련 API") @Operation(summary = "게시글 조회", descrip..

Dto Validation 예외 처리에 AOP를 적용해보자!

기존 방식 implementation 'org.springframework.boot:spring-boot-starter-validation' 위 validation 라이브러리를 사용하면 Controller 에서 @RequestBody 어노테이션으로 매핑하는 Request Dto 의 필드 유효성을 검사할 수 있다. public class UserCreateRequest { @Email(message = "올바른 이메일 형식이 아닙니다. '@' 를 포함시켜주세요.") private String email; @Length(min = 8,message = "비밀번호는 최소 8자 이상입니다.") private String password; } 위와 같이 매핑되는 필드에 validation에서 제공하는 어노테이션을..

테스트 코드 커버리지 분석 도구 Jacoco를 적용해보자!

Jacoco 란? Java Code Coverage 의 줄임말로, 코드 커버리지 분석을 위한 라이브러리이다. ❓ 코드 커버리지란? 소프트웨어의 테스트 케이스가 얼마나 충족되었는지를 나타내는 지표 중 하나이다. 1. 라인 커버리지 : 코드 한 줄이 한 번 이상 실행된다면 충족된다. 2. 결정 커버리지 : 브랜치 커버리지라고도 불린다. 모든 조건식의 내부 조건이 true/ false 를 가지게 되면 충족한다. 3. 조건 커버리지 : if 조건문 안의 개별 조건식이 false 인경우와 true인 경우 모두 실행되었을 때 충족한다. 결정 커버리지보다 더 detail한 커버리지이다. 적용해보자 적용 전 build.gradle plugins { id 'java' id 'org.springframework.boot'..

@ControllerAdvice 는 어떻게 동작하는 것일까?

📌 예외 처리 방식 프로젝트를 진행하면서, 내가 주로 했던 예외처리 방법은 다음과 같다. Enum 타입의 ErrorCode 정의 @AllArgsConstructor @Getter public enum ErrorCode { DUPLICATE_USERNAME(HttpStatus.CONFLICT, "이미 존재하는 사용자명 입니다."); private HttpStatus httpStatus; private String message; } Http 상태 코드와 에러 발생 시 전달할 메세지 정보가 담긴 Enum 타입의 ErrorCode 를 정의한다. RuntimeException 을 상속하는 AppException을 정의 @Getter public class AppException extends RuntimeExc..

NL 조인의 원리

조시형님의 친절한 SQL 튜닝을 읽고 개인적으로 공부한 내용을 정리한 글입니다. NL 조인은 Nested Loop 조인의 약자로 중첩 루프 문과 같은 방법으로 조인이 이루어진다. 위 두 테이블를 사원 번호로 조인한다고 가정해보자. 프로그래밍 식으로 로직을 구현해보면 다음과 같이 할 수 있다. for(int i=0;i= '19960101' AND e.부서코드 = 'Z123' AND c.관리사원번호 = e.사원번호 AND c. 최종주문금액 >= 20000 위와 같은 쿼리를 실행 후, ROWS | OPERATION 5 |NESTED LOOPS 3 |TABLE ACCESS BY INDEX ROWID OF 사원 2780 | INDEX RANGE SCAN OF 사원_X1 5 | TABLE ACCESS BY INDE..

Chapter 7. 객체 분해

조영호님의 오브젝트를 읽고 제 머릿속에 있는 내용들을 정리하며 작성한 글입니다. 프로시저 추상화와 기능 분해 💡 프로시저는 반복적으로 실행되거나 거의 유사하게 실행되는 작업들을 하나의 장소에 모아놓음으로써 로직을 재사용하고 중복을 방지할 수 있는 추상화 방법이다. 전통적인 기능 분해 방법은 시스템을 구성하는 최상위 기능을 정의하고 작은 단계의 하위 기능으로 분해해 나가는 방법을 사용한다. 💡 세분화된 마지막 하위 기능이 프로그래밍 언어로 구현가능한 수준이 될 때까지 계속 된다. 하향식 프로시저 추상화를 통해 만든 프로그램은 다음과 같은 구성이 된다. 최상위 기능(){ 세부기능1(); 세부기능2(); 세부기능3(); .. } 최상위 기능을 수행하기 위한 여러개의 세부기능이 호출되어 원하는 최상위 기능을 수..

Where 조건 절에서 Between 과 Like

조시형님의 친절한 SQL 튜닝을 읽고 개인적으로 공부한 내용을 정리한 글입니다. Between 과 Like의 스캔 범위 차이 Between 과 Like 는 범위 검색을 할 때 활용될 수 있는데, 언뜻 비슷해보이지만 효율적인 측면에서 살펴보면 다르게 동작한다. 예를 들어, 학생 테이블에 생년월 칼럼과 학점 칼럼이 있고 [생년월 + 학점] 이 인덱스라고 가정해보자. 1995년생이면서 학점이 'B'인 레코드들을 검색하기 위해서는 1️⃣ Between 의 경우 SELECT * FROM 학생 WHERE 생년월 BETWEEN "199501" AND "199512" AND 학점 = 'B'; 2️⃣ Like 의 경우 SELECT * FROM 학생 WHERE 생년월 LIKE "1995%" AND 학점 = 'B'; 와 같..

Where 조건 절에서 Between 과 in 의 차이

조시형님의 친절한 SQL 튜닝을 읽고 개인적으로 공부한 내용을 정리한 글입니다. Between 과 In 조건절의 인덱스 스캔 범위 비교해보기 위와 같이, DEPTNO 와 JOB 으로 인덱스를 구성했다고 가정해보자. SELECT * FROM TABLE WHERE DEPTNO BETWEEN 10 AND 30 AND JOB = 'B' 위와 같은 쿼리가 실행되면 어떻게 될까? 먼저, DEPTNO가 10이면서 JOB이 'B' 인 레코드에서 탐색을 시작하여 DEPTNO 가 30이면서 JOB이 'B'가 아니게 되는 레코드 까지 탐색할 것이다. 수직적 탐색은 한번 이루어지지만, 수평적 탐색이 많은 레코드를 탐색하게된다. 반면에, SELECT * FROM TABLE WHERE DEPTNO IN (10,20,30) AND..

Chapter 6. 메시지와 인터페이스

조영호님의 오브젝트를 읽고 제 머릿속에 있는 내용들을 정리하며 작성한 글입니다. 메시지와 메서드 💡 메시지란, 객체가 다른 객체에게 유일하게 접근할 수 있는 방법이다. 자바 문법을 예로 들면 아래와 같은 것이 메시지 전송이다. 수신자.오퍼레이션명(인자); [ ex. condition.isSatisfiedBy(screening) ] ❓ 메세지와 메서드는 그러면 같은거 아니야? 만약, 수신자 객체가 인터페이스 형태가 아닌 구현체라면 맞는 말이 될 수 있다. 하지만, 🚨 수신자 객체가 인터페이스로 정의되어있다면, 해당 메시지를 어떻게 구현하느냐에 따라 실제 실행되는 프로세스가 달라진다. 따라서, 💡 메서드는 수신자 객체가 메시지를 받아, 실제로 실행되는 프로세스(함수)를 메서드라고 부른다. 메시지를 전송하는 ..

배치 I/O와 인덱스를 믿고 쿼리에 ORDER BY를 생략하면 안되는 이유

조시형님의 친절한 SQL 튜닝을 읽고 개인적으로 공부한 내용을 정리한 글입니다. 인덱스의 비효율적인 랜덤 I/O 엑세스 인덱스는 큰 테이블에서 소량 데이터를 추출할때 유용하다고 배웠다. 인덱스로 레코드에 접근하는 경우, 인덱스와 연결된 해당 레코드가 존재하는 블록 정보를 통해서 레코드에 접근해야하기 때문에 랜덤 I/O 로 접근해야하고 이 랜덤 I/O가 많아지면, 전체 테이블을 풀 스캔해서 시퀀셜 엑세스로 접근하는게 비용이 더 적어질 수 있기 때문이다. 💡 이러한 성능 비효율을 어느정도 감소시키기 위해, 이전 인덱스를 통해 접근했던 테이블 블록 정보를 저장해두었다가 일치하면 바로 접근하는 캐싱 방법을 사용하긴하지만 인덱스로 정렬된 레코드마다 다른 블록을 가리키면 효과를 보기 힘든 방법이다. 그래서 고안해낸..

Chapter 5. 책임 할당하기

조영호님의 오브젝트를 읽고 제 머릿속에 있는 내용들을 정리하며 작성한 글입니다. 책임 주도 설계 데이터를 중심으로 설계하게되면 유연한 설계를 하기 힘들다. 애초에, '데이터' 라는 것은 객체의 구체적인 정보이고, 이는 구현에 해당한다. 따라서, 데이터 중심적 설계는 객체의 구현부에 초점을 맞추고 설계 한다는 의미이다. 그리고, 데이터를 중점으로 객체 간 협력을 생각하게 되면 외부 객체에게 자신의 데이터 정보를 넘겨주는 것이므로 캡슐화를 방해하게된다. 결과적으로, 구현을 중점으로한 설계는 캡슐화를 저해하고 응집도는 낮추고 결합도는 높임으로서 변화에 취약한 설계가 된다. 💡 따라서, 객체 지향의 핵심인 협력, 책임, 역할 중 가장 중요한 책임 을 중점으로 설계하는 것이 유연한 설계를 할 수 있게 해준다. [..

인덱스 튜닝

조시형님의 친절한 SQL 튜닝을 읽고 개인적으로 공부한 내용을 정리한 글입니다. 인덱스를 통해 레코드를 찾아가는 과정 먼저, 인덱스를 활용할 수 있는 인덱스 테이블이 캐싱되어 있는지 확인한다. 캐싱되어 있다면, 인덱스 테이블에서 인덱스 조건에 맞는 레코드를 찾는다. 그러면, 해당 조건에 맞는 실제 디스크 상 레코드의 위치 정보를 파악할 수 있다.(ROWID) 실제 접근해야하는 디스크 상 레코드의 위치는 일반적으로 블록으로 관리하므로, 해당 블록이 이미 버퍼에 캐싱되어 있는지 확인하고 있다면 캐싱된 블록에 접근해서 가져온다. 만약, 그렇지 않다면 실제 디스크로 접근한다. 버퍼에서는 테이블 블록 위치 값을 해싱하여 고유한 값으로 변경 후 관리한다. 그 과정에서, 해싱 계산이 필요하므로 바로 주 메모리 위치를..

인덱스 컬럼 결정과 가공

조시형님의 친절한 SQL 튜닝을 읽고 개인적으로 공부한 내용을 정리한 글입니다. 인덱스 스캔 데이터를 찾는 방법은 크게 2 가지로 나눌 수 있다. 1. 테이블 전체 스캔 2. 인덱스 스캔 테이블 전체 스캔은 말 그대로, 테이블 데이터가 저장되어 있는 블록 전체를 스캔한다. 인덱스 스캔은 인덱스로 설정한 기준에 따라 일정량을 스캔한다. ❓ 인덱스 스캔 방식이 항상 유리할까? 그렇지 않다. 💡 인덱스 스캔 방식은 큰 테이블에서 소량의 데이터를 찾고자 할때 유용하다. 예로, 전체 테이블 스캔을 진행하면 버퍼 캐시에 데이터가 존재하지 않을 시, 모든 레코드를 탐색하므로 오랜 시간이 소요될 수 있다. 하지만, 한번 가져오고 난 뒤에는 해당 테이블과 관련한 데이터는 물리적 I/O 없이 탐색할 수 있다. 인덱스 스캔..

SQL 처리 과정과 I/O

조시형님의 친절한 SQL 튜닝을 읽고 개인적으로 공부한 내용을 정리한 글입니다. SQL 처리 과정 SQL파싱과 최적화 1️⃣ SQL 파싱 사용자로부터 SQL을 전달받으면 SQL 파서가 파싱을 진행한다. 💡 SQL 문을 이루는 개별 구성 요소를 분석하여 파싱 트리를 생성한다. 💡 그리고 전달 받은 SQL 문에서 문법적 오류 (사용할 수 없는 키워드 사용 등) 나 의미상 오류(존재하지 않는 테이블 혹은 컬럼 사용 등)가 존재하는지 확인한다. 2️⃣ SQL 최적화 💡 옵티마이저는 다양한 실행 경로를 생성해서 비교한 후, 가장 효율적인 하나를 선택한다. 그렇게 선택한 경로를 실행 가능한 코드 또는 프로시저 형태로 포맷팅한다. 실행 계획과 비용 MySQL 서버로 요청된 쿼리는 결과는 동일하지만 그 결과를 만들어 ..

Chapter 4. 설계 품질과 트레이드오프

조영호님의 오브젝트를 읽고 제 머릿속에 있는 내용들을 정리하며 작성한 글입니다. 협력, 책임, 역할 그리고 설계 품질 협력은 객체들 간 메시지를 주고받으며 진행되는 상호작용이다. 책임은 객체가 수행하는 행동이다. 역할은 책임들의 집합이다. 협력, 책임, 역할 할당이 잘 되어야 바람직한 객체 지향 설계가 가능해진다. 💡 그 중에서도 책임이 잘 할당되는 것이 중요하다. 🚨 역할은 책임의 집합이기 때문에, 책임의 품질에 의존하게 된다. 협력 역시, 책임이 잘 할당되지 못하면 효율적으로 할 수 없게된다. ❓ 책임을 어떤 식으로 할당해야할까? 비슷한 책임끼리 하나의 목적을 위해 협력하는 것 끼리 모아두는 높은 응집도와 다른 책임끼리 분리하는 낮은 결합도를 만족하도록 하는 것이 좋다. 그래야만, 변경이 일어났을 때..

Chapter 3. 역할, 책임, 협력

조영호님의 오브젝트를 읽고 제 머릿속에 있는 내용들을 정리하며 작성한 글입니다. 객체 지향에서 가장 중요한 것은 💡 역할, 책임, 협력이다. 클래스, 상속, 지연 바인딩과 같은 개념은 구현에 초점이 맞추어져 있기 때문에, 애플리케이션의 기능을 구현하기 위해 어떤 협력이 필요하고 협력을 위해 어떤 역할과 책임이 필요한지 고민을 하는 것이 더 중요하다. 1️⃣ 협력 객체들이 애플리케이션의 기능을 구현하기 위해 수행하는 상호작용을 말한다. 두 객체의 협력은, 하나의 객체가 다른 객체에게 도움을 요청할 때 시작된다. 객체는 다른 객체의 상세한 내부 구현에 직접 접근할 수 없으므로, 💡 메시지 전송을 통해 협력한다. 만약 다른 객체의 내부 구현에 접근하여 동작한다면, 객체의 자율성을 훼손하는 행위이다. 따라서, ..

Chapter 2. 객체지향 프로그래밍

조영호님의 오브젝트를 읽고 제 머릿속에 있는 내용들을 정리하며 작성한 글입니다. 객체 지향 프로그래밍을 할 때, 유념해야할 부분은 다음과 같다. 어떤 클래스가 필요한지 고민하기 전에 어떤 객체들이 필요한지 고민해야한다. 코드로서 바라보기 전에 기능이 동작되는 메커니즘을 잘 생각하라는 의미인 것 같다. 객체를 고립된 존재로 바라보지 말고 협력에 참여하는 협력자로 바라보아야 한다. 무작정 결합도를 줄이려고 노력하기 보다 효율적으로 협력하기 위한 방법을 고민하는 것이 필요하다. 클래스의 경계를 잘 구분 지어야 한다. Chapter 1에서도 많이 설명했듯이, 객체는 자신의 필드를 자신이 관리하도록 해야하며 그러기 위해서는 캡슐화를 통해 외부에 공개하지 않는 것이 좋다. 외부에서 접근이 가능한 메서드를 통해 간접..

Chapter 1. 객체, 설계

조영호님의 오브젝트를 읽고 제 머릿속에 있는 내용들을 정리하며 작성한 글입니다. 변경에 취약한 코드 public class Theater { private TicketSeller ticketSeller; public Theater(TicketSeller ticketSeller) { this.ticketSeller = ticketSeller; } public void enter(Audience audience) { // 관람객 가방에 초대권이 있다면? if (audience.getBag().hasInvitation()) { Ticket ticket = ticketSeller.getTicketOffice().getTicket(); // 티켓 제공 audience.getBag().setTicket(ticket..

대규모 트래픽을 감당할 수 있는 시스템 설계를 위한 기초 지식

도서 가상 면접 사례로 배우는 대규모 시스템 설계 기초 를 보고 정리한 글입니다. 대규모 사용자를 감당할 수 있는 시스템을 설계하기 위한 지식들에 대해서 살펴보자. 📌 RDBMS vs NoSQL RDBMS는 자료를 테이블과 열, 칼럼으로 표현한다. 그리고 SQL을 이용해 테이블에 있는 데이터를, 그 관계에 따라 JOIN 하여 합칠 수 있다. 💡 정형화 된 스키마에 따라 구조화되어 저장되기 때문에, 데이터의 일관성과 무결성을 보장할 수 있다. NoSQL은 대량의 데이터를 처리하는데 특화되어 있다. 💡 데이터의 구조가 비정형이거나 아주 많은 양의 데이터를 저장할 필요가 있을 때 사용하면 좋다. 📌 Scale Up vs Scale Out Scale Up 은 서버에 고사양 자원을 추가하는 행위이고, Scale ..

equals() 와 hashcode()

equals() 와 hashcode() 메서드의 역할과 관계에 대해서 생각해보자. 1️⃣ 동일성과 동등성 일반적으로 동일성은 메모리상 동일한 위치에 있는지를 판단하고, 동등성은 두 데이터를 논리적으로 같은 데이터로 취급할 수 있는가를 판단한다. 자바의 데이터 타입은 원시 타입(Primitive Type)과 참조 타입(Reference Type) 데이터 두 종류로 나눌 수 있다. JVM의 메모리 구조에는 스택 영역과 힙 영역이 존재하는데, 원시 타입의 경우 스택 영역에 값으로서 관리되지만, 참조 타입의 경우 힙 영역에서 생성되고 스택 영역에서는 힙 영역의 위치로 데이터를 관리한다. public class Main { public static void main(String[] args) { int port ..

Hash 자료구조와 해시 충돌

Hash Table 이란 Hash Table은 데이터를 key-value 형식으로 보관하여 검색 · 삽입 · 삭제를 O(1) 시간 복잡도로 수행할 수 있는 자료구조이다. Hash Table은 key 값을 통해 데이터를 다루기 때문에, key 값은 고유해야한다. 이러한 고유한 key 값을 만드는 작업은 해시 함수가 담당하는데, 대표적으로는 key 값의 ASCII 값을 합하여 만드는 간단한 방법이 있다. 이러한 해시 함수가 key를 만드는 과정에서, 의도하지 않게 우연히 key 값이 일치하는 경우가 발생할 수 있는데 💡 이를 해시 충돌이라고 한다. 해시 충돌이 발생하면, key 값이 중복되어 데이터가 사라질 수 있다. 따라서 해시 충돌이 발생하면 대처해야한다. 대표적인 방법으로는 체인법 (Seperate C..

병합 정렬 (Merge Sort) 을 구현해보자

정렬을 할 수 있는 방법은 여러가지가 있다. 대표적으로 다음과 같은 방법이 있다. 💡 정렬의 종류와 방식 1. 버블 정렬 : 2개의 원소를 계속 비교해나가며 값이 큰 원소가 앞에 있는 경우 위치를 교환한다. 제일 큰 값(오름차순의 경우)을 제일 뒤로 보내어 최종적으로 정렬된다. 시간 복잡도는 O(N^2)으로 볼 수 있다. 만약 한번 순회했을 때 두 원소간 위치가 변한 적이 없다면 순회를 빠져나가는 방식으로 최적화를 할 수 있다. 2. 선택 정렬 : 원소들을 순회하여 가장 작은 값을 찾은 뒤(선택), 제일 앞 원소와 위치를 바꿈으로서 작은 값이 계속 앞으로 이동하면서 최종적으로 정렬된다. 시간 복잡도는 O(N^2)으로 볼 수 있다. 3. 삽입 정렬 : 2번째 원소부터 시작해서 N번째 원소까지 N-1까지의 ..

Linked List 구현해보기

리스트에는 연속하는 메모리 공간에 저장되어 있는 ArrayList와 각각의 데이터안에 다음 데이터에 대한 정보를 갖고 있어 연결되는 LinkedList가 있다. 각 자료구조의 특징은 다음과 같다. 1️⃣ ArrayList 1. 데이터가 연속적으로 나열되어 있어, 특정 인덱스의 데이터에 접근하는 경우 O(1) 로 접근할 수 있다. 2. 선형 탐색의 경우 O(n), 정렬되어 있을 때 이분탐색의 경우 O(logN) 으로 접근할 수 있다. 3. 중간 위치에 데이터를 삽입 · 삭제 하는 경우, 나머지 원소들의 위치를 옮겨야 하기 때문에 O(N) 이다. 2️⃣ LinkedList 1. 특정 인덱스에 위치한 원소에 접근하는 경우에, 순회를 해서 찾아야 하므로 O(N) 이다. 2. 단일 연결 리스트의 경우, 시작 부분..

가상 메모리 관리를 위한 기법

도서 쉽게 배우는 운영체제와 강의 운영체제-반효경 를 보고 정리한 글입니다. 📌 가상 메모리란? 가상 메모리는 크기가 다른 물리 메모리에서 일관되게 프로세스를 실행할 수 있는 기술이다. 현대 메모리 관리의 가장 큰 특징은 물리 메모리의 크기와 프로세스가 올라갈 메모리의 위치를 신경쓰지 않고 프로그래밍 하도록 지원한다. 물리 메모리의 크기와 상관없이 프로세스에 커다란 메모리 공간을 제공하는 기술을 가상 메모리라고 한다. ❓ 이론적으로 가상 메모리는 무한대의 크기인데, 어떻게 가능한 것일까? 가상 메모리 시스템에서는 물리 메모리의 내용 중 일부를 하드디스크의 일부 공간인 스왑 영역으로 옮긴다. 스왑 영역은 메모리 관리자가 관리하는 하드디스크의 영역이다. 메모리에서 스왑 영역으로 보내는 것을 스왑 아웃이라 부..

물리 메모리 관리

도서 쉽게 배우는 운영체제와 강의 운영체제-반효경 를 보고 정리한 글입니다. 📌 메모리 관리자 모든 프로그램은 실행되기 위해 메모리로 올라와야 한다. 그리고 시분할 시스템에서는 여러 프로그램이 메모리에 올라와있기 때문에, 메모리를 적절하게 관리하는 것은 성능에 중요한 영향을 준다. 이러한 메모리 관리를, 메모리 관리자 (Memory Manage Unit, MMU) 라는 하드웨어가 담당한다. 가져오기 작업 메모리 관리자는 사용자가 요청하면 프로세스와 데이터를 모두 메모리로 가져온다. 메모리가 충분하지 않다면, 일부만 먼저 가져오고 나머지 메모리는 지속적으로 가져오는 경우도 있고 사용자의 요청이 없더라도 앞으로 필요할 것으로 예상되는 데이터를 미리 가져오기도 한다. 배치 작업 가져온 프로세스와 데이터를 메모..

교착 상태(DeadLock)

도서 쉽게 배우는 운영체제와 강의 운영체제-반효경 를 보고 정리한 글입니다. 📌 교착 상태란? 프로세스들이 서로가 가진 자원을 기다리며 대기중인 상태이다. CPU 스케줄링 파트에 나왔던 아사 현상과는 다른데, 아사 현상의 경우 특정 프로세스의 우선순위가 계속 밀려 장기간 CPU를 할당받지 못하는 것이고 교착상태는 여러 프로세스가 작업을 하다보니 서로의 자원을 할당받기 위해 무한정 대기하는 상태인 것이다. 교착 상태는 다음 4가지 조건을 💡 모두 만족했을 때, 발생한다. 1. 상호 배제 2. 비선점 3. 점유와 대기 4. 원형대기 상호 배제 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다. 즉, 자원이 임계구역으로서 보호되기 때문에 여러 프로세스가 동시에 자원을 사용할 ..

프로세스 동기화

도서 쉽게 배우는 운영체제와 강의 운영체제-반효경 를 보고 정리한 글입니다. 📌 Race Condition 2개 이상의 프로세스사 공유 자원을 읽거나 쓰는 상황을 Race Condition 이라고 한다. Race Condition이 발생하면 공유 자원 접근 순서에 따라 실행 결과가 달라질 수 있기 때문에 발생하지 않도록 해야한다. kernel 수행 중 인터럽트 발생 시 커널 모드로 count를 증가시키고 있던 와중에 인터럽트가 들어오면 인터럽트 처리 루틴으로 들어간다. 인터럽트 작업이 커널모드로 수행하던 count를 감소시키는 작업을 진행했다. 다시 커널모드로 돌아와서 작업을 수행할때에는, 인터럽트의 작업이 반영된 count가 아닌 이전에 진행중이었던 작업을 이어서 수행하기 때문에, 인터럽트가 했던 작업..

CPU 스케줄링

도서 쉽게 배우는 운영체제와 강의 운영체제-반효경 를 보고 정리한 글입니다. 스케줄링은 여러 프로세스의 상황을 고려하여 CPU와 시스템 자원을 어떻게 배정할지 결정하는 일을 말한다. 📌 스케줄링 수준 고수준 스케줄링 장기 스케줄링 이라고도 한다. 고수준 스케줄링은 시스템 내의 전체 작업 수를 조절하는 것을 말한다. 시스템 상황을 고려하여 어떤 작업을 승인할지, 거부할지를 결정하기 때문에 동시에 실행 가능한 프로세스의 총 개수가 정해진다. 저수준 스케줄링 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정한다. 주로, 프로세스의 상태를 관리하고 단기 스케줄링 이라고도 한다. 중간 수준 스케줄링 시스템에 동시에 실행 가능한 프로세스의 수를 고수준 스케줄링이 정한다면 중간 수준 ..

프로세스와 스레드

도서 쉽게 배우는 운영체제와 강의 운영체제-반효경 를 보고 정리한 글입니다. 📌 프로그램과 프로세스 프로그램은 저장장치에 저장되어있는 정적인 상태이다. 프로세스는 실행을 위해 프로그램이 메모리에 올라온 동적인 상태이다. 📌 프로세스의 5 가지 상태 프로세스를 일괄 작업으로 처리하면, 메모리에 하나의 프로세스만 올려놓고 사용하면 되지만 다른 프로세스는 하나의 프로세스가 종료될때까지 무한정 대기해야한다. 따라서, 시분할 작업 방식을 사용한다. 여러 프로세스에 CPU를 사용할 수 있는 시간을 분배하는 것이다. 프로세스가 바뀔때마다 문맥교환이라는 비용이 발생하지만, 일괄 작업 시 생기는 CPU의 낭비를 방지할 수 있다. 1. 생성 상태 프로세스가 메모리에 올라와 실행준비를 완료한 상태이다. 프로세스를 처리하기 ..

OSI 모델

OSI 모델이란? OSI 모델은 컴퓨터에서 데이터를 전송하기 위해서 컴퓨터 내부에서 하는 여러 가지 일들은 7 계층으로 나눈 것이다. 💡 통신이 일어나는 과정을 단계별로 알 수 있기 때문에 특정한 단계에서 이상이 생기면 그 곳만 수정하면 되기 때문에 편리하다. 사용하는 기계, 케이블 등과 관계 없이 통신을 하기 위해 공통으로 사용하기로 약속한 통신 표준 규격이다. 💡 TCP/IP 모델은 OSI 모델을 바탕으로 실생활에 사용하기 위해 만들어졌다. 1. 물리 계층 - 전송 매체의 물리적(기계적, 전기적) 인터페이스에 관한 기술 - 하드웨어로 구현 - 데이터 전송 속도, 클럭 동기화, 물리적 연결 형태 물리 계층은 전기 신호를 전달하는 계층이다. 컴퓨터는 0과 1로 이루어진 비트열을 사용한다. 따라서 통신이라..

MySQL 옵티마이저

MySQL 서버로 요청된 쿼리는 결과는 동일하지만 그 결과를 만들어 내는 방법은 매우 다양하다. 다양한 방법 중, 가장 최적이고 최소의 비용이 소모되는 방법을 선택하는 작업을 옵티마이저가 담당한다. MySQL 옵티마이저는 쿼리를 처리하기 위한 여러 가지 가능한 방법을 만들고, 각 단위 작업의 비용 정보와 대상 테이블의 예측된 통계 정보를 이용해 실행 계획별 비용을 산출한다. 산출된 비용을 바탕으로, 비용이 최소로 소요되는 처리 방식을 선택하는 💡 비용 기반 옵티마이저 이다. 옵티마이저가 만들어 내는 실행 계획을 이해할 수 있어야 실행 계획의 불합리한 부분을 찾아내고, 더 최적화된 방법으로 유도할 수 있다. 데이터 처리 📌 풀 테이블 스캔과 풀 인덱스 스캔 풀 테이블 스캔은 인덱스를 사용하지 않고 테이블의..

좋은 객체 지향 설계의 5가지 원칙 SOLID

S : SRP(Single Reposibility Principle), 단일 책임 원칙 한 클래스는 하나의 책임만 가져야 한다. 중요한 기준은 변경이다. 변경이 발생할때, 파급효과가 적으면 단일 책임 원칙, 즉 SRP 원칙을 잘 따른 것이다. O : OCP(Open/Closed Principle), 개방·폐쇄 원칙 확장에는 열려있어야 하나, 변경에는 닫혀있어야 한다. 새로운 기능을 추가하고 싶으면, 수정하는 것이 아닌, 인터페이스를 구현한 새로운 클래스를 하나 더 만들어서 새로운 기능을 구현한다. 구현 클래스와 실행클래스를 연결해주는 Config 클래스의 변경만 있으면 변화를 유연하게 할 수 있으며, 구현클래스에서의 직접적인 수정은 필요하지 않다. L : LSP(Liskov Substitutuion Pr..

운영체제란?

도서 쉽게 배우는 운영체제와 강의 운영체제-반효경 를 보고 정리한 글입니다. 📌 운영체제란? 운영체제는 컴퓨터 하드웨어 바로 위에 설치되어, 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어이다. 💡 사용자에게 편리한 인터페이스 환경을 제공하고 컴퓨터 시스템의 자원을 효율적으로 관리하는 소프트웨어이다. 대표적인 예로 윈도우, Mac OS, Linux, Unix 등이 운영체제라고 할 수 있다. 운영체제가 없는 기계는 만들 당시에 구현한 기능 외에 다른 기능을 추가하거나 성능을 향상할 수 없다. 운영체제가 있는 기계는, 기능의 추가나 성능 변경이 가능한 프로그래밍이 가능한 기계이다. 전화기와 스마트폰을 비교해보면, 전화기는 만들어진 기능인 전화만 사용할 수 있고, 스마트폰은 새로운 프로그램을 ..

Index(인덱스)에 대해서 알아보자

Real MySQL 책을 공부하면서 정리한 내용입니다. 데이터베이스의 성능 튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건일때가 상당히 많다. 💡 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 오래 걸린다. 그래서 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 삼아 인덱스를 만들어 둔다. 그리고 칼럼의 값을 주어진 순서로 미리 정렬해서 보관한다. 💡 조회 요청 시, 데이터가 정렬되어 있기 때문에 빨리 원하는 값을 찾아올 수 있다. (SELECT) 🚨 데이터가 저장될 때 마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리다. ( INSERT · UPDATE · DELETE ) 데이터 저장 방식 별로 구분하면, 대표적으로 B-Tree 인덱스와 Hash 인덱..

InvalidDefinitionException: No serializer found for class 에러

com.fasterxml.jackson.databind.exc.InvalidDefinitionException: No serializer found for class com.nts.domain.user.dto.UserCreateResponse and no properties discovered to create BeanSerializer (to avoid exception, disable SerializationFeature.FAIL_ON_EMPTY_BEANS) (through reference chain: com.nts.domain.Response["result"]) 간단한 Post 컨트롤러 API를 만들고, 테스트를 해봤는데 위와 같은 에러가 발생했다. 해석해보면, jackson 라이브러리를 사용해서..

[JAVA] 백준 1507번 【G2.궁금한 민호】

문제 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 풀이 1️⃣ 플로이드 알고리즘을 이용한 풀이 💡 참고한 Idea 먼저 입력으로 주어지는 비용 그래프가 플로이드 알고리즘을 이미 한번 거친 비용 그래프라고 생각해야한다. 그리고나서, 이 그래프를 다시 분해를 해야하는데 어떻게 분해할 수 있을까? 플로이드 알고리즘의 경우 costs[u][v] = Math.min(costs[u][v], costs[u][m] + costs[m][v]);​ 위와 같이 u에서 v로 가는 비용보다, u에서 m으로 간..

[JAVA] 백준 13168번 【G3.내일로 여행】

문제 13168번: 내일로 여행 첫 번째 줄에는 한국에 있는 도시의 수 N(1 ≤ N ≤ 100)과 1인당 내일로 티켓의 가격 R(1 ≤ R ≤ 1,000,000)이 주어집니다. 두 번째 줄에는 N개의 도시의 이름이 주어집니다. 도시의 이름은 알파벳 대소 www.acmicpc.net 풀이 1️⃣ 플로이드 알고리즘과 해시를 이용한 풀이 💡 떠오른 Idea 먼저, 플로이드 알고리즘을 사용해서 도시와 도시간 어떤 경로를 거치던 최소 비용을 구해야겠다고 생각이 들었다. 다만, 이 문제의 경우 도시가 숫자가 아닌 문자열의 형태로 주어지기 때문에 도시를 고유한 숫자로 변환하여 플로이드 알고리즘을 사용해야겠다는 생각이 들었다. 1. 먼저, 주어지는 도시의 중복이 있을 수 있다고 했으므로 중복을 제거한다. 중복을 제거..

[JAVA] 백준 2637번 【G2.장난감 조립】

문제 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 풀이 1️⃣ 위상정렬을 이용한 풀이 💡 떠오른 Idea 일단 부품의 조립 순서가 있으므로 위상 정렬을 사용해야한다는 것은 파악했다. 근데, 원하는 출력은 최종 장난감을 구성하는 기본 부품의 수를 출력해야했다. 기본 부품은 조합되어 만들어진 부품이 아닌 경우 기본 부품이라고 한다. 따라서, 특정 부품을 조립할때마다 해당 조립 부품을 구성하는 기본 부품의 정보를 저장하고 계속 넘겨주어야겠다고 생각했다. 일단, indegree 값이 0..

[JAVA] 백준 21276번 【G2.계보 복원가 호석】

문제 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 풀이 1️⃣ 위상 정렬과 우선순위 큐를 활용한 풀이 💡 떠오른 Idea 이 문제에서 가장 중요한 포인트는 직계 자손임을 어떻게 파악하는가였다. haeun doha doha minji haeun minji 위와 같이 관계가 주어졌을 때 하은은 도하와 민지의 자손이고 도하는 민지의 자손임을 알 수 있는데 들어오는 간선의 수를 보면 민지 : 0 도하 : 1 하은 : 2 임을 알 수 있다. 위상 정렬에 따라 정렬하면 민지에서 시작해서 민지와 연결된 간선..

[JAVA] 백준 1967번 【G4.트리의 지름】

문제 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 1️⃣ dfs를 이용한 풀이 💡 떠오른 Idea 처음에는 문제에서 친절하게 부모 노드를 명시해서 알려줘서 다른 방향으로 많이 생각했던 것 같다. 근데, 이 문제는 부모 노드를 특정해서 문제를 풀기보다는 모든 노드가 루트 노드가 될 수 있음을 가정해서 푸는 것이 편리하다. 예시에서 나온 그림은 위와 같은데 사실 위 그림은 9 를 최상단 노드라고 생각하고 그리면 위와 같이 그려질 수 있다. 그리고 9 → 5 → 3 → 6 → 12 노드..

[JAVA] 백준 2250번 【G2.트리의 높이와 너비】

문제 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 풀이 1️⃣ 중위순회를 이용한 풀이 💡 떠오른 Idea 중위 순회는 위와 같이 트리의 노드를 순회하는 방식이다. 중위 순회를 사용하면 트리에 존재하는 각 노드의 열 값을 알 수 있다. 각 노드의 깊이를 체크해나가면서 중위 순회를 하고, 각 깊이에 해당하는 열 값의 최솟값과 최댓값을 기록해두면 된다. public class Main { static Node[] tree; static Map info = new HashMap(); static..

[JAVA] 백준 20955번 【G4.민서의 응급 수술】

문제 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 풀이 1️⃣ 트리의 특징과 bfs 를 이용한 풀이 💡 떠오른 Idea 이 문제는, 무작위로 주어지는 노드간의 관계를 트리관계로 풀어가야 하는 문제이다. 먼저, 생각할 수 있는 경우는 다음과 같다. 1. 정상적인 트리 형태를 이루고 있는 집합인 경우 2. 특정 노드 집합이 사이클을 이루고 있는 경우 3. 1번 혹은 2번 같은 집합이 연결되어있지 않고 떨어져 있는경우 그래서 모든 뉴런을 하나의 트리 형태로 연결하기 위한 횟수를 어떻게 구해야할까 고민했는데 먼저..

[JAVA] 백준 22856번 【G4.트리 순회】

문제 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 풀이 1️⃣ 트리 클래스를 정의한 풀이 💡 떠오른 Idea 처음에는 이 문제에서 정의한 유사 중위 순회를 똑같이 구현해야하나 고민했었지만, 그러지 않고 쉽게 해결할 수 있었다. 이 유사 중위 순회의 특징은 트리에서 제일 오른쪽 간선은 한번만 지나가게 된다는 특징이 있다. 따라서, 가장 오른쪽 자식만 지나가게끔 하는 순회를 정의하여 노드의 개수를 구했고 간선의 개수는 노드의 개수 -1 임을 이용하여 편도 간선의 개수를 구할 수 있었다. 그리고 (전체 노드의 ..

[JAVA] 백준 5214번 【G2.환승】

문제 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 풀이 1️⃣ bfs와 인접리스트를 이용한 풀이 💡 참고한 Idea 역의 수 N이 최대 100000 이고 하이퍼 튜브와 하이퍼 튜브가 연결하는 역의 개수 K 와 M이 최대 1000 이라서 일반적인 그래프를 푸는 방식으로 노드를 연결하면 시간 복잡도가 말도안되게 커져서 고민을 많이 했다. 계속 메모리 초과를 어떻게 해결해야할지 고민하다가 다른 사람의 아이디어를 참고하였다. 하이퍼 튜브를 일종의 역으로서 생각을 하고 노드로서 추가하는 ..

[JAVA] 백준 1043번 【G4.거짓말】

문제 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 1️⃣ 플로이드 알고리즘을 이용한 풀이 💡 떠오른 Idea 이 문제는 파티별로 바로 체크를 할 수 없는 문제이고, 모든 파티의 정보를 처리한 다음에 개수를 구할 수 있다. 그 이유는 예제 처럼 4 5 1 1 1 1 1 2 1 3 1 4 2 4 1 위와 같이 주어졌을 때, 4번째 파티인 1 4 에서는 4번이 진실을 모를것 같지만 5번째 파티에서 진실을 아는 1번이 4번에게 알려 줄 수 있기 때문이다. 따라서, 순차적으로 판단할 수 없다. 내가 생각한 전략은 지민이..

[JAVA] 백준 2617번 【G4.구슬 찾기】

문제 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 풀이 1️⃣ bfs와 Marble 클래스 정의를 통한 풀이 💡 떠오른 Idea 문제를 해결하기 위한 방법은 문제에 거의 주어지다 싶이 나와있었다. 구슬이 총 5개일때는 특정 구슬보다 가벼운게 3개 이상인 경우 중간이 될 수 없고 무거운게 3개 이상인 경우는 중간이 될 수 없다. 처음에는 N이 짝수로도 주어지나 싶어서, 짝수인 경우에는 약간 기준이 달랐지만 홀수로만 주어진다고 했으므로 특정 구슬이, 상대적으로 가벼운 구슬이 (N+1)/2 개..

[JAVA] 백준 1707번 【G4.이분 그래프】

문제 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 1️⃣ 이분 그래프의 정의와 bfs 를 이용한 풀이 예전에 풀어봤던 문제여서, 원리를 쉽게 파악할 수 있었다. 이전에도, 한참을 고민했었다가 서칭해서 풀었었는데, 이분 그래프라는 단어가 나오면 이 정의를 생각해야한다. 이분 그래프인지 아닌지 확인할 수 있는 특징 중 하나인, 노드 그래프를 2개의 색깔로 칠했을 때, 인접하는 노드끼리 색이 겹치지 않게 색칠할 수 있을 때, 이분 그래프가 될 수 있다고 한다. 위와 같은 그림처럼 말이다. 아직 방문하지 않..

[JAVA] 백준 2660번 【G5.회장뽑기】

문제 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 1️⃣ 플로이드 알고리즘 사용 💡 떠오른 Idea 처음에 문제가 '어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.' 라고 나와있어서 이해하기가 힘들었었다. 근데, 이 문제를 직관적으로 이해해보니 '특정 회원이 있을 때 가장 사이가 ..

[Java] 909. Snakes and Ladders

문제 파악 Boustrophedon 스타일의 n*n 보드가 주어진다. ( (n-1,0) 좌표에서 시작한다. ) 주사위에 따라 최대 6칸을 이동할 수 있다. 만약 뱀이나 사다리를 만나면 뱀이나 사다리를 이용해야한다. n^2 칸에 도달했을 때, 게임은 끝난다. 보드 값이 -1이 아닌 경우 뱀이나 사다리가 존재한다. 뱀이나 사다리인 경우 도착하는 보드 값이 기록되어있다. 뱀이나 사다리는 1 또는 n^2 칸에 존재하지 않고 연속으로 이동할 수 없다. n^2에 도달하기 위한 최소 이동 횟수를 반환하고, 도달하지 못하면 -1을 반환한다. 풀이 1️⃣ 1차원 맵과 bfs 를 이용한 방법 💡 떠오른 Idea 먼저, 보드판 순서가 헷갈려서 이를 1차원 맵으로 바꿔서 해결하면 간단할것이라 생각이 들었다. 따라서, 제일 아..

[Java] 133. Clone Graph

문제 파악 노드로 연결된 그래프가 주어지고, 해당 그래프를 깊은 복사해서 반환해야한다. 풀이 1️⃣ bfs 를 이용한 풀이 💡 떠오른 Idea 깊은 복사를 하기 위해서는 어쩃든, 모든 노드에 방문해보고 해당 값을 갖는 새로운 노드를 생성해야한다. 문제에서 val 값은 unique 하다고 했으므로 map에 val 을 키값으로 해서 노드를 참조해준다. 첫번째 노드부터 이웃 노드들에 방문해보고, map에 들어있지 않은(아직 방문하지 않은) 노드들은 큐에 집어넣어 이웃 노드들에 방문하기를 반복한다. 만약 map에 들어있는(방문했던) 노드라면 큐에 넣지 않고 이웃으로서 추가만 해준다. class Solution { Map map = new HashMap(); Queue q = new LinkedList(); pu..

[Java] 373. Find K Pairs with Smallest Sums

문제 파악 비 내림차순인 두 정수 배열 nums1 과 nums2 그리고 k가 주어진다. k개의 가장 합이 작은 pair 를 반환해야한다. 풀이 1️⃣ PriortyQueue 와 일종의 그리디 법을 활용 💡 참고한 Idea 이번 문제는, 아무리 열심히 떠올려봐도 시간 초과 & 메모리 초과 때문에 해결하지 못하고 다른 사람의 아이디어를 참고하여 해결하였다. 핵심 아이디어는 다음과 같다. 먼저, 두 원소의 합을 기준으로 오름차순으로 정렬하는 우선순위 큐를 준비한다. nums1 배열의 인덱스는 0 으로 고정한 채, nums2 배열을 순회하며 합을 구하고 우선순위 큐에 입력한다. 우선순위 큐에는 [ nums1의 값, nums2 의 값, nums1의 인덱스, nums1의 값 +nums2의 값 ] 으로 입력해준다. ..

[Java] 215. Kth Largest Element in an Array

문제 파악 정수 배열 nums 가 주어지고 k가 주어진다. k번째로 큰 원소를 반환하면 된다. 풀이 1️⃣ PriorityQueue를 활용한 풀이 💡 떠오른 Idea 내림차순으로 정렬하는 우선순위큐에 원소들을 넣고 k번째의 원소를 반환한다. import java.util.*; class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue pq = new PriorityQueue((a, b) -> b - a); for (int num : nums) { pq.offer(num); } int ans = 0; while (k-- > 0) { ans = pq.poll(); } return ans; } } 결과 📖 회고 너무 간단하게 문제..

[Java] 212. Word Search II

문제 파악 문자가 채워져있는 m*n 크기의 보드가 주어진다. 문자열이 주어지는데, 해당 문자열을 만들 수 있으면 반환한다. 풀이 1️⃣ 백트래킹과 Set 이용한 풀이 💡 떠오른 Idea 백트래킹으로 만들 수 있는 문자열을 모두 구해본다. ( 최대 길이 10으로) 구한 문자열을 Set 에 넣고, 주어지는 문자열이 Set에 들어있는지 확인한다. import java.util.*; class Solution { int R; int C; boolean[][] checked; StringBuilder str = new StringBuilder(); int[] dr = {1, -1, 0, 0}; int[] dc = {0, 0, 1, -1}; char[][] board; Set set = new HashSet(); ..

[Java] 211. Design Add and Search Words Data Structure

문제 파악 특정 문자열을 보관하고 search 했을 때, 존재하면 true를 반환하는 자료구조를 만들어야한다. . 이 포함된 경우는 어떠한 문자가 들어가도 허용된다. 풀이 1️⃣ Trie 자료구조를 이용한 풀이 💡 떠오른 Idea Trie 자료구조를 이용하면 접두어나 부분 문자열을 검색할 수 있다. 따라서, Trie 자료구조를 구현하였다. 특히, 이 문제에서는 search 과정에서 . 이 포함되어 있는 경우는 해당 노드가 갖는 모든 자식 노드들을 탐색하도록 구현하여 해결할 수 있을 것이라 판단하였다. import java.util.*; class WordDictionary { static class Node { Map children; boolean isEndOfWord; public Node() { t..

[Java] 208. Implement Trie (Prefix Tree)

문제 파악 Trie 자료구조를 구현해야하는 문제이다. 트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 해시 테이블을 사용하면 되는데, 왜 트라이를 사용해야할까? 🚨 해시 테이블의 경우 접두사나 부분 문자열로 검색하기 힘들다. 또한, 해시 코드로 저장하기 때문에 정렬되어 있지 않다. 풀이 1️⃣ Node 클래스 정의 class Trie { Node root; static class Node { Map children; boolean isEndOfWord; public Node() { this.children = new HashMap(); this.isEndOfWord = false; } } public Trie() { this.root = new Node(); } } Trie..

[JAVA] 백준 1781번 【G2.컵라면】

문제 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 풀이 1️⃣ 우선 순위 큐와 그리디를 이용한 풀이 💡 떠오른 Idea 컵라면을 데드라인이 짧고 컵라면을 많이 주는 문제부터 결정해서 큐에 집어넣는다. 즉, 큐의 크기 = 풀기로 결정한 문제 수 = 내가 문제를 푸는데 사용한 시간이 된다. 그리고, 이후에 나오는 문제들이 내 큐의 크기보다 크거나 같으면서 내 큐에 들어있는 컵라면보다 많이 준다면 내 큐에 들어있던 가장 컵라면을 적게 주는 문제를 제거하고, 추가해준다. 예제로 원리를 설명해보면, 먼저, 데드라인이 짧은 ..

[JAVA] 백준 1655번 【G2.가운데를 말해요】

문제 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 1️⃣ 우선 순위 큐 두개를 활용한 풀이 💡 떠오른 Idea 우선 순위 큐는 이진 힙 방식으로 구성되어 있기 때문에, 사용하면 정렬을 유지한 삽입 과정을 O(logN) 에 수행할 수 있다. 그리고, 우선 순위 큐에 따라 정렬된 데이터를 꺼낼 때 역시, O(logN) 로 수행할 수 있다. 따라서 우선 순위 큐를 사용하는게 시간 복잡도를 만족시킬 수 있다고 판단하였다. 가운데 수를 항상 말해야 하므로, 내림차순으로 정렬된 우선순위 큐 (l..

[Java] 637. Average of Levels in Binary Tree

문제 파악 각 level(depth)의 노드들의 val 값 평균을 구해서 반환해야한다. 풀이 1️⃣ 그래프 탐색을 이용한 풀이 (전위 탐색) 💡 떠오른 Idea 전위 탐색을 depth를 1씩 증가시키면서 탐색을 한다. 각 depth에 도달했을 때, 해당 depth의 합과 개수를 저장하는 List를 통해 정보를 갱신한다. 탐색이 끝나고 나서, 평균 값을 구해서 반환해준다. import java.util.*; class Solution { List list = new ArrayList(); public List averageOfLevels(TreeNode root) { List ans = new ArrayList(); preOrder(root, 0); for (int i = 0; i < list.size()..

[Java] 199. Binary Tree Right Side View

문제 파악 주어지는 트리를, 오른쪽에서 바라보았을 때 보이는 노드들을 반환해야한다. 문제 해석 시, 약간 혼동이 있어서 처음에는 트리의 가장 오른쪽 노드들을 출력해야하는 줄 알았다. 따라서 위와 같이 구성된 트리의 경우, root 노드의 right node 는 없기 때문에 결과가 [1] 이 나와야 된다고 생각했는데 요구하는 답은 [1,2] 였다. 해석을 찾아보니, 이 트리를 오른쪽에서 바라봤을 때 보이는 노드들을 출력하라는 뜻이었다. 풀이 1️⃣ 전위 탐색을 이용한 풀이 💡 떠오른 Idea 전위 탐색의 경우 위와 같이 루트 노드에서 시작하여 왼쪽 혹은 오른쪽 경로의 끝에 도달하면 부모의 반대편 노드로 넘어가는 방식으로 탐색한다. 위 문제의 경우는 가장 오른쪽을 탐색해야하므로 경로를 오른쪽으로 시작하도록 ..

[Java] 230. Kth Smallest Element in a BST

문제 파악 k번째로 작은 값을 출력해야한다. 풀이 1️⃣ 중위 순회를 이용한 풀이 💡 떠오른 Idea 트리 구조에서 중위 순회를 하면 오름차순 순서로 노드 데이터를 출력할 수 있다. 이러한 원리를 적용하여 k번째 노드에 접근했을 때, 값을 저장하도록 구현하면 되겠다고 판단하였다. class Solution { int ans = 0; int idx = 1; public int kthSmallest(TreeNode root, int k) { inOrder(root, k); return ans; } private void inOrder(TreeNode node, int k) { if (node == null) { return; } inOrder(node.left, k); if (idx == k) { ans =..