Spring을 배우다보면 WAS, Dispatcher Servlet ... 등등 영어로 된 기괴한 용어들이 저희를 힘들게 합니다. 그 중 가장 처음에 등장하는 WAS와 Servlet의 개념에 대해 정리하려고 합니다.

 

1. WAS란?

WAS는 Web Application Server의 줄임말입니다. Application은 '응용'이란 뜻을 갖고 있습니다. 따라서, Web Application Server란 '웹(Web) 상에서 요청에 따라 동적(Application)으로 리소스를 제공(Server)하는 주체' 입니다. WAS의 종류에는 Tomcat, Jetty 등이 있고 Spring의 대표적인 WAS는 Tomcat입니다.

그렇다면 Spring의 WAS인 Tomcat을 이용해서 요청에 따라 다른 응답을 하는 '로직'을 작성할 수 있다는 건데,  Tomcat은 어떻게 우리가 이 로직을 잘 작성할 수 있도록 도와주는 걸까요?

 

2. Tomcat 없다면?

클라이언트와 서버는 HTTP 위에서 HTTP 메시지로 데이터를 주고 받습니다. 그리고, 이러한 HTTP 메시지는 예를 들어 아래와 같은 모양을 하고 있습니다.

자료 : Spring MVC 1편(김영한)

우리는 서버의 입장에서 클라이언트로부터 위와 같은 HTTP 메시지를 받았다고 가정하겠습니다. Tomcat이 없는 우리가 가장 먼저 해야하는 일은 위 메시지에서 의미있는 문자를 뽑아내는 것입니다. 예를 들어 어떤 HTTP 메소드인지(get, post ..), 어떤 url인지(/save), 메시지 바디는 어떻게 되어있는지 등이 있습니다.

서버는 의미있는 비즈니스 로직을 짜는 일이 더 중요한데, 그것보다 HTTP 메시지를 파싱하는 일이 더 커져버리는 배보다 배꼽이 더 큰 상황이 벌어졌습니다.

 

3. Tomcat 하는 일

이러한 불편함을 해소시켜주는 것이 바로 Tomcat(WAS)입니다.

Tomcat은 클라이언트로부터 받은 HTTP 메시지를 잘 파싱해서 Request 객체로 만들어줍니다. 또한, 우리가 클라이언트에게 보내줘야할 응답인 Response 객체도 만들어주어서 응답 HTTP 메시지를 보다 쉽게 만들 수 있도록 도와줍니다. 

출처 : Spring MVC 1편(김영한)

 

4. Servlet 이란?

우리는 WAS를 이용해서 HTTP 메시지를 손쉽게 다룰 수 있게 되었습니다. 그럼 이제 요청에 따라 응답을 동적으로 만들 '로직'이 필요합니다. 

이러한 '로직'이 있는 곳이 Servlet 입니다. Servlet에서 WAS로 부터 받은 Request 객체를 이용해서 동적인 Response 객체를 생성하고, 이를 다시 WAS에게 전달합니다. WAS는 받은 Response 객체를 응답 HTTP 메시지로 만들고 클라이언트에게 전달합니다.

따라서, Servlet은 'WAS로 부터 Request 객체를 전달받고 이를 통해 동적인 Response를 만드는 공간' 입니다.

이해하기 쉽게 대략적으로 작성한 내용이 많이 부실합니다. 큰 그림으로 WAS와 Servlet에 대해 이해하는데 도움이 되셨으면 좋겠습니다~

저작자표시

'Spring' 카테고리의 다른 글

AOP (2)  (1) 2023.08.28
AOP (1)  (0) 2023.08.25
IOC(Inversion Of Control), DI(Dependency Injection)  (0) 2023.08.24

학부에서 Java강의를 들으면, 'static'은 시험에서 단골문제입니다. 전에는 암기하기만 했던 'static'의 성질들을 JVM의 메모리구조부터 차근차근 살펴보며 이해하려 합니다. 왜 static이 그러한 성질을 갖게 되었는지 알아보겠습니다.

 

1. Java 응용프로그램 실행 순서

먼저, Java 응용프로그램이 실행되는 순서를 되짚고 가겠습니다.

(1) 운영체제로 부터 JVM이 사용할 메모리 할당받음
(2) javac.exe로 .java파일을 JVM이 실행할 수 있는 .class파일로 컴파일함
(3) java.exe로 main메서드 실행
(4) 실행 중 어떤 class가 필요할 때, 해당 .class파일을 읽어서 JVM이 할당받은 메모리에 올림.
(5) 모든 코드 실행 후 종료

이 순서로 실행됩니다. 신기했던 건, 프로그램 시작할 때가 아닌 실행 중에 필요한 .class파일을 메모리에 올린다는 점이었는데요. 클래스 로더라는 친구가 이 역할을 한다고 합니다. 

 

2. JVM 메모리 구조

그렇다면 어떤 형태로 .class파일을 읽어서 메모리에 올릴까요?

자료 : 'Java의 정석'

JVM은 위 그림처럼 메모리를 용도에 따라 대표적으로 3가지 영역으로 나누어 관리합니다. 그리고 이 중 'static'을 이해하기 위해서는 'Method Area'와 'Heap'에 대해 알아야합니다.

 

- Method Area

: 이 영역에는 클래스에 대한 정보가 저장됩니다. JVM은 해당 클래스가 필요할 때 .class파일을 읽어서 클래스에 대한 정보를 이곳에 저장합니다. 그리고 이 영역에 해당 클래스의 static변수와 static메소드 또한 생성됩니다.

- Heap

: 이 영역에는 인스턴스가 생성됩니다. 인스턴스가 생성될 때, 이 영역에 인스턴스 변수와 인스턴스 메소드가 생성됩니다.

 

예를 들어, 아래와 같은 클래스가 있습니다. 그리고 이 클래스는 실제 사용될 때 메모리에 올라갑니다.

public class Data {
	int x;
	static int y = 3;
	void m() {}
	static void s() {};
}

아래는 실제 사용될 때 입니다.

public static void main(String[] args) {
	//...
	Data data1; //Method Area에 Data클래스 생성
	data1 = new Data(); //Heap에 Data인스턴스(data1) 생성
	Data data2 = new Data(); //Heap에 Data인스턴스(data2) 생성
	//...
}

아래는 메모리에 로딩된 최종 결과 입니다.

정리하면

첫 번째로, 메모리에 생성되는 공간이 다릅니다. static변수와 메모리는 Method Area에, 인스턴스 변수와 메모리는 Heap에 생성됩니다.

두 번째로, 생성되는 시점이 다릅니다. static변수와 메모리는 클래스가 로딩되는 시점에 생성되는 반면, 인스턴스 변수와 메모리는 인스턴스가 생성될 때 생성됩니다.

세 번째로, 생성 횟수가 다릅니다. static변수와 메모리는 메모리에 한번만 올라가서 계속 있는 반면, 인스턴스 변수와 메모리는 새롭게 인스턴스가 생성될 때마다 메모리에 생성됩니다. 

 

3. static 성질 이해하기

저희가 이해한 것을 바탕으로 static의 성질들을 이해해보겠습니다.

 

- "static변수는 모든 인스턴스가 하나의 저장공간을 공유하므로, 항상 공통된 값을 갖는다"

: YES. 클래스의 static변수는 Method Area에 딱 하나 존재합니다. 인스턴스에서 참조하더라도 같은 공간을 참조하므로 항상 같은 값을 갖게됩니다.

 

- "static변수 및 메소드는 인스턴스를 생성하지 않아도 사용할 수 있다"

: YES. static변수와 메소드는 인스턴스가 생성되는 시점에 메모리에 올라가는 것이 아닌, 클래스가 메모리에 올라갈 때 생성됩니다.

 

- "static메소드는 인스턴스 변수나 메소드를 사용할 수 있다"

: NO. 클래스는 메모리에 로딩되었지만, 인스턴스는 없을 수 있습니다. 따라서, static메소드를 사용하는 시점에 인스턴스는 없을 수 있으므로 사용할 수 없습니다.

 

- "인스턴스 메소드는 static 변수나 메소드를 사용할 수 있다"

: YES. 인스턴스 메소드는 인스턴스가 생성되고 사용할 수 있습니다. 인스턴스가 생성되었다는 의미는 클래스가 메모리에 이미 로딩되었다는 뜻이므로 static변수와 메소드 또한 메모리에 로딩되었음을 의미합니다. 따라서, 사용할 수 있습니다.

시험에서 단골문제로 나왔던 'static' 성질 찾기. 위 예시 뿐만 아니라 여러가지 변형들이 무수히 존재합니다. 하지만, 메모리 관점에서 시작해서 static의 본질 이해하면 변형들도 쉽게 이해할 수 있으리라 생각합니다. 'static'을 공부하시는 분들께 도움이 됐으면 좋겠습니다~

저작자표시

'Java' 카테고리의 다른 글

JAR, WAR, EAR  (1) 2023.09.18
Garbage Collector  (0) 2023.09.15
JVM  (0) 2023.09.14
Abstract Class vs Interface  (0) 2023.09.13
[Java의 정석] JVM이란?  (0) 2023.04.01

1학년 때, 학부 강의를 듣다보면 JVM..., JDK를 설치해서..., 시스템 환경변수 path에 bin파일을 추가... 등등 하나도 이해하지 못하고 따라하기 급급한 행동들이 있습니다. 저도 그랬습니다. 그리고 저는 심지어 졸업을 한 지금까지도 이해를 하지 못했습니다. 

지금부터, 이에 대해 조금 더 쉽게 이해해보도록 하겠습니다.

 

1. JVM...?

우리가 다른나라로 여행을 간다고 가정해봅시다. 나라마다 표준전압이 다르기 때문에 저희는 '어댑터'를 가져갑니다. 그런데 혹시 이런 어댑터가 없는 상황을 생각해보신적 있으신가요? 저희는 코드가 필요한 모든 전자기기를 해당 나라의 전압에 맞는 것으로 새로 사서 가져가야 합니다(어댑터는 정말 소중한 겁니다ㅎㅎㅎ). 어댑터가 있음으로써, 저희는 '하나의 220V짜리 핸드폰 충전기'와 '어댑터'를 가지고 모든 나라에서 핸드폰을 충전할 수 있는 것입니다.

 

위 비유는 Java 세계에서 아래와 매칭됩니다.

'나라마다 다른 표준전압' = 다양한 운영체제(OS)
'어댑터' = JVM
'전자기기' = Java 어플리케이션

따라서, 우리는 '하나의 Java 어플리케이션' 과 'JVM'을 가지고 모든 '운영체제'에서 실행할 수 있습니다. 하지만 '어댑터'는 220V를 110V, 250V 등등 여러 전압으로 변환해주지만, JVM은 해당 운영체제에 맞는 JVM이 필요합니다. 그래서 저희가 1학년때 그냥 따라만 했던, '운영체제에 맞는 JDK를 다운받아서...'가 해당 운영체제에 맞는 JVM을 다운받는 행위였습니다.

(JDK : JVM과 자바 클래스 라이브러리 등 자바를 개발하는데 필요한 프로그램)

 

2. 시스템 환경변수 path에 bin디렉토리 경로를 추가한다...?

여기서 의문이 드는 점은 두가지 입니다.

JDK의 bin폴더에는 뭐가 있는데? 와 시스템 환경변수 path에 등록하면 뭐가 좋은데? 입니다.

 

(1) JDK의 bin폴더에 있는것

여기에는 javac.exe, java.exe 등등 쉽게 말해서 JVM을 실행시키는 실행파일들이 있습니다. 쉽게 알아보도록 하겠습니다.

javac.exe - 220V 핸드폰 충전기를 어댑터에 꽂는 행위
java.exe - 이 어댑터를 콘센트에 꽂는 행위

좀 더 깊게 들어가면,

javac.exe 실행파일은 Java코드를 JVM이 이해할 수 있는 바이트 코드로 바꾸는 역할을 합니다.

java.exe 실행파일은 이렇게 만들어진 바이트 코드를 기계어로 번역해 운영체제로 전달해서 실행하는 역할을 합니다.

자세히 이해하려면 컴퓨터 구조, 운영체제에 대한 이해가 필요합니다. 따라서, 이러한 지식이 없다면 그냥 느낌정도만 아는 것으로 충분하다고 생각합니다.

 

(2) 시스템 환경변수 path에 등록하면 좋은 점

시스템 환경변수 path에 디렉토리 경로를 등록하면, 어디서라도 해당 디렉토리안에 들어있는 파일을 실행할 수 있습니다. 이는 쉽게 말해, 운영체제에게 어댑터(JVM)의 위치를 알려준다고 생각할 수 있습니다. 운영체제는 어댑터의 위치를 알고있어서, Java어플리케이션을 실행할 때 언제든 가져와 사용할 수 있습니다. 이를 위해 path를 등록하는 것입니다. 

'Java의 정석' 책의 Chapter 1을 읽으면서, 이전에 대학교 1학년 때 따라만 했던 행위를 이해할 수 있었습니다. 저와 같은 분들에게 도움이 됐으면 좋겠습니다~ 

 

저작자표시

'Java' 카테고리의 다른 글

JAR, WAR, EAR  (1) 2023.09.18
Garbage Collector  (0) 2023.09.15
JVM  (0) 2023.09.14
Abstract Class vs Interface  (0) 2023.09.13
[Java의 정석] Static이란?  (0) 2023.04.07

과거와 달라진 현재, 그리고 현재 모습을 통해 그려낼 미래에 대해 남기려고 합니다.

지금 이 글을 쓰며 했던 생각과 다짐을 기록으로 남겨, 훗날 다시 채찍질하기 위해 읽으려 합니다.

 

과거

2016.03 ~ 2019.11

: 대학교 입학부터 전역까지 입니다. 정말... 술마시고 놀러다니기만 했습니다. 학업에 손을 대지 않아 이때까지 학점은 2.9였던 걸로 기억합니다. 하지만 이 때 한 가지 얻은 것이 있다면, 가정사로 인해 배운 '마음 먹으면 무엇이든 할 수 있다'라는 가치관 입니다.  

2019.11 ~ 2020.12

: 귀신같이 전역하고 사람이 달라졌습니다. 지금 생각해보면 신기한 것 같아요. 군대에서도 군대 사람들이랑 맨날 놀았던 저가 전역하고 나서 갑자기 공부하는 사람으로 변하다니... 이 기간동안 정말 열심히 공부했습니다. 복학 전에 학과 선배의 권유로 알고리즘 문제를 풀며 공부하기 시작했습니다. 그리고 복학한 후에는 학과 공부를 했습니다. 

2021.02 ~ 2021.06

: 작년 한해 열심히 공부했던 결실을 맺는 기간이었습니다. 학부 연구실에 인턴으로 들어갔고, 교내 코딩테스트에서 입상했습니다. 처음으로 했던 노력에 보상을 받으며 뿌듯함을 느꼈고, 한번 더 '마음 먹으면 무엇이든 할 수 있다'를 체험할 수 있었습니다.

2021.06 ~ 2022.12

: 작년부터 테니스를 하고 있었는데, 전국 동아리테니스 대회를 갔다온 이후에 열정이 공부보다 더 커졌습니다. 2022년에는 부모님께 '대학생때만 할 수 있는 이 대회에서 입상을 하고 싶다'고 말하며, 테니스만 했습니다. 이 기간에 공부를 더 꾸준히 했더라면 지금 취업으로 고생하고 있지 않았을텐데라는 생각을 하지만, 목표를 위해 열정적으로 달려갔기에 후회는 하지 않습니다. 

2023.01 ~ 2023.03

: 졸업을 하고 취업 준비 기간입니다. 다시 공부를 시작하고 이곳 저곳 기업에 원서를 썼습니다. 하지만, 모두 탈락을 했습니다.  이 때 느낀점은 '내가 하고 싶은 직무의 확실한 역량을 쌓아야 겠다'와 '정말 이 기업에 가려는 이유를 찾아 어필하자' 였습니다.

 

현재

'아무 기업이나 저 좀 뽑아주세요'가 아니라 '이 기업에서 이러한 이유로 일하고 싶고, 그래서 이런 준비를 했다'를 보여주려고 합니다. 저는 'XXX의 백엔드 개발자'가 되려 합니다. 아직 기업은 정하지 못했지만, 차차 기업과 동기를 찾을 예정입니다. 역량 준비는 부족한 기본기에 기술을 쌓아올리는 것이 아니라 다시 처음으로 돌아가 기본기부터 탄탄하게 다질 예정입니다. 이를 위해 제 계획은 다음과 같습니다.

1. Java 

: 가장 먼저 Java언어의 기본기를 다지려 합니다. 'Java의 정석'이란 책을 읽으며 하나하나씩 정립해 나가려하고, 새롭게 알게된 부분을 저만의 언어로 블로그에 기록하려 합니다. 

2. 객체지향 설계

: 읽을 책을 아직 정하지 않았지만, 책을 읽으며 객체지향 설계의 핵심을 이해하려 합니다. 그리고, 이전 우테코 프리코스의 과제들을 수행해보며 객체지향 설계를 활용할 예정입니다.

3. Spring boot

: 김영한님의 스프링 부트 강의를 듣고 기회가 된다면 '토비의 Spring' 책도 읽어볼 예정입니다. 그리고, 이를 활용해 예전에 만들었던 프로젝트를 다시 새롭게 Spring boot로 만들어볼 예정입니다.

4. 데이터베이스

: 추후 계획을 업데이트 하겠습니다.  

5. JPA

: 김영한님의 JPA강의를 들으려 합니다. 추후 읽을 책을 업데이트 하겠습니다.

6. 기타

: 올해 6월부터 진행하는 K-Digital Training 백엔드 데브코스와 내년에 있을 우테코에 지원할 예정입니다. 여기서 강의를 들으며 기반 지식을 습득하고 다양한 사람들과 프로젝트 경험을 쌓으려 합니다.

 

미래

저는 크게 두 가지 꿈이 있습니다. '대체불가 백엔드 개발자'와 '좋은 아빠' 입니다. 이 두 모습의 그림을 그리며 나아갈 것이고, 분명히 이렇게 될 것입니다. 왜냐하면 저는 마음 먹으면 무엇이든 해낼 수 있기 때문입니다.

테니스를 하며 배운점이 있습니다. '욕심이 많고 급하면, 탈난다'

저는 작년 한해 테니스 실력을 빠르게 늘리기 위해, 하루에 8시간 정도를 쳤던 것 같습니다. 하지만, 분명 실력은 늘었겠지만 만족하지 못했고 더 많이 더 빠르게 성장하기 위해 혹사 하다시피 운동했습니다. 그러자 크게 부상을 당했습니다. 

이 때 얻은 교훈을 지금 적용하려 합니다. 단순히 주변 사람들이 다 취직해서 조급한 마음에 부실하게 쌓아 올리는 것이 아니라, '천천히, 정확히, 꾸준하게' 저를 튼튼하게 만들어 가려 합니다.

앞으로 자주 읽으며 업데이트도 하자~~~ 화이팅!

 

저작자표시

https://school.programmers.co.kr/learn/courses/30/lessons/150365

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

<풀이>

1. 미로 정보를 입력받는다.

2. 사전 순으로 가장 빠른 미로 탈출 경로를 반환한다.

 

<해법>

1. 완전탐색 X

=> 평범한 길찾기 문제라는 생각이 듭니다. 하지만 이 문제는 k가 최대 2500이므로, 완전탐색으로 풀 때 최악의 경우 O(4^2500)의 시간복잡도를 가집니다. 따라서, 완전탐색 알고리즘은 배제해야합니다.

 

2. 불가능한 경우 찾기

=> 먼저 "impossible"한 경우부터 생각해보겠습니다.

첫번째로, 출발지점에서 끝지점까지 갈 수 있는 최단거리보다 k가 작을 경우 불가능합니다. 여기서, 출발지점에서 끝지점까지 최단거리를 계산하는 방법은 매우 간단합니다. 지도 상에 장애물이 없으므로, 맨해튼 거리계산법(ㅣx - rㅣ+ ㅣy - cㅣ)를 이용해서 구할 수 있습니다. 따라서, if(최단거리 > k) answer = "impossible" 입니다.

두번째로, (k - 최단거리) % 2 == 1 일 때 불가능합니다. 이유는 k번을 채우기 위해서는 어디선가 왔다갔다를 해야하기 때문입니다. 단순히 k번을 이용한 거리를 구하라고 한다면, 출발지점에서 끝지점까지 간 후 끝지점에서 바로 옆칸으로 왔다갔다하면 구할 수 있습니다. 그런데 이 때, '왔다갔다'를 해야하므로 2번이 필요합니다. 만약 도착지점에서 k가 1이라면 불가능합니다. 따라서, if((k - 최단거리) % 2 == 1) answer = "impossible" 입니다.

 

3. 사전순으로 가장 빠른 경로 찾기

=> 위 경우를 제외하고서는 k번 이동하여 출발지점부터 끝지점까지 갈 수 있습니다. 이제 사전순으로 가장 빠른 경로를 찾아야합니다. 사전순으로 가장 빠르려면, 앞자리가 가장 빨라야합니다. 이 말은 'd(아래)로 갈 수 있으면, d로 가는게 가장 좋다.' 입니다. 또, 'd -> l -> r -> u 순으로 갈 수있는 곳을 탐색해서 간다.' 가 됩니다. 

그렇다면 이제 해당 방향으로 가도 되는지 안되는지 판단하는 일만 남았습니다. 해당 방향으로 가도 되려면, 먼저 맵을 벗어나면 안됩니다. 그리고 또 한가지는 위에 "impossible"한 경우가 아니면 됩니다. 이 말은 다음 위치에서 최단거리 <= 남은 k 면 된다는 뜻입니다. 이렇게 하면 greedy하게 사전순으로 가장 빠른 방향으로 이동하며 정답을 구할 수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <string>
#include <vector>
 
using namespace std;
 
char d[] = { 'd', 'l', 'r', 'u' };
int dx[] = { 1,0,0,-1 };
int dy[] = { 0,-1,1,0 };
 
bool isInner(int x, int y, int n, int m) {
    if (x <= 0 || y <= 0 || x > n || y > m) return false;
    return true;
}
 
string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
 
    int shortest = abs(x - r) + abs(y - c);
    if (shortest > k || (k - shortest) % 2) answer = "impossible";
    else {
        while (k--) {
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (!isInner(nx, ny, n, m)) continue;
                int nshortest = abs(nx - r) + abs(ny - c);
                if (nshortest > k) continue;
                x = nx, y = ny;
                answer += d[i];
                break;
            }
        }
    }
 
    return answer;
}

 

Greedy 알고리즘에 대해 알아볼 수 있었습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 표 병합  (0) 2023.02.02
[C++] 프로그래머스 - 표현 가능한 이진트리  (0) 2023.02.02
[C++] 프로그래머스 - 이모티콘 할인행사  (0) 2023.02.01
[C++] 프로그래머스 - 택배 배달과 수거하기  (0) 2023.02.01
[C++] 프로그래머스 - 개인정보 수집 유효기간  (0) 2023.02.01

https://school.programmers.co.kr/learn/courses/30/lessons/150366

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

<풀이>

1. 표를 편집하는 명령어를 입력받는다.

2. 명령어를 실행한 결과를 반환한다.

 

<해법>

1. 알고리즘 선택하기

=> 문제를 읽고 가장 먼저 Union-Find 알고리즘이 떠오릅니다. 아래는 Union-Find 알고리즘에 따라 구현 방법에 대해 정리한 생각입니다.

(1) 'UPDATE r c value'

: 표의 (r, c)의 부모를 찾아 value를 바꾼다.

(2) 'UPDATE value1 value2'

: 표의 모든 value1을 value2로 바꾼다. 표의 크기는 50x50 = 2500이고 명령어의 갯수는 최대 1000개이므로, O(2500x1000)의 시간복잡도로 풀이 가능하다.

(3) 'MERGE r1 c1 r2 c2'

: (r2, c2)의 부모를 (r1, c1)의 부모로 바꾼다. 데이터는 규칙에 따라 바꾼다.

(4) 'PRINT r c'

: (r, c)의 부모를 찾아 value를 출력한다.

(5) 'UNMERGE r c'

: 여기서 막힙니다. 표의 모든 셀과 (r, c)의 부모가 같은지 확인해야하는데, 이 경우 O(2500x2500x1000)의 시간복잡도가 되기 때문입니다(Union-Find의 find함수가 최악의 경우 O(N)이기 때문). 그렇다면 어떻게 해야할까요?

 

2. UNMERGE 해결하기

=> 생각해보면, Union-Find 알고리즘은 Union과 Find에만 관심이 있는 알고리즘입니다. 저희 문제와 같이 UNMERGE하는 부분에는 관심이 없습니다. 따라서, 이 알고리즘의 좋은 부분만 가져와 저희의 문제에 맞게 조금 변형해서 사용해야합니다. UNMERGE 명령어에서 가장 큰 문제점은 셀의 부모가 제 멋대로라는 점입니다.

위 그림처럼 부모를 찾기위해 계속해서 타고들어가야 하기 때문에 3,4,5번이 모두 1번 셀이라는 것을 단번에 알 수 없습니다. 그렇다면 3,4,5번이 모두 2번처럼 1로 표시되면 어떨까요? 정말 간단해집니다. 모든 셀을 돌며 부모가 1인것만 다시 되돌리면 되기 때문입니다. 그리고 이렇게 되면 O(2500x1000)의 시간복잡도가 되므로 풀 수 있습니다. 

 

3. MERGE 교체하기

=> 3,4,5번의 부모가 모두 1로 표현되려면, MERGE부터 바꿔야합니다. 기존 Union-Find의 경우는 부모만 바꾸어 주었다면, 저희는 부모의 자식들 또한 바꾸어주어야합니다.

위 그림처럼 교체하면 MERGE는 O(2500x1000)의 시간복잡도를 가지게 되므로 풀 수 있습니다.

 

4. 구현 전 정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 셀은 1차원 배열로 바꿔서 생각한다. 부모를 정수로 편하게 관리할 수 있기 때문.

(2) 부모 배열과 데이터 배열 두 개를 관리한다.

(3) 빈 데이터는 "EMPTY"를 넣는다. 데이터는 알파벳 소문자와 숫자로만 이루어져있으므로 가능하고, 출력할 때 편리하다.

자세한 구현은 아래 코드를 참고해주세요.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <string>
#include <vector>
#include <sstream>
 
using namespace std;
 
int link[2501];
string value[2501];
 
int flatPos(int r, int c) {
    return (r - 1) * 50 + c;
}
 
vector<string> solution(vector<string> commands) {
    vector<string> answer;
 
    //초기화
    for (int i = 1; i <= 2500; i++) {
        link[i] = i;
        value[i] = "EMPTY";
    }
 
    //해법
    for (string &command : commands) {
        vector<string> v;
        stringstream ss(command);
        string token;
        while (ss >> token) v.push_back(token);
 
        if (v[0] == "UPDATE") {
            if (v.size() == 4) { //1. UPDATE r c value
                int pos = flatPos(stoi(v[1]), stoi(v[2]));
                string val = v[3];
                int parent = link[pos];
                value[parent] = val;
            }
            else { //2. UPDATE value1 value2
                string val1 = v[1], val2 = v[2];
                for (int i = 1; i <= 2500; i++) {
                    if (value[i] == val1) value[i] = val2;
                }
            }
        }
        else if (v[0] == "MERGE") { //3. MERGE r1 c1 r2 c2
            int pos1 = flatPos(stoi(v[1]), stoi(v[2])), pos2 = flatPos(stoi(v[3]), stoi(v[4]));
            int parent1 = link[pos1], parent2 = link[pos2];
            if (parent1 != parent2) {
                for (int i = 1; i <= 2500; i++) {
                    if (link[i] == parent2) link[i] = parent1;
                }
                string val1 = value[parent1], val2 = value[parent2];
                if (val1 == "EMPTY" && val2 != "EMPTY") {
                    value[parent1] = value[parent2];
                }
                else {
                    value[parent2] = value[parent1];
                }
            }
        }
        else if (v[0] == "UNMERGE") { //4. UNMERGE r c
            int pos = flatPos(stoi(v[1]), stoi(v[2]));
            int parent = link[pos];
            string val = value[parent];
            for (int i = 1; i <= 2500; i++) {
                if (link[i] == parent) {
                    link[i] = i;
                    value[i] = "EMPTY";
                }
            }
            value[pos] = val;
        }
        else { //5. PRINT r c
            int pos = flatPos(stoi(v[1]), stoi(v[2]));
            int parent = link[pos];
            answer.push_back(value[parent]);
        }
    }
 
    return answer;
}

 

Union-Find에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 미로 탈출 명령어  (0) 2023.02.03
[C++] 프로그래머스 - 표현 가능한 이진트리  (0) 2023.02.02
[C++] 프로그래머스 - 이모티콘 할인행사  (0) 2023.02.01
[C++] 프로그래머스 - 택배 배달과 수거하기  (0) 2023.02.01
[C++] 프로그래머스 - 개인정보 수집 유효기간  (0) 2023.02.01

https://school.programmers.co.kr/learn/courses/30/lessons/150367

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

<풀이>

1. 숫자들을 입력받는다.

2. 각 숫자를 하나의 이진트리로 표현할 수 있는지의 여부를 반환한다.

 

<해법>

1. 이진트리로 표현할 수 있는 수와 없는 수의 규칙 찾기

=> 번뜩이는 알고리즘이 떠오르지 않습니다. 따라서, 예제를 보면서 하나하나씩 직접 해보며 규칙을 찾아야합니다. 

7 = 111 (O)

42 = 0101010 (O)

5 = 101 (X)

그림과 쉽게 비교하기 위해 더미노드(0)도 추가했습니다. 규칙이 조금씩 보이시나요? 읽는 순서를 고려했을 때, 루트노드는 항상 2진수의 중앙에 옵니다. 루트노드에 더미노드(0)이 올 수 있을까요? 없습니다. 루트노드가 0인 수는 0뿐인데, 주어지는 숫자는 1이상 이기 때문입니다. 따라서, 규칙 하나를 찾았습니다. '2진수의 중앙은 0이 될 수 없다.'

 

두 번째 예시를 보며 규칙을 찾아보겠습니다. 

63 = 0111111 (O)

111 = 1101111 (O)

95 = 1011111 (X)

95는 2진수의 중앙이 1인데 불가능하다고 나옵니다. 왜일까요?

위와 같이 그려지기 때문입니다. 규칙 하나를 더 찾았습니다. '0이 1의 부모노드로 존재할 수 없다.' 또한, 그림을 직접 그려보면 트리를 왼쪽, 오른쪽 서브트리로 분할하고 정복해서 풀어야겠다는 느낌을 강하게 받을 수 있습니다. 그렇다면, 이제 어떻게 분할정복할지 알아보겠습니다.

 

2. 분할정복하는 방법

=> 위의 예시들로 몇가지 규칙을 찾았습니다. 찾은 규칙을 바탕으로 자세하게 분할정복하는 방법을 알아보겠습니다. 110 = 1101111을 예시로 들겠습니다.

(1) 분할하는 방법

110(왼쪽 서브트리) / 1(부모) / 111(오른쪽 서브트리) 로 분할합니다. 이후 왼쪽과 오른쪽을 정복한 후 이진트리로 표현할 수 있는지 판단합니다.

(2) 부모가 1인 경우

일단 이진트리로 표현할 수 있습니다. 왼쪽과 오른쪽 서브트리 또한 이진트리로 표현할 수 있다면, 이진트리로 표현할 수 있습니다.

(3) 부모가 0인 경우

부모가 0인 경우는 모두 불가능할까요? 아닙니다.

위와 같이 자식도 모두 0인 경우에는 이진트리로 표현할 수 있기 때문입니다. 따라서, 부모가 0인 경우에는 자식이 모두 0인 경우에는 가능하고, 나머지 경우는 불가능합니다.

 

3. 구현 전 정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 주어진 숫자를 이진수로 만든다. (ex 5 -> 101) (코드의 hexToDec함수 참고)

(2) 만든 이진수를 포화 이진수로 만든다. 포화 이진수란 포화 이진트리로 표현할 수 있는 숫자이다. 포화이진트리의 노드 갯수는 2^n - 1개 입니다. 따라서, 포화이진트리 노드의 갯수에 맞춰서 앞에 0을 추가한다. (ex 11 -> 1011 -> 0001011) (코드의 changeToFullDec함수 참고)

(3) 만든 포화 이진수를 분할정복한다. 왼쪽, 중앙, 오른쪽으로 분할해서 정복한다. (ex 0001011 -> 000 / 1 / 011) (코드의 canDraw함수 참고)

자세한 구현은 아래 코드를 참고해주세요.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
string hexToDec(long long num);
string changeToFullDec(string str);
bool isAllZero(string str);
bool canDraw(string str);
 
vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    for (long long& num : numbers) {
        string dec = hexToDec(num);
        string fullDec = changeToFullDec(dec);
        answer.push_back(canDraw(fullDec));
    }
    return answer;
}
 
string hexToDec(long long num) {
    string ret = "";
    while (num) {
        ret = to_string(num % 2) + ret;
        num /= 2;
    }
    return ret;
}
 
string changeToFullDec(string str) {
    string ret = str;
    int idx = 2;
    while (true) {
        if (str.length() <= idx - 1) break;
        idx *= 2;
    }
    for (int i = 0; i < idx - 1 - str.length(); i++) ret = "0" + ret;
    return ret;
}
 
bool canDraw(string str) {
    if (str.length() == 1 || isAllZero(str)) return true;
 
    int midIdx = str.length() / 2;
    string left = str.substr(0, midIdx);
    string right = str.substr(midIdx + 1);
 
    if (str[midIdx] == '1' && canDraw(left) && canDraw(right)) return true;
    else return false;
}
 
bool isAllZero(string str) {
    for (char c : str) {
        if (c != '0') return false;
    }
    return true;
}

 

분할정복에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 미로 탈출 명령어  (0) 2023.02.03
[C++] 프로그래머스 - 표 병합  (0) 2023.02.02
[C++] 프로그래머스 - 이모티콘 할인행사  (0) 2023.02.01
[C++] 프로그래머스 - 택배 배달과 수거하기  (0) 2023.02.01
[C++] 프로그래머스 - 개인정보 수집 유효기간  (0) 2023.02.01

https://school.programmers.co.kr/learn/courses/30/lessons/150368

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

<풀이>

1. 사용자 정보와 이모티콘 정보를 입력받는다.

2. 행사 목적의 최대치를 반환한다.

 

<해법>

1. 알고리즘 선택하기

=> 문제를 읽고 가장 먼저 떠오르는 알고리즘은 모든 경우를 다 해보는 브루트 포스 입니다. 브루트 포스를 사용할 수 있는지 확인하기 위해 시간복잡도를 계산해야합니다. 10, 20, 30, 40%로 7개의 이모티콘 모두 적용해 보아야하고 모든 사용자 100명에 있어서 7개의 이모티콘을 확인해봐야합니다. 시간 복잡도는 O(4^7 x (100 x 7)) = O(11,468,800) 입니다. 따라서, 브루트 포스 알고리즘을 사용할 수 있고 선택했습니다.

 

2. 구현 전 정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 브루트 포스 알고리즘을 사용한다. 7개의 이모티콘에 10, 20, 30, 40% 할인 비율을 모두 적용시키는 것은 재귀함수로 구현한다.

(2) 이모티콘의 가격은 100의 배수로 주어지므로, 가격 연산은 편하게 진행하면 된다.

자세한 구현은 아래 코드를 참고해주세요.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
int N, M;
int rate[7];
vector<vector<int>> u;
vector<int> e;
int ansService, ansProfit;
vector<int> answer;
 
int calcPrice(int price, int discountRate) {
    return (price * (100 - discountRate)) / 100;
}
 
void selectDiscountRate(int idx) {
    if (idx == M) {
        int service = 0, profit = 0;
        for (int i = 0; i < N; i++) {
            int price = 0;
            for (int j = 0; j < M; j++) {
                if (rate[j] >= u[i][0]) price += calcPrice(e[j], rate[j]);
            }
            if (price >= u[i][1]) service++;
            else profit += price;
        }
 
        if (service > ansService) {
            ansService = service, ansProfit = profit;
        }
        else if (service == ansService) {
            if (profit > ansProfit) ansProfit = profit;
        }
        return;
    }
    
    for (int i = 10; i <= 40; i += 10) {
        rate[idx] = i;
        selectDiscountRate(idx + 1);
    }
}
 
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    //초기화
    u = users, e = emoticons;
    N = u.size(), M = e.size();
    ansService = 0, ansProfit = 0;
 
    //해법
    selectDiscountRate(0);
    answer.push_back(ansService);
    answer.push_back(ansProfit);
 
    //반환
    return answer;
}

 

브루트 포스에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 표 병합  (0) 2023.02.02
[C++] 프로그래머스 - 표현 가능한 이진트리  (0) 2023.02.02
[C++] 프로그래머스 - 택배 배달과 수거하기  (0) 2023.02.01
[C++] 프로그래머스 - 개인정보 수집 유효기간  (0) 2023.02.01
[C++] 프로그래머스 - 코딩 테스트 공부  (0) 2022.08.24

+ Recent posts

티스토리툴바