지난 주말 자동차 업계에 종사하는 친구들을 따라 현대자동차 UX 스튜디오 서울을 방문했습니다.

겸사겸사 따라가서 자동차 설명도 듣고 현대자동차는 UX를 어떻게 접근하는지 직접 볼 수 있어 값진 시간이었습니다 :)

역시 현대자동차 사옥답게 외관은 굉장히 깔끔하고 세련된 느낌이었고 ‘여기서 일하고싶다..’ 라는 생각이 절로 들더라구요..

입구에 들어서자마자 굉장히 큰 로봇들로 이루어진 생산 공정이 보였는데요, 2021년부터 적용된 공정이라고 하는데 굉장히 인상깊었습니다.

들어가자마자 쭈뼛쭈뼛하고 있으니, 가이드분께서 알아차리시고 하나하나 정말 친절하게 설명해주셨어요.

가이드는 사전에 예약이 가능하니, 방문하실 분들은 꼭 예약하고 설명을 들으시길 추천드려요! 저는 예약 마감으로 신청을 못 했지만, 다행히도 친절한 가이드님 덕분에 설명을 들을 수 있었답니다 😊

아래 링크로 들어가시면 바로 예약하실 수 있어요! 👇🏻 https://www.hyundai.co.kr/uxstudio/reservation/tour

UX Test 존

1층 전시관의 가장 먼저 보이는 곳은 현대자동차가 UX를 설계하는 5단계를 보여주고 있었습니다.

Discover → Define → Ideate → Prototype → Test

출근’을 예시로 든 것이 특히 기억에 남는데요,

출근길에 커피를 자주 마시는 직장인을 위해 드라이브 스루 결제 시스템과 차량 번호판 등록을 연동해 아이디어였습니다. 평소 스타벅스에서 자주 사용하는 기능이 등장한 배경이라 생각하니 정말 인상깊었어요🙂

SDV 존

두번째로 눈에 띄는 곳은 SDV Zone이었습니다.

차량 내부의 시스템과 제어가 어떻게 이루어지는지를 한눈에 볼 수 있어 매우 흥미로웠는데요,

기존에는 선으로 연결되던 부분들이 소프트웨어 기반 무선 통신(wireless)로 전환되면서 경량화를 이루었고 중앙 집중형이었던 zone controller 또한 로드밸런싱과 이중화를 통해 안정성을 강화한 아키텍처로 구성된 점이 인상깊었습니다.

배울 점이 정말 많았고, 실제 차량 소프트웨어 구조에 대해 이해할 수 있는 좋은 기회였답니다👍🏻

UX 아카이브 존

UX 아카이브 존에서는 과거와 현재의 인포테인먼트 시스템을 비교하여 UI가 어떻게 진화해왔는지를 한눈에 볼 수 있었어요.

어릴 적 아버지 차에서 봤던 익숙한 버튼 중심의 UI부터 요즘 차량에서 자주 보이는 화려한 터치 디스플레이의 UI까지 시간의 흐름에 따라 기술이 발전하면서 UX도 함께 진화해왔다는 것을 체감할 수 있는 공간이었습니다.

UX 라운지

전시를 마치고 올라온 2층 UX 라운지에서는 로봇 바리스타가 커피를 내려줬는데요! 그맛이 기가 막혀서 또 방문하고 싶었답니다..ㅎ

2층에는 현대자동차의 실제 랩실과 회의 공간을 구경할 수 있었는데요, 굉장히 깔끔하고 세련된 회의실에서 일하고싶다는 생각이 뿜뿜 했답니다🤩✨

그 외에도 GV70, IONIQ 6, IONIQ 9를 직접 타볼 수 있어 볼거리와 체험거리를 모두 잡은 전시였답니다!

제가 갔을때는 아쉽게도 UX 프로페셔널 (Professional) 과정이 오픈되지 않아 아이트래킹과 더 많은 UX를 체험해보지는 못했는데요, 7월 중순부터 오픈한다고 하니 관심있는 분들은 미리 예약하시고 가시는걸 추천드립니다!

문제상황

MacBook M1에서 Docker 이미지를 빌드한 뒤, 해당 이미지를 ECR에 푸쉬하고 이를 기반으로 k8s deployment를 생성하려했습니다.

하지만, Pod 생성시 이미지 다운로드 과정에서 오류가 발생했고, Pod는 ImagePullBackOff 상태에 머무르게 되는 상황이었습니다.

자체진단

1. Pod 상태를 확인해보았습니다.

kubectl logs -f << Pod 명 >> -n << namespace 명 >>

→ Pod가 생성조차 되지 못했기 때문에 Pod의 log를 확인하는 것이 불가능했습니다.

kubectl describe pod << Pod 명 >> -n << namespace 명 >>

→ k8s의 리소스 상태를 파악하기위해 describe 명령어를 사용해 확인해보았고

⇒ no match for platform in manifest: not found 오류는 이미지는 존재하지만 EKS 노드에서 실행할 수 있는 플랫폼에 맞는 이미지가 없어 생긴 문제였습니다.

MacBook M1 환경에서 이미지를 빌드했기 때문에 생성된 이미지는 inux/arm64 용 이지만, EKS는 일반적으로 linux/amd64이기 때문에 아키텍처가 맞지않아 이미지를 실행할 수 없는 문제로 보였습니다.

2. linux/amd64 아키텍처로 이미지를 다시 빌드한 뒤, ECR로 푸쉬하였습니다.

# linux/amd64 아키텍처로 이미지 빌드 명령어 
# --load 를 통해 local docker에 이미지 저장(이미지는 저장되지만 아키텍처가 달라 error를 띄운다)
docker buildx build --platform linux/amd64 -t << 이미지 명 >> --load .   

# EKS push 
docker push << 이미지 명 >>   

이후 deployment를 생성했더니 정상적으로 pod가 실행되는 것을 확인할 수 있었습니다.

배운점

지난 게시글을 통해 컨테이너 이미지의 아키텍처를 정확히 확인하는 것이 얼마나 중요한지 다시 한 번 깨달았습니다.

이번 경험을 통해 EKS의 노드는 기본적으로 linux/amd64 아키텍처를 사용한다는 사실을 알게 되었고, M1 Mac에서 빌드할 경우 별도로 아키텍처를 지정하지 않으면 linux/arm64로 생성된다는 점도 배울 수 있었습니다!

오늘도 해결!

문제상황

Dockerfile을 사용해서 jar 파일을 이미지로 생성하려고 했지만 Dockerfile 스크립트 내의 FROM openjdk:17-jdk-alpine as stage1이 문제가 되어 정상적인 이미지 생성이 불가한 문제였습니다.

ERROR: failed to solve: openjdk:17-jdk-alpine: failed to resolve source metadata for docker.io/library/openjdk:17-jdk-alpine: no match for platform in manifest: not found

자체진단

• openjdk:17-jdk-alpine와 eclipse-temurin:17-jdk-alpine 이미지는 ARM64(M1/M2) 아키텍처에 맞는 Alpine 태그를 제공하지 않기 때문에 m1 환경에서는 에러가 발생한 것이었습니다.

두 이미지 모두 x86_64 (Intel/AMD)만 지원하기 때문이죠.

![](https://velog.velcdn.com/images/illli_705/post/4573cbcc-ae8f-473b-bbc3-804058cfc01b/image.png)


이를 해결하기 위해 ARM64를 지원하는 Linux 기반 Java 이미지인 `eclipse-temurin:17-jdk`로 변경하였고, 해당 환경에서는 문제없이 jar 이미지 생성이 가능했습니다. 

배운점

문제는 간단하게 FROM eclipse-temurin:17-jdk로 바꾸는 것으로 해결할 수 있었지만, 한 가지 의문이 생겼습니다.

Docker는 어떤 OS든지 똑같이 실행환경을 보장하는 것이 장점이라 했는데, 왜 내 M1에서는 특정 이미지가 작동하지 않았는지 이해가 되지 않았습니다.

그에 대한 제가 찾은 답변입니다 :)

Docker는 운영체제에는 독립적이지만, CPU 아키텍처에는 종속적입니다.

즉, windows, mac, Linux 모두 Docker를 사용할 수 있지만 그 내부에서 사용하는 이미지는 해당 시스템의 CPU 종류와 맞아야합니다!

Docker인데 왜 내 CPU 아키텍처에 의존적일까?

도커 이미지는 운영환경과 실행 가능한 프로그램이 포함된 패키지입니다.

도커 이미지 내부에는

• 리눅스 사용자 공간: 쉘, 명령어 유틸리티
• 런타임 바이너리: 언어 실행기
• 파일 시스템 계층: 실제 프로그램 파일

하지만 이들은 모두 기계어로 컴파일된 바이너리 파일로 각각은 특정 CPU 아키텍처의 명령어 집합에 맞춰 만들어집니다.

즉, 이미지가 x86 아키텍처용으로 컴파일 되었다면, ARM64 아키텍처의 CPU는 그 명령어를 해석할 수 없기 때문에 해당 이미지를 실행할 수 없게 되는거죠!

물론, 대안으로 에뮬레이션을 활용하는 방법이 있지만 이것은 성능저하가 크기때문에 권장하지 않는 방법이라고 합니다.

따라서 설치하려는 이미지가 지원하는 CPU 아키텍처가 무엇인지를 확인하는것이 중요합니다.

Docker.. 알고 씁시다.. 😓

문제상황

진행 중인 프로젝트에서 Docker로 MySQL 컨테이너를 실행하면서 3306:3306 포트를 사용하도록 설정했습니다. 하지만 로컬 환경에서도 기존에 설치된 MySQL이 이미 3306 포트를 사용 중이었고, 이로 인해 intelliJ에서 적절한 DB를 찾지 못하며 생긴 문제입니다.

자체진단

기존 Docker에서 실행하는 포트를 3307:3306으로 변경해 진행을 했습니다.

→ 연결 문제를 해결할 수 있었지만, 로컬의 brew로 설치한 MySQL을 삭제해보았지만 여전히 3306으로 연결이 불가능한 상황입니다.

실제 해결 방안

1. 3306 포트로 실행 중인 프로그램을 확인해봤습니다.

lsof -i :3306 # 3306 포트로 실행 중인 프로그램 목록 확인 명령어 

→ 로컬의 mySQL과 Docker의 MySQL이 모두 3306 포트에서 다른 IP로 바인딩되어 실행 중이었습니다.

→ intelliJ는 Docker의 MySQL이 아닌 로컬 MySQL에 연결을 시도했기때문에 연결되지 않는 문제였죠!

2. 가장 위 mysqld가 문제라는 것을 찾았기 때문에 해당 프로그램을 종료해줍니다.

brew services stop mysql # brew로 실행중이던 mySQL 종료 

3. 해결

배운점

문제는 해결되었지만 두가지 의문이 있었습니다.

1. 어떻게 3306 포트에 여러개의 프로그램이 실행될 수 있었던걸까?
2. brew로 mySQL을 삭제했지만 왜 자동으로 3306으로 진행되던 brew의 mySQL은 종료되지 않았을까?

여기에 대해 제가 찾은 해답을 공유하겠습니다 :)

1. 어떻게 3306 포트에 여러개의 프로그램이 실행될 수 있었던걸까?

처음 문제가 발생했을때 MySQL Workbench로 3306 포트로 접속을 했더니 정상적으로 db에 접근이 되는 것을 보고 3306포트로 정상적으로 진행된다고 생각했습니다. 하나의 포트에 하나의 프로그램이 실행되어야한다고 알고 있었기 때문이죠.

하지만 실제로는 Docker로 띄운 MySQL 컨테이너도 같은 3306 포트를 사용 중이었습니다. 어떻게 이런 일이 가능했던걸까요?

포트와 IP 바인딩

• 하나의 포트 번호는 하나의 IP 주소 안에서만 고유합니다.
• 즉, 포트 번호 + IP 주소가 중복되지 않으면 여러 프로그램이 같은 포트를 사용할 수 있는거죠.

로컬의 MySQL은 127.0.0.1:3306 으로, Docker의 MySQL은 0.0.0.0:3306으로 같은 포트번호라도 접속을 받는 IP 주소가 다르기 때문에 두 프로그램이 충돌없이 실행될 수 있었던거에요.

아래 문제 상황을 하나씩 뜯어볼게요!

• mysqld 759 chan-il 21u IPv4 0x4f96304d9abbeaaa 0t0 TCP localhost:mysql (LISTEN) → 로컬 MySQL이 127.0.0.1:3306에서 접속을 기다리는 상태 → 내 컴퓨터에서만 접속 가능한 상태

• com.docke 995 chan-il 76u IPv6 0x1f638d94031049e5 0t0 TCP *:mysql (LISTEN) → Docker의 포트 포워딩 프록시가 *(0.0.0.0 모든 IP):3306에서 접속을 기다리는 상태 → 외부 IP를 포함한 모든 네트워크에서 접속 가능한 상태

• com.docke 995 chan-il 125u IPv6 0xf931d8ed9e81f23e 0t0 TCP localhost:mysql->localhost:50273 (ESTABLISHED) com.docke 995 chan-il 137u IPv6 0xd3dfd8e3011e0db1 0t0 TCP localhost:mysql->localhost:50274 (ESTABLISHED) → Docker 프록시가 localhost:3306으로 들어온 요청을 수신 → Docker 컨테이너 내부의 MySQL(3306)에 연결하기위해 내부적으로 50273,50274 임시 포트를 사용해 연결

• MySQLWork 1717 chan-il 13u IPv6 0xfe91934859180074 0t0 TCP localhost:50273->localhost:mysql (ESTABLISHED) MySQLWork 1717 chan-il 15u IPv6 0xaa9e580b2d8ead66 0t0 TCP localhost:50274->localhost:mysql (ESTABLISHED) → MySQL Workbench가 localhost:3306으로 연결을 시도 → 클라이언트 측에서 생성한 50273,50274 포트를 통해 Docker 프록시를 거쳐 Docker 컨테이너의 MySQL과 연결

결국 MySQLWorkbench는 localhost:3306으로 요청을 보냈지만, 이 요청을 Docker 프록시가 가로채 컨테이너 내부의 MySQL과 연결이 된 상태였기때문에 Workbench에서는 Docker의 MySQL이, intelliJ에서는 로컬의 MySQL이 연결된 상태가 되었던거죠..

2. brew로 MySQL을 삭제했는데 왜 자동으로 3306 포트에 실행되던 MySQL이 자동으로 종료되지 않았을까?

MySQL workbench로 3306 포트에 정상적으로 접속이 되고, 정상적으로 db를 생성했지만 연결되지 않는 문제를 보고 3306 포트에 다른 MySQL이 실행되고 있구나! 라는 의심을 했습니다.

제 로컬에는 brew로 설치된 MySQL이 있었기 때문에 terminal로 해당 프로그램을 삭제한다면 자동으로 종료될거라 생각하고 삭제만 하고 따로 확인하지 않았습니다. 이게 문제의 원흉이었죠!

그렇다면 왜 brew로 MySQL을 삭제했는데도 계속 실행되고 있었던 걸까요?

간단하게 이야기해보자면, macOS는 launchctl이라는 실행되는 프로그램을 시작/중지/등록/제거하는 서비스 관리 도구가 있습니다. 보통 brew에서 설치하는 프로그램들은 brew services start << program >> 라는 명령어로 진행하게 되는데요. 이때, launchctl을 통해 MySQL을 데몬으로 등록해 자동으로 실행하게 된다고합니다. 즉, 백그라운드에서 계속해서 실행되는 상태로 만드는거죠.

이렇게 MySQL이 데몬으로 실행되고 있었기때문에 의도한 DB로 접근이 되지 않았던거에요!

저는 brew uninstall mysql 을 통해 제거를 했지만 brew services stop mysql과는 별도의 작업이었던거죠..

앞으로는 데몬으로 실행 중인 프로그램이 있는지 brew services list 나 launchctl list 명령어를 통해 실행 상태를 꼭 확인하고,

필요하다면 brew services stop [프로그램명] 또는 launchctl remove [서비스명]으로 명시적으로 종료하는 습관을 들여야겟습니다

결국 내가 접속한 대상이 무엇인지 포트만 보고는 알 수없다는 것을 배웠습니다.

포트를 의심하기전에 IP 주소를 먼저 확인하는 습관을 들입시다!

Docker 알고 사용합니다!

WebSocket을 사용하는데 있어 왜 필요한지, WebSocket이 무엇인지에 대해 공부해보았습니다!

WebSocket 왜 필요할까?

WebSocket의 필요성을 이해하기 위해, 흔히 사용하는 HTTP 통신 방식과 비교해보며 그 차이를 쉽게 이해할 수 있었습니다.

HTTP 통신의 단방향성

HTTP 통신은 클라이언트가 서버에 요청을 보내면 서버에서 이에 해당하는 응답을 보내주는 구조입니다. 즉, 클라이언트가 요청해야만 서버가 응답할 수 있는 단방향 통신 방식이라는 특징이 있습니다.

하지만, 채팅, 알림, 실시간 데이터 표시 기능처럼 실시간으로 클라이언트와 서버 간의 양방향 통신이 필요한 경우, HTTP 통신 방식으로는 한계가 있습니다. HTTP는 클라이언트가 요청해야만 서버가 응답할 수 있기 때문에 서버가 임의의 시점에 클라이언트에게 데이터를 보내는 것이 불가능합니다. 이는 곧, 실시간성이 중요한 기능들에서는 제약으로 작용하게 됩니다.

HTTP 통신의 대안

그렇다면 HTTP 통신으로는 실시간 통신과 유사한 기능을 구현하지 못하는 걸까요?

꼭 그렇지는 않습니다. 앞서 언급했듯이, 서버가 클라이언트에게 응답을 보내기 위해서는 클라이언트의 요청이 선행되어야한다고 했는데요, 그렇다면 클라이언트가 일정 주기로 계속해서 서버에 요청을 보내면 되지 않을까요?

맞습니다. 해당 방식을 사용한다면 실시간과 유사한 효과를 낼 수 있으며, 대표적으로 다음과 같은 방식들이 존재합니다

WebSocket

이러한 점들을 종합해 볼 때, WebSocket은 실시간 통신의 적합한 기술이 될 수 있습니다.

WebSocket은 서버와 클라이언트간 메시지 교환을 위한 통신 규약입니다.

WebSocket의 특징

• 양방향성(Full-Duplex): 클라이언트와 서버가 동시에 데이터를 송수신할 수 있어 실시간 상호작용이 가능합니다.
• 실시간성(Real-Time Networking): 연결을 유지한 상태에서 즉각적으로 데이터 전송이 가능하므로 실시간으로 데이터 전달이 가능합니다.
  

WebSocket 동작 과정

WebSocket 동작 과정은 크게 연결, 통신, 종료 세가지로 나눌수 있습니다.

연결

여기서 중요한 점은 WebSocket 연결의 시작은 항상 HTTP 통신으로 이루어진다는 점입니다.

1. 클라이언트 → 서버: 업그레이드 요청(HTTP GET) 클라이언트는 기존의 HTTP 통신을 WebSocket 통신으로 바꾸기 위해 서버에게 HTTP ‘Connection: Upgrade, Upgrade: webSocket’ 헤더가 포함된 GET 요청을 보냅니다.

   (ws://로 요청을 보내는 것으로 보이지만, 실제로는 HTTP 1.1 기반 GET 요청으로 진행됩니다!)

   

   2. 서버 → 클라이언트: 101 Switching Protocols 응답

   서버가 해당 업그레이드 요청을 수락하면 HTTP 상태코드 101 Switching Protocols를 응답하며 WebSocket 프로토콜로 통신을 전환하게 됩니다.

   

   3. WebSocket 연결 성립

통신

연결이 이루어지면 헤더와 바디로 이루어졌던 HTTP 통신과 달리 ‘메시지’라는 단위로 데이터 전달이 이루어지게 됩니다.

즉, HTTP 통신보다 가벼운 통신이 진행되는거죠!

• 메시지(Message) WebSocket 연결이 성립된 후 프레임이라는 하위 단위를 통해 메시지를 송수신합니다. 하나의 메시지는 하나 이상의 프레임으로 구성되며 클라이언트와 서버는 메시지를 실시간으로 주고받게됩니다.

hi 라는 메시지를 보내보았습니다 :)

종료

클라이언트와 서버는 연결을 종료할때 각각 컨트롤 프레임(Control Frame)을 전송할 수 있습니다.

WebSocket 연결 종료는 HTTP가 아닌 ws를 통해 이루어지며 이때 Close Frame이라는 WebSocket 전용 제어 프레임을 주고받으며 연결이 종료됩니다.

클라이언트가 topic 1에 대한 구독을 종료하며 websocket 통신을 종료하는 것을 확인할 수 있었습니다 :)

이렇게 WebSocket에 대해서 공부해보았습니다. 저에게 ‘채팅’이라는 기술이 추가되어서 뿌듯합니다. ㅎㅎ

[참고]

https://doozi0316.tistory.com/entry/WebSocket%EC%9D%B4%EB%9E%80-%EA%B0%9C%EB%85%90%EA%B3%BC-%EB%8F%99%EC%9E%91-%EA%B3%BC%EC%A0%95-socketio-Polling-Streaming

https://d2.naver.com/helloworld/1052

https://sendbird.com/ko/developer/tutorials/websocket-vs-http-communication-protocols

문제상황

BCryptPasswordEncoder 사용해 encode한 비밀번호를 DB에 저장하고 passwordEncoder.mathes 를 사용해 비교한 결과를 토대로 로그인 여부를 확인하려 했지만 같은 비밀번호를 입력함에도 비밀번호가 틀렸다는 오류를 return

Code

• 회원가입
• 로그인

자체진단

1. 저장할때 비밀번호가 DB에 저장되는 비밀번호와 일치하는지 확인 테스트로 확인 → 모두 통과 = 회원 가입, 로그인 로직에는 문제 없음

2. 프론트단에서 올바른 데이터를 던져주는지 확인 v-model로 받는 부분에서 password를 email로 받고 있어 오류가 생김

배운점

1. BCryptPasswordEncoder

BCryptPasswordEncoder는 비밀번호를 해시화할 때마다 랜덤한 salt를 자동으로 생성하여 적용하기 때문에, 같은 비밀번호라도 해시 결과는 매번 달라집니다. → 따라서 일반적인 문자열 비교 (equals)를 사용할 수 없으며, 대신 passwordEncoder.matches(원문, 해시값) 메서드를 사용해 비밀번호 일치 여부를 검증합니다.

❓어떻게 가능할까? → 이는 BCrypt 알고리즘의 특성 덕분인데, BCrypt는 해시 문자열 내부에 salt와 해싱 라운드 정보가 포함되어 있어서, 저장된 해시에서 salt와 해싱 횟수를 추출해 입력된 비밀번호 원문을 같은 방식으로 해시를 수행해 DB에 저장된 비밀번호와 비교하는 방식을 사용하기 때문입니다.

2. @Transactional 어노테이션

@Transactional은 데이터베이스 트랜잭션 관리 방법을 제공하는 어노테이션입니다. 메서드 단독으로 사용하거나 클래스 내 모든 public 메서드에 적용이 될 수 있습니다. @Transactional이 붙은 메서드는 메서드를 실행할때 트랜잭션을 시작하고, 메서드가 정상적으로 종료되면 commit, 예외가 발생하면 트랜잭션을 rollback하게됩니다. 즉, 데이터의 일관성과 무결성을 지켜주는 역할을 한다고 볼 수 있습니다. → ‼️ Transaction 어노테이션을 사용할때 주의해야할 몇가지 사항이 있습니다.
1. 트랜잭션을 적용하려는 메서드는 반드시 public으로 선언되어야 합니다. 2. Checked Exception은 rollback 대상이 아닙니다. 3. 되도록이면 Service 계층에서 사용해야합니다.

또 하나의 문제 해결!

문제설명

풀이방식

1. BFS를 2번 수행해 문제를 풀려한다. why? → 불이 번지기 전에 지훈이가 탈출해야하는데, 불은 매분 한칸씩 번지기 때문에 불이 번지는 시간을 먼저 체크한 뒤, 지훈이가 이동하며 지훈이의 이동시간과 불이 번진 시간을 비교할 생각이다.

2. 동일한 방식으로 BFS를 수행하되, 다음 노드를 탐색하는 조건에서 약간의 차이가 있다.

• 불이 번지는 경우 빈 땅일 경우만 탐색하면 되기 때문에 문제 없다.
• 지훈이의 경우 다음 땅에 도달할때 불보다 빨리 도착해야하기 때문에 map[nx][ny] > 지훈이가 다음땅에 도달할 시간 이어야한다. 위의 조건 때문에 visited 배열을 따로 두어 방문한 곳을 다시 방문하지 않도록 해야한다.

코드

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int col = Integer.parseInt(st.nextToken());
        int row = Integer.parseInt(st.nextToken());
        int[][] map = new int[row][col];
        boolean[][] visited = new boolean[row][col]; // 지훈용
        ArrayDeque<int[]> q = new ArrayDeque<>(); // x, y, fs
        int sx = 0;
        int sy = 0;

        for (int i = 0; i < row; i++) {
            String str = bf.readLine();
            for (int j = 0; j < col; j++) {
                char c = str.charAt(j);
                if (c == 'J') {
                    sx = i;
                    sy = j;
                    map[i][j] = -1; // 시작점
                } else if (c == 'F') {
                    map[i][j] = -2; // 불
                    q.offer(new int[]{i, j, 0});
                } else if (c == '#') {
                    map[i][j] = -3; // 벽
                } else {
                    map[i][j] = 0; // 번질 수 있는 곳
                }
            }
        }

        int[] dr = new int[]{-1, 1, 0, 0};
        int[] dc = new int[]{0, 0, -1, 1};

        // 불 점화
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];
            int cf = cur[2];

            for (int i = 0; i < 4; i++) {
                int nx = cx + dr[i];
                int ny = cy + dc[i];
                int nf = cf + 1;

                if (nx > -1 && nx < row &&
                        ny > -1 && ny < col &&
                        map[nx][ny] == 0) {
                    q.offer(new int[]{nx, ny, nf});
                    map[nx][ny] = nf;
                }
            }
        }

        q.offer(new int[]{sx, sy, 0});
        int min = Integer.MAX_VALUE;
        visited[sx][sy] = true;
        boolean escape = false;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];
            int cf = cur[2];

            // 가장 먼저 접하는게 가장 빠른 경우 아닐까
            if (cx == row - 1 || cx == 0 || cy == col - 1 || cy == 0) {
                min = cf;
                escape = true;
                break;
            }

            for (int i = 0; i < 4; i++) {
                int nx = cx + dr[i];
                int ny = cy + dc[i];
                int nf = cf + 1;

                if (nx > -1 && nx < row && ny > -1 && ny < col &&
                    map[nx][ny] != -3 && // 벽이 아니고
                    map[nx][ny] != -2 && // 불도 아니고
                    (map[nx][ny] > nf || map[nx][ny] == 0) &&
                    !visited[nx][ny]){// 불보다 빨리 도착하거나 불이 도달하지 않았거나
                    q.offer(new int[]{nx, ny, nf});
                    visited[nx][ny] = true;
                }
            }
        }

        if (escape) System.out.println(min + 1);
        else System.out.println("IMPOSSIBLE");
    }
}

DFS 정복주를 지나고 있는데 어느정도 난이도가 있는 문제도 풀어낼 수 있다는게 뿌듯하다! 화이링링~

시간을 두고 총 3번 문제를 풀었습니다. 효율성 면에서는 3회차 > 1회차 > 2회차 가 가장 좋았으며 삽입과 삭제 면에서 뛰어난 LinkedList를 실제로 사용해볼 수 있어 좋았습니다..!

문제설명

• 주어진 파라미터: int cacheSize, String[] cities
• 반환값: int
• cities를 순회하며 cacheSize만큼 캐시 저장한 뒤, LRU 방식에 맞게 실행시간 측정
• 캐시 히트: 1 / 캐시 미스: 5

풀이방식

1. Queue를 이용해서 캐시 구현
2. LRU 방식에 맞게 Queue 내에 있을 경우 해당 요소만 빼고 맨 뒤 삽입 (1회차) Queue 1개 사용, 총 4가지 경우의 수(q내에 있는 경우, 없는 경우 + 캐시 사이즈 초과 / 미만) (2회차) Queue 1개, List 1개 사용, Queue를 통해 contains를 확인할 수 있었지만.. 그러지 않고 굳이 List 사용 (3회차) LinkedList 1개 → 중간 삭제면에서 가장 뛰어난 속도를 보여줌

코드

• 1회차 Queue 1개 사용 총 4가지 경우의 수(q내에 있는 경우, 없는 경우 + 캐시 사이즈 초과 / 미만)

/*
1. 없다 -> q 개수 x / q 개수 o
2. 있다 ->
*/
import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        Queue<String> q = new ArrayDeque<>();
        int answer = 0;

        if (cacheSize == 0) return cities.length * 5;

        for(int i = 0; i < cities.length; i++){
            String c = cities[i].toLowerCase();

            if(!q.contains(c)){
                if(q.size() < cacheSize){
                    q.offer(c);
                }else{
                    q.poll();
                    q.offer(c);
                }

                answer += 5;
            }else{
                if(q.size() < cacheSize){
                    int len = q.size();
                    for(int j = 0; j < len; j++){
                        String cur = q.poll();
                        if(cur.equals(c)) continue;
                        q.offer(cur);
                    }
                    q.offer(c);
                }else{
                    for(int j = 0; j < cacheSize; j++){
                        String cur = q.poll();
                        if(cur.equals(c)) continue;
                        q.offer(cur);
                    }
                    q.offer(c);
                }

                answer += 1;
            }
        }

        return answer;
    }
}

• 2회차 Queue 1개, List 1개 사용 Queue를 통해 contains를 확인할 수 있었지만.. 그러지 않고 굳이 List 사용

  import java.util.*;
  // Queue, ArrayList -> queue안에 있는지 확인 
  

class Solution { public int solution(int cacheSize, String[] cities) { ArrayList list = new ArrayList<>(); ArrayDeque queue = new ArrayDeque<>(); int playTime = 0;

    if(cacheSize == 0 ) return cities.length * 5;

    for(String city : cities ){
        city = city.toLowerCase();

        if(list.size() < cacheSize){
           // 캐시가 차지 않았을 때 
            if(list.contains(city)){
                // 캐시에 있을 경우 
                ArrayDeque<String> stack = new ArrayDeque<>();
                while(!queue.peekFirst().equals(city)){
                    stack.push(queue.poll());
                }

                queue.poll();
                while(!stack.isEmpty()){
                    queue.addFirst(stack.pop());
                }
                queue.offer(city);
                playTime += 1;
            }else{
                // 캐시에 없을 경우 
                queue.offer(city);
                list.add(city);
                playTime += 5;
            }

        }else if(list.size() >= cacheSize){

            // 캐시 가득 찬 경우 
            // 캐시 내 있는 경우 
            if(list.contains(city)){
                ArrayDeque<String> stack = new ArrayDeque<>();
                while(!queue.peekFirst().equals(city)){
                    stack.push(queue.poll());
                }

                queue.poll();
                while(!stack.isEmpty()){
                    queue.addFirst(stack.pop());
                }
                queue.offer(city);
                playTime += 1;

            }else{
                // 캐시 내 없는 경우 
                String deleteCity = queue.poll();
                list.remove(deleteCity);
                queue.offer(city);
                list.add(city);
                playTime += 5;
            }
        }
    }

    return playTime;
}

}

- 3회차 ![](https://velog.velcdn.com/images/illli_705/post/0380b3fc-d238-400e-b5c7-dd7814bc4805/image.png)

LinkedList 1개
중간 요소 삭제 면에서 가장 뛰어난 속도를 보여줌 

import java.util.*;

class Solution { public int solution(int cacheSize, String[] cities) { LinkedList list = new LinkedList<>(); int playTime = 0;

    if(cacheSize == 0) return cities.length * 5;

    for(String city : cities){
        city = city.toLowerCase();

        if(list.remove(city)){
            playTime += 1;
        }else{
            if(cacheSize == list.size()) list.removeFirst();
            playTime += 5;
        }

        list.addLast(city);
    }

    return playTime;
}

}

```

시간을 두고 총 3번 문제를 풀었습니다. 효율성 면에서는 3회차 > 1회차 > 2회차 가 가장 좋았으며 삽입과 삭제 면에서 뛰어난 LinkedList를 실제로 사용해볼 수 있어 좋았습니다..!

특히, B- 트리는 검색, 삽입, 삭제 연산 시에도 항상 균형을 유지하면서도 디스크 접근 횟수를 최소화 하도록 설계된 구조입니다.

조금 더 정확하게 표현하면 M차 B트리는 다음 조건을 만족해야합니다.

• 루트 노드를 제외한 모든 내부 노드는 최소 ceil(M/2) ~ M 개의 자식 노드를 가져야합니다.
• 하나의 노드에 저장되는 키의 개수는 자식 수 -1개로 최소 ceil(M/2)-1 ~ M-1개 입니다.
• 모든 리프 노드는 동일한 깊이에 위치합니다.
• 모든 키는 정렬된 상태로 유지됩니다.

3차 B- 트리를 예로 들자면 노드 당 키의 개수는 ceil(3/2)-1 ~ 3-1개(1~2) 노드 당 ceil(3/2) ~ 3개(2~3)의 자식을 가질 수 있습니다.

1. 데이터 검색

B- 트리에서 데이터 검색은 root 노드부터 시작해 하향식으로 검색하게 됩니다.

1. 먼저 루트 노드를 살펴보고, 찾고자 하는 데이터가 있는지 확인합니다.
2. 데이터가 없다면, 해당 키의 크기를 기준으로 적절한 자식 노드 방향을 선택해 내려갑니다.
3. 이 과정을 리프 노드까지 반복하며 탐색하고,
4. 리프 노드에 도달했음에도 원하는 데이터가 없다면, 해당 데이터는 트리 내에 존재하지 않는 것입니다.

위 B 트리에서 15를 검색해 본다면,

1. 먼저 루트 노드를 살펴보고, 찾고자 하는 데이터가 있는지 확인합니다. → 5, 21이 아닙니다.
2. 데이터가 없다면, 해당 키의 크기를 기준으로 적절한 자식 노드 방향을 선택해 내려갑니다. → 5와 21 사이 노드 방향으로 내려갑니다.
3. 이 과정을 리프 노드까지 반복하며 탐색하고, → 11이 아니므로 11보다 큰 자식 노드 방향으로 내려갑니다.
4. 리프 노드에 도달했음에도 원하는 데이터가 없다면, 해당 데이터는 트리 내에 존재하지 않는 것입니다. → 15를 찾았습니다.

2. 데이터 삽입

B- 트리에서 데이터 삽입은 항상 리프 노드에서 시작되며, 검색과는 달리 상향식으로 처리됩니다.

앞서 언급했듯이, B- 트리의 각 노드는 ceil(M/2)-1 ~ M-1 개의 데이터를 저장할 수 있습니다. 따라서 삽입으로 인해 해당 범위를 초과하게 되면, 노드를 분할하게 되고, 중간키를 부모 노드로 올리는 구조적 조정이 필요합니다.

• 삽입 과정

1. 트리가 비어있다면 루트 노드를 할당하고 데이터를 삽입한다.
2. 트리가 비어있지 않다면, 데이터를 넣을 적절한 리프 노드를 탐색한다.
3. 리프 노드에 데이터를 넣고 리프 노드가 적절한 상태에 있다면 종료한다.
4. 리프 노드가 부적절한 상태에 있다면 분리한다.

*부적적한 상태: 각 노드 당 데이터 개수가 ceil(M/2)-1 ~ M-1 범위를 넘어서는 상태

그럼 삽입 과정을 크게 2가지 케이스로 분리해 적용해보겠습니다.

< 노드 분할이 필요 없는 경우 >

위 예시 B- 트리에 16을 삽입해보겠습니다.

(3차 B트리이므로, 노드 당 가능한 데이터 범위는 1~2개입니다.)

1. 트리가 비어있다면 루트 노드를 할당하고 데이터를 삽입한다. → 루트가 비어있지 않습니다.

2. 트리가 비어있지 않다면, 데이터를 넣을 적절한 리프 노드를 탐색한다.

   → 5, 21 사이 자식 노드로 내려갑니다.

   → 1보다 넣으려는 데이터(16)이 크기 때문에 큰 자식 노드로 내려갑니다.

3. 리프 노드에 데이터를 넣고 리프 노드가 적절한 상태에 있다면 종료한다.

   → 15보다 크기 때문에 15 오른쪽에 데이터를 삽입합니다.

   → 노드 당 가능한 데이터 범위 내에 있기 때문에 삽입 과정을 종료합니다.

이처럼, B- 트리 삽입 과정에서 리프 노드에 키가 과도하게 많아질 경우, 가운데 키를 부모 노드로 올리고, 부모 노드 역시 조건을 초과하는지 계속 확인하며, 필요한 경우 상위 노드까지 분할을 반복하게 됩니다.

이러한 과정을 통해 B- 트리는 삽입 후에도 항상 노드의 키 개수와 자식 수 조건을 만족하는 균형 구조를 유지합니다.

3. 데이터 삭제

B- 트리에서는 균형을 맞추기위해 항상 아래 조건을 만족하는 것이 중요합니다.

• 내부 노드는 ceil(M/2) ~ M개의 자식을 가질 수 있다.
• 각 노드는 ceil(M/2)-1 ~ M-1개의 데이터를 가질 수 있다.
• 각 노드 데이터가 K개라면 K+1개의 자식노드를 가진다.

하지만, 데이터가 삭제되면서, 어떤 노드는 최소 데이터 개수나 자식 수 조건을 만족하지 못하는 경우가 발생합니다. 이런 경우에는 형제 노드나 부모 노드로부터 데이터를 가져오거나(재배치) 노드를 병합(병합)하는 등의 조치를 통해 균형을 다시 맞춰야합니다.

각 경우에 따른 과정을 살펴보겠습니다.

< 리프 노드에서 삭제되어도 문제 없는 경우 >

리프 노드에서 삭제되어도 B- 트리 조건을 모두 만족할 경우 그냥 삭제만 해줘도 문제가 없습니다.

위 B- 트리에서 15나 16 둘 중 하나만 삭제할 경우 최소 노드 당 데이터 수가 지켜지기 때문에 문제가 없습니다.

< 리프 노드 삭제 시 최소 유지 개수를 만족하지 못하지만, 형제 노드에서 값을 빌려올 수 있는 경우 >

위 B- 트리에서 21을 삭제할 경우, 최소 노드 당 데이터 개수가 지켜지지 않지만, 23보다 큰 노드에서 31의 값을 23의 위치와 교환한 후, 23을 31의 왼쪽 자식 노드로 둠으로써 조건을 충족시킬 수 있습니다.

→ 회전이 된 것처럼 보입니다!

< 리프 노드가 아닌 내부 노드에서 삭제할 경우 >

위 B- 트리에서 5를 삭제할 경우, 3의 노드가 최소 데이터 개수를 충족시키지 않기 때문에 자식노드 7을 부모 노드로 올려 3,7이 부모노드가 되고, 나머지 1,4,11이 자식 노드가 되며 조건이 충족되는 것을 알 수 있습니다.

< 내부 노드 삭제 시, 현재 노드와 자식 노드 개수 모두 최소인 경우 >

하지만, 부모와 자식 노드가 모두 최소 개수일 경우 노드를 끌어올 수 없습니다.

위 B- 트리에서 4를 삭제할 경우 부모, 자식 어느 노드에서도 끌어올 수 없습니다.

이 경우, 4를 삭제한 뒤,

1. 자식 노드들을 하나의 노드로 합칩니다. → 1, 11
2. 이후, 삭제된 값의 부모 노드를 삭제된 값의 형제 노드에 합칩니다. → 15를 31의 형제로 합칩니다.
3. 이후, 해당 부모 노드를 이전의 자식 노드들과 연결합니다. → 1,11 노드를 15의 자식 노드로 연결합니다.
4. 만약 이 과정에서 부모 노드의 데이터 수가 조건을 충족시키지 못한다면 그 부모 노드로 올라가며 2번 과정을 반복합니다.

삭제 규칙

위 과정을 살펴보면 모든 삭제는 리프에서 발생하며, 균형을 회복하기 위해 재분배나 병합등의 방식을 사용하는 것을 알 수 있습니다.

1. 삭제할 키를 리프까지 옮깁니다.

   • 삭제 대상이 리프에 없다면 전임자(Predecessor) 또는 후임자(Successor)와 값만 교체한 뒤, 실제 삭제는 리프에서 진행합니다.
   • 전임자 = 왼쪽 자식에서 가장 큰 값
   • 후임자 = 오른쪽 자식에서 가장 작은 값
     

2. 리프 노드에서 삭제합니다.

   • 삭제 후 해당 노드의 Key 수가 최소 개수 미만인지 확인합니다.
     

3. 균형을 회복합니다.(재분배 or 병합) 1) 형제 노드가 최소 개수보다 더 많은 Key를 가지고 있을 경우 → 하나 빌려와서 균형 맞추기

   • 왼쪽 형제에게 빌릴 경우 → 부모의 Key 내려오고 형제의 Key 올라감
   • 오른쪽 형제에게 빌릴 경우 마찬가지

   2) 형제도 최소 개수라 빌릴 수 없는 경우 → 형제 + 부모 Key 하나 포함해 병합

   • 부모에서 Key 하나 빠짐
   • 이로 인해 부모 노드도 Key가 부족할 수 있기 때문에 재귀적으로 위로 올라가며 처리

※ 참고

https://code-lab1.tistory.com/217 https://www.cs.usfca.edu/~galles/visualization/BTree.html

문제설명

• 주어진 파라미터: String[] park, String[] routes
• 반환값: int[]
• 로봇 강아지 상책 → 입력된 명령 따라 진행
• 공원 벗어나는지, 장애물 만나는지 확인 → 명령 무시 & 다음 명령 수행

풀이방식

1. S로 시작 위치 찾기
2. 명령어 돌면서 N E W S 분기별 Cnt 만큼 이동 → X, 범위를 넘어가는지 확인 → 넘어가지 않을 경우 해당 값으로 변경

   코드

class Solution {
    public int[] solution(String[] park, String[] routes) {
        int row = park.length;
        int col = park[0].length();
        int curX = 0;
        int curY = 0;

        // 시작 위치 찾기
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(park[i].charAt(j) == 'S'){
                    curX = i;
                    curY = j;
                    break;
                }
            }
        }

        for(String str : routes){
            String[] split = str.split(" ");
            String dir = split[0];
            int cnt = Integer.parseInt(split[1]);
            int nextX = curX;
            int nextY = curY;
            boolean flag = true;

            if(dir.equals("N")){
                for(int i = 0 ; i < cnt; i++){
                    nextX -= 1;
                    if(nextX < 0 || park[nextX].charAt(nextY) =='X'){
                        flag = false;
                        break;
                    }
                }
                if(flag) curX = nextX;

            }else if(dir.equals("S")){
                for(int i = 0 ; i < cnt; i++){
                    nextX += 1;
                    if(nextX >= row || park[nextX].charAt(nextY) == 'X'){
                        flag = false;
                        break;
                    }
                }
                if(flag) curX = nextX;

            }else if(dir.equals("E")){
                for(int i = 0 ; i < cnt; i++){
                    nextY += 1;
                    if(nextY >= col || park[nextX].charAt(nextY) == 'X'){
                        flag = false;
                        break;
                    }
                }
                if(flag) curY = nextY;

            }else{ // "W"
                for(int i = 0 ; i < cnt; i++){
                    nextY -= 1;
                    if(nextY < 0 || park[nextX].charAt(nextY) == 'X'){
                        flag = false;
                        break;
                    }
                }
                if(flag) curY = nextY;
            }
        }

        return new int[]{curX, curY};
    }
}![](https://velog.velcdn.com/images/illli_705/post/2f271296-8daf-4471-8878-9e612002f3c5/image.png)

문제설명

• 주어진 파라미터: int[] order
• 반환값: int 실을 수 있는 택배 수
• 벨트에 놓인 순서대로 꺼낼 수 있음
• 미리 알려준 순서에 맞게 실어야함
• 순서 다르면 다른 곳에 보관 가능 → stack 형 보관함

풀이방식

1. 보관함을 Stack으로 구현
2. 1부터 Order.length 까지 반복하며 확인
   • 일치할 경우 answer++
   • 일치하지 않을 경우 stack에 넣기
3. Stack의 Peek와 order[idx]를 비교해서 같은지 확인하기 → answer++

코드

import java.util.*;

class Solution {
    public int solution(int[] order) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int answer = 0;
        int len = order.length;
        int idx = 0;

        for (int i = 1; i <= len; i++) {
            if (order[idx] == i) {
                answer++;
                idx++;
            } else {
                stack.push(i);
            }

            while (!stack.isEmpty() && stack.peek() == order[idx]) {
                stack.pop();
                answer++;
                idx++;
            }
        }

        return answer;
    }
}![](https://velog.velcdn.com/images/illli_705/post/251b903a-1749-4855-8e5c-06c37608d7b5/image.png)

1. 이진수로 실수를 표현하는 법

컴퓨터는 이진수로 이루어진 명령어만 이해하기 때문에 실수 또한 2진수로 변경이 가능해야합니다. 실수는 정수부와 소수부로 이루어져있으며, 이 둘은 2진수로 변환하는 방식이 서로 다릅니다.

먼저, 정수부의 경우 해당 값이 몇개의 2의 거듭 제곱으로 이루어져있나 를 확인하는 과정이기 때문에 2를 나눠주며 나머지를 활용해 2진수를 구합니다.

소수부의 경우 정수부와 반대로 2의 음수 제곱을 얼마나 포함하는가를 확인하는 과정이기 때문에 2를 곱해주며 오버플로우가 나는 것을 활용해 2진수를 구하게 됩니다.

그럼 그 과정을 예시를 들어 보여드리겠습니다.

11.765625

• 정수부: 11

• 소수부: 0.765625

위 과정을 통해 정수부와 소수부의 이진수 변환이 이루어졌고, 둘을 합쳐줌으로써 11.765625 라는 10진수 표현식은 1011.110001(2) 이라는 2진수로 표현될 수 있다는 것을 확인할 수 있습니다.

2. 무한 소수

실수에는 일정 패턴이 반복되거나 같은 수가 무한히 반복되는 ‘무한소수’라는 개념도 있습니다. 하지만, 컴퓨터 메모리의 특성상 무한한 수를 저장할 수는 없기 때문에 10진수의 소수를 2진수로 변환할 때 많은 경우 정확한 변환이 불가능합니다.

0.1의 경우 2진수로 변환했을때 무한히 반복되는 것을 확인할 수 있습니다.

→ 대다수의 수는 정확하게 2진수로 변환이 어려우며 소수의 끝이 5가 아닌 수를 2진수로 표현할 경우 무한 소수가 발생한다고 볼 수 있습니다.

3. 실수의 메모리 표현

지금까지 10진수의 실수를 2진수로 변환하는 방법에 대해 알아보았습니다.

변환된 2진수 실수는 컴퓨터 메모리에 저장될 때 고정소수점 방식, 부동소수점 방식 중 하나로 저장됩니다.

고정 소수점 방식(Fixed-Point Number Representation)

고정 소수점 방식은 소수점 자릿수가 고정된다는 의미로 실수를 정수부와 소수부로 나누어 저장하는 방식을 말합니다.

32bit 기준으로 보았을때 부호(1bit) + 정수부(15bit) + 실수부(16bit)로 구성됩니다.

부동 수수점 방식(Fixed-Point Number Representation)

부동 소수점 방식은 소수점의 위치가 정해져 있지 않았다는 의미에서, 숫자를 가수부와 지수부로 나누어 표현하는 방식입니다.

32bit 기준으로 보았을때 부호(1bit) + 지수부(8bit) + 가수부(23bit)로 구성됩니다.

지수부는 소수점의 위치(크기)를 결정하는 역할을 하며, 가수부는 실제 숫자의 유효 자릿수를 나타냅니다.(가수부는 1.xxx 형태로 표현되며 해당 소수점을 기준으로 지수부가 결정됩니다.)

• 부동 소수점 계산 방법(정규화) 부동 소수점 방식은 IEEE 754 표준을 따르며 수식은 다음과 같습니다.

  m은 가수부를, e는 지수부를 의미합니다.

  부동소수점 방식은 실수를 저장할 때, 변환된 2진수를 지수 표현식 형태로 바꾸는 정규화(Normalization) 과정을 거친 후, 그 결과를 부호 비트, 지수부, 가수부로 나누어 메모리에 저장합니다.

  -118.625 를 부동소수점 방식으로 변경해보겠습니다.

  이때, 지수부에는 고정된 값인 bias(127)을 더해 저장하게 되는데, 이것은 지수가 음수가 될 수 있는 경우를 고려한 설계입니다.

  127이라는 bias 값을 더해줌으로써 0127은 음수를, 128255는 양수를 표현할 수 있게 됩니다.

3. 소수의 계산 오차

앞서 언급했듯이, 소수의 끝자리가 5로 끝나지 않거나 무한히 반복되는 경우, 컴퓨터는 표현 가능한 비트수의 한계로 모든 자릿수를 정확히 저장할 수 없습니다.

이로 인해 마지막 자릿수에 반올림이 발생하고, 결과적으로 부정확한 실수 값이 저장되게 됩니다.

10진수를 2진수로 변환하는 과정 자체는 고정소수점과 부동소수점 모두 동일하기 때문에 두가지 방식 모두 오차가 발생하는 근본적 원인은 같습니다.

그렇다면 왜? 부동소수점이 고정소수점보다 더 부정확하다는 말이 나오는걸까요?

부동소수점은 가수부와 지수부로 나뉘며, 소수점의 위치가 고정되지않은 방식이라는 것을 앞서 살펴보았습니다. 하지만, 가수부는 23 Bit 내에 전체 수를 저장해야하기 때문에 값이 커질수록 정수부에 비해 비교적 크기가 작은 소수부의 경우 반올림 과정을 통해 표현하게 됩니다.

이것은 넓은 수의 범위를 표현하기위해 정밀도를 희생한 구조이기 때문입니다.

부동소수점은 1.x * 2^e 형태로 e(지수부)가 커질수록 소수점은 오른쪽으로 이동하게 됩니다.

이 경우, 가수부의 비트가 정수부 표현에 더 많이 사용되게 되면서, 소수부에서 사용할 수 있는 비트수가 줄어들게되고 결과적으로 정밀도가 떨어지게 됩니다.

반대로, 고정소수점은 소수점의 위치가 고정되어있기 때문에, 값이 커지더라도 정수부와 소수부에 배정된 비트수는 변하지 않습니다. 즉, 고정소수점 방식은 값이 커지더라도 소수부의 정밀도는 동일하기 때문에 값이 커질수록 부동소수점보다 값이 정확하다는 말이 나오는 것입니다

실수? 이제 알고 사용하자구요~

문제설명

• 파라미터: int[][] board, int[] moves
• 반환값: int
• 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return

풀이방식

1. 각 줄마다 Stack을 적용해 거꾸로 인형을 넣어준다.
2. moves를 토대로 꺼내면서 answerStack의 peek와 비해한다.
   • 같다면 answerStack에서 뽑아주고 answer += 2를 진행한다.
   • 다르다면 해당 인형을 answerStack에 추가한다.

코드

import java.util.*;
class Solution {
    public int solution(int[][] board, int[] moves) {
        int len = board.length;
        List<Stack<Integer>> list = new ArrayList<>(); // 0부터 시작
        Stack<Integer> store = new Stack<>();
        int answer = 0;

        for(int i = 0; i < len; i++){
            list.add(new Stack<>());
        }

        // 각 스택에 인형 넣기 
        for(int i = len -1 ; i > -1; i--){
            for(int j = 0; j < len; j++){
                if(board[i][j] != 0) list.get(j).push(board[i][j]);
            }
        }

        // moves 돌며 하나씩 answerStack peek와 비교하기 
        for(int i : moves){
            int curIdx = i-1;
            if(list.get(curIdx).size() == 0) continue;

            int curItem = list.get(curIdx).pop();
            if(store.isEmpty()) store.push(curItem);
            else{
                int peekItem = store.peek();
                if(peekItem == curItem){
                    answer += 2;
                    store.pop();
                }else{
                    store.push(curItem);
                }
            }
        }

        return answer;
    }
}

Client가 만드는 페이지! Server가 만들어서 던져주는 페이지! 라고 단순하게 이해하고있었는데, 이러한 수준의 이해는 아느니만 못하다는 생각에 한번 공부해보았습니다.

함께 보시죠!

(기존 CSR, SSR에 대한 개념이 확실하신 분은 3번으로 넘어가도 좋습니다.)

1. 개념 정리

CSR(Client Side Rendering)

단어에서 의미하는 그대로 Client Side에서 Rendering 맡는 것을 의미합니다.

그림으로 쉽게 이해해보자면

1. 사용자의 요청이 들어옵니다.

2. 프론트서버로부터 HTML을 다운받습니다. (진입점 Html ex. vue - index.html)

   → 여기서 중요한 점은 HTML을 다운받았다고해서 Client가 창을 볼 수 없습니다. 빈 HTML을 다운받은 상태기 때문이죠!

3. 프론트 서버로부터 JavaScript를 다운받습니다.

4. JavaScript를 돌리며 처음 넘겨받은 HTML을 채웁니다.

   → 이때 프로젝트 내의 모든 HTML과 JS를 채웁니다.

5. 모든 데이터를 받았을때 최종적으로 사용자에게 창을 보여줍니다.

위에서 언급했다시피 중요한 점은 처음 넘겨받은 HTML에는 내용이 없는 빈 HTML이라는 것과 모든 데이터가 연동이 됐을때 비로소 사용자에게 창이 보이기 시작한다는 점입니다.

SSR(Server Side Rendering)

Server Side에서 Rendering을 진행한 뒤 Client에게 던져주는 걸 의미합니다.

그림으로 쉽게 이해해보자면

1. 사용자의 요청이 들어옵니다.

2. 서버에서는 요청된 주소의 HTML을 사용자에게 넘겨줍니다. (정적 HTML Map.vue)

   → 여기서 HTML은 요청 주소의 HTML입니다. CSR의 초기 HTML과 다른점은 이 HTML은 /map 과 같이 요청된 주소에 해당하는 HTML이라는 점입니다.(내용이 있는 것이죠!)

   → 이미 내용이 들어있기 때문에 사용자는 창을 볼 수 있습니다. 다만, JavaScript를 아직 다운받지 못했기때문에 단순히 기능이 없는 창을 보게 됩니다.

3. 사용자는 서버로부터 JavaScript를 다운받습니다. (Map.vue를 수행할 수 있는 최소한의 JavaScript)

4. JavaScript를 돌리며 처음 넘겨받은 HTML의 동작을 추가합니다.

5. 모든 데이터를 받았을때 창이 동작합니다.

CSR과 다르게 SSR은 HTML을 다운받은 즉시 사용자에게 보여줄 수 있습니다. 빈 HTML이 아니기 때문이죠. 하지만 JavaScript를 다운받은 상태가 아니기때문에 정상적으로 동작하지 않습니다.

CSR은 처음에 전체 앱의 JavaScript를 한번 로드한 후, 사용자가 다른 페이지로 이동할 때 서버로부터 HTML 전체를 다시 받지 않고, 클라이언트 측에서 라우팅을 처리하여 필요한 데이터만 추가로 가져와 페이지를 보여주지만,

SSR은 각 페이지 요청마다 서버가 페이지를 새롭게 렌더링하고 그 결과를 HTML로 보내주기 때문에 매번 페이지가 바뀔 때마다 서버에 새로운 요청이 발생한다는 점입니다.

2. CSR, SSR 차이 정리

3. Vue 적용 설명

저는 CSR 기반 Vue를 사용해 본적이 있어 이 개념을 이용해서 CSR SSR을 정확하게 이해해보고 싶었습니다. 다음은 제가 이해한 내용을 바탕으로 CSR, SSR을 Vue의 관점에서 정리해본 결과입니다.

틀린 내용이 있을 수 있으니 지적, 충고, 정정요청 모두 대 환영입니다!

📂 src
 ├ 📂 components
 │ ├ Main.vue
 │ └ Map.vue
 ├ 📂 js
 │ ├ mapApi.js
 │ └ login.js
 └ index.html

• 사용자는 /map으로 요청을 보냅니다.
• /map은 Map.vue에서 처리되며 mapApi.js가 필요합니다.
• /map에 Main.vue, login.js는 사용되지 않습니다.

CSR

1. 사용자의 /map 요청 → 프론트 서버가 Index.html을 전송 (빈페이지)
2. 필요한 모든 JS 로딩 → Main.vue, Map.vue, mapApi.js, loginApi.js
3. 사용자 측에서 JavaScript가 실행되며 빈 html에 Map.vue 화면을 채웁니다
4. 이후 /main 에 대한 요청이 오면 다운받은 Main.vue와 loginApi.js를 사용해 렌더링합니다.

SSR

1. 사용자의 /map 요청 → 서버에서 렌더링한 Map.vue의 HTML을 내려줍니다.

   → 이때 사용자는 바로 map 페이지를 확인할 수 있습니다.

2. Map 페이지에 필요한 최소한의 JS를 로딩합니다. → mapApi.js, 그외 필요 js

3. JavaScript가 실행되며 기능을 연결합니다.

4. 이후 /main에 대한 요청이 오면 다시 Main.vue, loginApi.js를 내려받아 화면을 채웁니다.

4. SEO(Search Engine Optimization)

SSR과 CSR에 대해 구글링을 하다보면 항상 둘의 차이점에 SEO라는 부분이 있습니다.

저도 처음에 이 부분을 이해하기 어려워서 애를 좀 먹었는데 여기까지 읽으신 여러분이라면 이제 정확하게 이해가능합니다.

구글링을 하면 SEO에 대응하기 위해서는 SSR이 CSR보다 용이하다 라는 말을 쉽게 찾을 수 있습니다.

왜일까요?

그건 처음 초기 웹 페이지 로딩을 보면 알 수 있습니다.

초기렌더링때 CSR은 index.html을 보여주기때문에 빈페이지로 검색 엔진이 긁어올 데이터가 없습니다 🫢

반면, SSR은 초기 렌더링에서 내용이 꽉찬 HTML을 내려보내주기 때문에 검색엔진이 내용을 확인하고 결과로 보여줄 수 있는 것이죠.

구글이 최근 CSR 페이지도 어느 정도 렌더링하여 검색엔진을 최적화한다고 하는데 아직 SSR이 더 안정적이고 효율적이라고합니다!

아직 terminal로 깃을 다루는게 익숙하지 않다보니 sourceTree를 같이 사용하곤 했습니다.

이게 문제의 원인이 된거죠..

git으로 main에 ‘init’이라 commit하고 main에서 브랜치를 따오지 않고 다시 sourcetree로 ‘initial commit’이라는 새로운 커밋으로 시작한 것이 원흉이었습니다.(조상 커밋이 다른 2개의 히스토리) ㅠㅠ

1. 서로 다른 커밋(init, initial commit)에서 시작했기 때문에 history가 다른 2개로 시작되게 됩니다.
2. merge를 위해서는 공통의 조상이 필요한데 history가 다르기때문에 자동 merge가 불가능합니다

다음은 제가 해결 과정을 순서대로 정리한 결과입니다.

해결 방법

1. --allow-unrelated-histories

현재 2개의 history가 존재하는 것을 알 수 있습니다.

이 두개의 history를 합쳐줘야하기 때문에 --allow-unrelated-histories로 두개의 history를 합쳐줍니다.

git pull origin 브랜치명 --allow-unrelated-histories

• --allow-unrelated-histories: 이미 존재하는 두 프로젝트의 기록을 저장하는 드문 상황에 사용합니다.

2. Need to specify how to reconcile divergent branches

main으로 checkout한 뒤 origin master를 --allow-unrelated-histories조건으로 pull 받으려 했지만

Need to specify how to reconcile divergent branches라는 오류가 났습니다.

이 오류는 branch를 새로 생성해서 작업하면서 생긴 오류로 새로운 branch가 추가됐다면 pull 전에 어떤 병합 전략을 사용할지 선택해 달라는 말입니다.

• git pull은 원격 저장소에서 로컬 저장소로 파일을 가져와 자동으로 병합을 실행합니다.
• git fetch는 원격저장소의 내용을 가져오지만 로컬 데이터와 병합하지는 않습니다.
  

즉, pull은 fetch + merge로 pull을 하면서 자동 merge를 시도하지만 fast-forward에 적합하지 않기때문에 오류가 발생했던거죠.

fast-forward란? fast-forward는 Git에서 합칠 때, 별도의 추가 커밋 없이 커밋 히스토리를 그냥 앞으로 전진시키는 것을 말합니다. → 원격에만 새로운 커밋 존재, 로컬엔 X인 경우

master와 main을 합쳐야 했기에 checkout main에서 git pull origin master —rebase를 진행했습니다.

이렇게 연결이 됐고, 이제 local main과 origin main을 합치고 싶어 git pull origin main을 했더니 정방향이 불가능하므로, 중지합니다.라는 오류가 발생했습니다.

3. 정방향이 불가능하므로, 중지합니다.

원인은 공통의 조상이 없는 상태에서 merge를 진행하려 했기 때문입니다.

공통 조상이 없을 경우 자동 merge가 불가능하고 merge 전략을 제시해줘야합니다

git merge master --allow-unrelated-histories 로 merge의 충돌을 잡아줬고, merge 결과를 푸쉬하면서 문제를 해결할 수 있었습니다.

정리

다른 커밋으로 시작하게 될 경우 별도의 history로 시작하게 됩니다. 이것은 다른 조상으로 시작한다는 말이기 때문에 자동 merge가 될 수 없는 환경인거죠!

merge 전략을 세우고 별도 작업(--allow~~)들로 해결할 수는 있지만 꽤나 귀찮은 상황입니다.

작업전 pull을 확실하게! 하는걸 생활화합시다!

문제설명

• 파라미터: int n, int w, int num
• 반환값: int
• 교차로 쌓아가는 택배에서 자신의 번호를 꺼낼때 자신 포함 몇개의 상자를 꺼내야하는지 return

풀이방식

1. 본인이 몇번째 줄, 몇번째 위치인지 알아야한다. + 마지막 상자가 몇번째 줄, 몇번째 위치인지 알아야한다.

2. 만약 상자가 w로 나누었을때 나머지가 0이라면 위치를 조정시킬 필요가 있다.

   → col == 0 → row— , col = w

3. 자신의 위로 몇줄이 있는지 알아야한다.

4. 마지막 줄에 자신의 col이 존재하는지 알아야한다.

코드

class Solution {
    public int solution(int n, int w, int num) {
        int answer = 0;
        int row = num / w + 1 ;
        int col = num % w;
        if(col == 0){
            row--;
            col = w;
        }
        int limitRow = n / w + 1;
        int limitCol = n % w;
        if(limitCol == 0){
            limitRow--;
            limitCol = w;
        }
        boolean even = true; 
        // 진행방향 확인 
        int curDir = 0; // 0 우 1 좌 
        int numDir = 0;

        if(row % 2 == 0) curDir = 1;
        if(limitRow % 2 == 0) numDir = 1;

        System.out.println(col + " " + limitCol);

        if(curDir == numDir){
            answer = limitRow - row + 1;
            System.out.println(col + " " + limitCol);
            if(col > limitCol) answer--;

        }else{
            answer = limitRow - row + 1;
            col = w - col + 1;
            if(col > limitCol) answer--;
        }

        return answer;
    }
}
```![](https://velog.velcdn.com/images/illli_705/post/60aa00b4-cdc4-4566-b463-cc6de2a83812/image.png)

1. 개념

힙 정렬은 말 그대로 힙을 사용하는 정렬 방식을 말합니다. 여기서 힙은 트리(tree)에 기반한 자료구조로 우선 순위 큐의 효율적인 구성 방식 중 하나입니다.

힙 정렬은 힙 자료구조를 사용해 최댓값 혹은 최솟값을 순차적으로 뽑으며 정렬하는 방식을 말합니다.

2. 동작 과정

1. 주어진 배열로 힙 자료구조를 만듭니다. → $O(N)$
2. 만들어진 힙 자료구조에서 루트 노드를 삭제하고 맨 뒤로 옮깁니다.
3. 해당 과정을 힙 자료구조가 빌때까지 반복합니다.

→ 최종적으로 정렬된 배열이 나옵니다.

3. 힙 정렬의 시간 복잡도

힙 정렬은 입력 배열을 힙 자료구조(완전 이진 트리)를 이용해 정렬하는 알고리즘입니다. 배열 자체를 힙 구조로 재구성한 후, 루트 노드를 반복적으로 삭제하며 정렬을 진행합니다.

힙을 구성하는데 배열의 모든 원소를 한 번씩 방문하여 제자리에서 힙의 속성을 만족하도록 재구성하기 때문에 보통 O(N)의 시간 복잡도를 가집니다.

또, 힙 자료구조가 완성된 상태에서 루트 노드를 삭제하고 다시 힙 자료구조를 재구성하는데 약 $O(logN)$ 만큼의 시간복잡도를 가집니다. 이런 작업을 모든 원소에 대해서 진행하기때문에 O(N)번 반복하게 됩니다.

이를 정리해보면 아래와 같습니다.

• 힙 구성: $O(N)$
• 루트 삭제 & 힙 재구성: $O(logN)$
• 삭제 & 힙 재구성 횟수: $O(N)$
• 시간 복잡도: $O(N) + O(NlogN)$ → $O(NlogN)$
• 공간복잡도: $O(1)$ → 배열 자체로 힙 자료구조를 만들기 때문
• 안정성: X

병합 정렬

1. 개념

병합 정렬은 말 그대로 여러개였던 배열을 하나로 합치며 정렬하는 방식입니다.

기존에 정렬된 배열을 병합해 정렬된 배열의 완성본을 만드는 방식은 굉장히 쉽습니다. 병합 정렬에서는 이 방식을 그대로 사용합니다. 정렬을 하기 위해서는 기존의 배열을 여러개의 요소로 나눠야합니다. 하지만, 정렬되지 않은 배열을 어떻게 정렬된 여러개의 정렬된 배열로 나눌까요?

그 방법은 웃기게도 모두 1개의 요소로 이루어진 배열로 나누는 것입니다. 요소가 하나뿐이면 정렬이 된 상태로 볼 수 있기 때문이죠.

이후 나눠진 요소들을 정렬의 원칙을 지키며 하나씩 합치며 정렬하는 방식을 병합 정렬이라고 합니다.

2. 동작 과정

1. 주어진 배열을 정확하게 반씩 나눕니다.
2. 7,2,5,1,3,7,4,8,6 이렇게 총 8개의 배열이 남게 됩니다.
3. 나눈 방향의 역순으로 정렬된 상태로 배열을 합쳐나갑니다.

→ 최종적으로 정렬된 배열이 나옵니다.

3. 병합 정렬의 시간 복잡도

힙 정렬은 입력 배열을 힙 자료구조(완전이진트리)를 이용해 정렬하는 방식으로 배열 자체를 힙 구조로 정렬한 후 루트 노드를 반복적으로 삭제하며 정렬을 진행합니다.

힙 자료구조를 구성하는 것은 배열의 모든 원소를 한번씩 방문하여 제자리에서 힙의 속성을 만족하도록 재구성하는 것이기 때문에 $O(N)$의 시간복잡도가 필요하고

루트 노드를 삭제하며 남은 원소로 다시 힙을 구성하는 작업에서 힙의 높이만큼 시간이 소요되기 때문에 $O(logN)$이 소요되기 때문에 최종적으로 정렬을 위해서 $O(NlogN)$의 시간복잡도가 소요됩니다.

이를 정리해보면 아래와 같습니다.

• 힙 구성: $O(N)$
• 삭제 연산 & 힙 재구성: $O(logN)$
• 삭제 연산 횟수: $O(N)$
• 시간 복잡도: $O(N)$ + $O(NlogN)$ → $O(NlogN)$
• 공간복잡도: $O(N)$ → N개의 배열을 만들기 때문
• 안정성: O

1. 개념

Quick 정렬은 말 그대로 가장 빠른 정렬 방식입니다. 정렬을 하기 위해서는 모든 요소를 들여다봐야합니다(O(N)) 하지만 퀵 정렬 방식을 이용하면 $O(N logN)$ 의 시간복잡도로 정렬이 가능합니다. 흥미롭죠? 한번 살펴보시죠

퀵 정렬은 어떤 값을 기준으로 목록을 하위 목록으로 나눈 뒤 재귀를 반복하는 방식입니다. 하위 목록으로 계속해서 나누기때문에 $N logN$ 이 나오는 것이죠.

재귀의 과정은 말로 설명하기 어려우니 그림으로 살펴보겠습니다.

2. 동작 과정

1회 순회 목표: 가장 오른쪽 값을 기준으로 기준값보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치

1. 가장 왼쪽값-1(left)과 가장 오른쪽 값(right)을 기준으로 설정
2. left+1 요소부터 살펴보기 시작
   • 해당 요소가 기준값(right)보다 크면 그대로 유지
   • 해당 요소가 기준값(right)보다 작으면 left+1과 left 요소를 바꾸고 left 인덱스를 1 증가
3. 해당 과정을 right까지 계속해서 반복
4. 최종적으로 left 요소의 값과 right 요소의 값을 변경하면 순회 목표와 유사한 정렬이 완성

→ 해당 순회를 통해 기준 값의 위치는 선정이 되지만, 나머지 왼쪽과 오른쪽 값들은 정렬이 진행되지 않은 상태입니다.

그렇기 때문에 왼쪽과 오른쪽 각각 범위에 대해서도 위의 과정을 재귀로 넘겨주어 최종적으로 확정되는 요소들만 남게 됩니다.

3. 퀵 정렬의 시간 복잡도

퀵 정렬은 각 계층마다 N → 일정 부분 나뉜값 → 일정 부분 나뉜값을 방문하게 됩니다. 이를 쉽게 생각해 $O(N)$의 요소를 방문한다고 생각하겠습니다.

퀵 정렬은 재귀를 통해 반복되기때문에 재귀의 횟수가 시간 복잡도에 영향을 주게 됩니다. 평균적으로는 $\frac{1}{2}$씩 줄어든다고 가정하여 $O(longN)$으로 생각 할 수 있지만, 최악의 경우 1과 N-2 개씩 남게되는 상황이 있을 수 있기 때문에 $O(N)$까지 증가할 수 있습니다.

또, 재귀 함수를 활용하기 때문에 스택 메모리를 사용하게 되고 그 사용량은 $O(logN)$입니다.

이를 정리해보면 아래와 같습니다.

• 총 반복 횟수(재귀)

  • 매단계 좌우 균등 시: $O(longN)$
  • 매 단계 한쪽으로 몰릴 시: $O(N)$

• 각 계층마다 반복하는 요소 수: $O(N)$

• 시간 복잡도: 평균: $O(NlogN)$, 최악: $O(N^2)$

• 공간복잡도: $O(logN)$

• 안정성: ❌

구현

void quickSort(int[] arr, int left, int right) {
        if(left >= right) return;

        int pivotPos = partition(arr, left, right);

        quickSort(arr, left, pivotPos - 1);
        quickSort(arr, pivotPos + 1, right);
    }

    private int partition(int[] arr, int left, int right) {
        int pivot = arr[right];

        int i = left - 1;
        for(int j = left; j < right; j++){
            if(arr[j] < pivot){
                i++;
                swap(arr, i, j);
            }
        }

        int pivotPost = i + 1;
        swap(arr, pivotPost, right);

        return pivotPost;
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

‼️주의 재귀를 호출하는 과정(quickSort)과 재귀 내에서 정렬하는 과정(partition)을 나누어서 구현하였습니다.

퀵 정렬은 실무에서 가장 많이 사용하는 알고리즘입니다. 직접 구현하기는 어려울지라도 그 개념만큼은 확실하게 익히세효!

1. 개념

삽입 정렬은 말 그대로 Insertion(넣다) 해당하는 장소에 넣는 정렬입니다. 특정 범위 내에서 해당 요소가 들어갈 자리에 쏙! 넣는다 라고 생각하면 이해하기 쉽습니다.

삽입 정렬은 현재 위치의 요소를 뽑아 이전 방문했던 요소들 중 어디 사이에 넣어야 정렬이 유지되는지 판단하는 정렬 방식입니다.

매 순회마다 해당 요소를 이전 요소들 사이 어딘가에 넣게 되는데 이 경우 이후 요소들을 한자리씩 밀어내야하기때문에 구현하기가 꽤 까다롭습니다.

2. 동작 과정

int[] arr = new int[]{7,4,2,5,6};

1. 기준 인덱스(1)부터 이전 범위에서 해당 값이 들어갈 위치 찾기
2. 해당 위치로 요소 삽입
3. 기준 인덱스 위치 증가
4. 인덱스를 순차적으로 증가시키며 해당 과정 반복

→ 해당 과정을 1회 통과마다 살펴봐야하는 범위가 1씩 증가합니다.

3. 삽입 정렬의 시간 복잡도

삽입 정렬은 총 N-1회의 반복을 진행합니다. 순회를 하며 살펴보는 요소의 수는 N-1 → N-2 → ... 1 로 줄어들게 되는데 모든 항이 평균적으로 $\frac{N}{2}$ 만큼 살펴보게 됩니다. 또, 원본 배열을 가지고 정렬을 진행하기때문에 별도의 메모리 소요는 없기때문에 공간복잡도는 $O(1)$이 됩니다.

이를 정리해보면 아래와 같습니다.

• 총 반복 횟수: N-1
• 평균 살펴보는 요소 수: $\frac{N}{2}$
• 시간 복잡도: $O(\frac{N(N-1)}{2}) ⇒ O(N^2)$
• 공간복잡도: $O(1)$
• 안정성: O

구현

1. swap 방식 한꺼번에 요소를 밀기보다는 인접한 요소 비교하며 해당 위치 찾아가는 방식

void insertionSort(int[] arr) {
    int len = arr.length;

        for(int i = 1; i < len; i++){
            int target = arr[i];

            // swap을 통해 위치 이동
            for(int j = i-1; j >=0; j--){
                if(target < arr[j]){
                    arr[j+1] = arr[j];
                    arr[j] = target;
                    target = arr[j];
                }else{
                    break;
            }
        }
    }
}

2. shift 방식 위치를 찾은 뒤 한번에 요소 이동 후 삽입

void insertionSort(int[] arr) {
    int len = arr.length;
        for (int i = 1; i < len; i++) {
            int target = arr[i];
            int j = i - 1;

            // target보다 큰 원소들은 오른쪽으로 한 칸씩 이동
            while (j >= 0 && arr[j] > target) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 찾은 위치에 target 삽입
            arr[j + 1] = target;
        }
}