ZooKeeper의 개발 배경

개발 배경

• 분산 시스템에서는 클러스터간의 통신이나 데이터를 처리하는데 있어 고민

1. 분산된 시스템 같이 정보를 어떻게 공유할 것인가
2. 클러스터에 있는 서버들의 상태를 어떻게 체크할 것인가
3. 분산된 서버들 간의 동기화를 위해 잠금을 어떻게 처리할 것인가

• 이러한 분산 시스템을 처리해주고 관리의 필요성이 생겼다.

분산된 서버들끼리 통신할 때 리소스를 공유하려다 보면 자원 점유 문제가 발생하는데, 이를 처리하기 위한 대표적인 해결책으로 리소스 락을 볼 수 있다. 이 리소스는 Lock,Unlock하는데도 관리해주는 시스템이 필요하다.

코디네이션 서비스는 분산 시스템 내에서 중요한 상태 정보나 설정 정보 등을 유지하기 때문에 코디네이션 시스템의 장애는 전체 시스템 장애로 이어지는 장애 전파 특성이 있다.

따라서 고가용성을 제공하는 것이 필수이다.

ZooKeeper는 분산 시스템을 위한 중앙화된 설정, 네이밍, 동기화, 상태 관리를 지원하는 오픈소스 코디네이션 서비스

• 즉, 여러 서버들이 “누가 리더인지?”, “누가 살아있는지”, “설정을 공유할지?”를 조율해주는 분산 시스템 관리자 역할을 한다.
• 어플리케이션의 정보를 중앙 집중화하고 구성관리, 그룹 관리 네이밍, 동기화 등의 서비스를 제공한다. 주키퍼의 데이터는 메모리에 저장되고, 영구 저장소에 스냅샷을 저장한다.

분산 코디네이션 서비스

분산 시스템에서 시스템 간의 정보 공유, 상태 체크, 서버들 간의 동기화를 위한 락 등을 처리해주는 서비스

⇒ 그림에서 Server는 주키퍼, Client는 카프카

구성

1. Request Processor : Write 요청 처리

1. Zab (Zookeeper Atomic Broadcast Protocol) : Request Processor에서 처리한 요청을 트랜잭션을 생성하여 모든 서버에게 전파한다. [Leader-Propose] -> [Follower-Accept] -> [Leader-Commit] 단계로 구성
2. In-memory DB: Znode 정보 저장, 로컬 fs에 Replication을 구성

주키퍼 역시 분산 시스템의 일부분이기 때문에 동작을 멈춘다면 분산 시스템이 멈출수도 있다. 그래서 안정성을 확보하기 위해 클러스터(Cluster)로 구축한다.

• 클러스터는 홀수로 구축

  • 어떤 서버에 문제가 생겼을 경우 과반수 이상의 데이터를 기준으로 일관성을 맞추기 때문
  • 살아남은 노드가 과반수 이상이라면 지속적인 서비스를 제공

• 서버 여러 대를 클러스터로 구축하고, 분산 어플리케이션들의 각각 클라이언트가 되어 주키퍼 서버들과 커넥션을 맺은 후 상태 정보 등을 주고 받음.

  • 상태 정보들은 주키퍼에 Znode 라고 불리는 곳에 Key - Value 형태로 저장
  • 저장된 형태로 분산 어플리케이션들은 서로 데이터를 주고받음

  ---

Znode란?

주키퍼의 인터페이스

주키퍼가 상태 정보를 저장하는곳

→ 파일 시스템과 유사하게 노드간 계층구조(트리구조)를 가지며 각 노드를 ‘/’로 구분하나 file과 directory 구분이 없음

• 모든 znode는 메모리에 저장됨.빠른 접근을 위해 메모리에 올려둠)
  • 따라서 jvm의 모든 heap memory를 모든 znode를 올릴 수 있는 충분한 크기로 만들어야함
• 목적은 데이터 저장이 아니라 분산 처리되는 시스템 간의 조정. 하는 역할 자체가 read와 write 밖에 없다.
  • 따라서 1 Znode당 데이터 크기 제한 있음.
• znode는 디렉토리와 파일의 구분이 없기 때문에, 경로를 가지면서 데이터를 가질 수 있다.
• 분류
  • Persistent Node: 영구 저장소
  • Ephermeral Node: Client가 종료되면 사라짐
  • Sequence Node: 생성 시 뒤에 숫자가 붙음

Quorum

Leader가 새로운 트랜잭션을 수행하기 위해서는 자신을 포함하여 과반수 이상의 서버의 합의를 얻어야하는데, 과반수 합의를 위해 필요한 서버들

Ensemble을 구성하는 서버의 수가 5개라면, Quorum은 3개의 서버로 구성이 된다.

왜 쿼럼은 과반수로 이루어져야 하느냐?

첫번째, 리더 선출

• 각 서버는 자신의 현재 zxid(트랜잭션 ID)와 자신을 후보자로 지명해 모든 서버로 전송 (zxid가 높은 놈일수록 더 많은 데이터가 있는것)
• 각 서버는 zxid를 받은 뒤, 자신의 zxid와 비교해 더 높은 쪽을 후보자로 지명해 모든 서버에 전송
• 과반수 이상의 서버로부터 지명된 서버가 leader로 선출

두번째, 데이터의 일관성

• 데이터가 죽었을때, 반드시 과반수 이상의 데이터를 가져와서 브로드캐스팅을 진행

과반수 이상의 데이터가 죽어버리면, 주키퍼는 동작을 멈춘다! 더이상 데이터를 쓸수가 없다.

• Leader에게 Request 전달 새로운 트랜잭션 요청이 Follower에게 도착하였을 경우, Follower는 Leader에게 요청을 전달한다.

• Propose Propose는 Leader가 Quorum을 구성하는 서버들에게 트랙잭션을 수행해도 되는지 여부를 요청하는 과정을 의미한다.

• Ack Quorum을 구성하는 서버들은 Leader로 부터 Propose 요청을 받으면, 트랙잭션을 수행해도 된다는 Ack 응답을 Leader에게 전송한다.

• Commit 모든 Quorum으로 부터 Ack를 받으면, Leader는 트랙잭션을 처리하라는 Commit 명령을 broadcast 형태로 모든 Follower에 전파한다. ZooKeeper에서는 Commit 명령을 전달할 때, ZAB(ZooKeeper Atomic Broadcast) 알고리즘을 사용한다. Atomic Broadcast는 broacast 방식 중 하나로, 멀티 프로세스 시스템에서 모든 프로세스에게 동일한 순서로 메시지가 전달된다는 것을 의미한다.

• Watcher

  ZooKeeper는 znode에 변화를 감지할 수 있는 Watcher를 클라이언트가 설정할 수 있도록 한다. Watcher는 자신이 감시하고 있는 znode에 수정이 발생하였을 때, 클라이언트로 callback 호출을 전송하는 알림 기능을 제공한다.

  주키퍼를 사용하는 클라이언트 A가 ZooKeeper에게 Watcher 등록을 요청한다. 주키퍼를 사용하는 클라이언트 B가 ZooKeeper에게 Znode를 수정한다고 말한다. 클라이언트 A에게 변경 이벤트를 전달한다.

Zookeeper의 목적과 Kafka와의 관계

주키퍼의 목적

Zookeeper는 DB처럼 데이터 저장하려는 목적이 아니다.

진짜 목적은 분산 시스템끼리 서로 "상태를 동기화"하고 "조정"하는 것.

• 누가 리더(Leader)가 될지 선출하기 (Leader Election)
• 분산 락(Distributed Lock) 걸기
• 설정 파일(Configuration)을 중앙 집중화해서 관리
• 서버들이 클러스터에 살아 있는지 확인(Heartbeat)

즉, Zookeeper는 다음 같은 걸 해주는 조정자(Coordinator) 역할.

• 서버 A, B, C가 있다고 할 때
• A, B, C가 서로 직접 통신하지 않고
• Zookeeper의 Znode를 통해 간접적으로 상태 공유함

Kafka와의 관계

• 주키퍼는 별도의 독립된 서버(클러스터)로 운영하는 경우가 많음
• 카프카는 일시적으로 브로커 하나가 죽어도 클러스터 전체가 바로 멈추진 않음
  • 살아있는 브로커들이 계속 서비스 유지 가능
• 그러나 주키퍼는 다름
  • 주키퍼는 다수결(Quorum) 구조 사용함
  • 노드 과반수 이상 살아있어야 정상 동작 가능
  • 과반수 무너지면 주키퍼 전체가 동작 중단함 (읽기/쓰기 모두 불가)
• 만약 주키퍼가 동작 멈추면?
  • 카프카 브로커는 당장은 정상적으로 메시지 생산/소비할 수 있음 (이미 리더 선출된 상태에서는 주키퍼 필요 없음)
  • 그러나 이후에
    • 새로운 브로커가 클러스터에 합류하려 하거나
    • 리더 브로커가 죽어서 리더 재선출해야 할 때
    • 파티션 리더 변경 같은 메타데이터 변경 작업이 필요할 때
  • 카프카가 주키퍼에게 요청해야 하는 상황이 생김

주키퍼는 "중앙 심판" 역할. 카프카는 "선수들". 평소에는 선수들끼리 알아서 경기함. 심판이 없어도 당장은 진행됨. 근데 문제가 생기거나 판정이 필요한 순간 → 심판 없으면 경기 진행 불가.

• 이때 주키퍼가 죽어있으면 카프카가 요청을 처리 못 함 → 결국 카프카 클러스터 장애로 연결될 수 있음

1. 오픈소스란?

• 오픈소스(Open Source)는 소스 코드가 공개되어 누구나 자유롭게 열람, 수정, 배포할 수 있는 소프트웨어 또는 그 개발 방식을 말한다.
• 소프트웨어뿐 아니라, 오픈소스는 하드웨어 설계, 데이터, 알고리즘, 문서 등에도 적용될 수 있다.

2. 오픈소스 소프트웨어란?

• 오픈소스 소프트웨어(Open Source Software, OSS)는 소스코드를 자유롭게 사용할 수 있도록 라이선스를 통해 배포되는 소프트웨어.
• 누구나 기능을 추가하거나 오류를 수정하여 개선하거나 사용자 환경에 맞게 커스터마이징할 수 있다.
• 대부분 커뮤니티 기반으로 협업 개발되며, 투명성과 신뢰성이 높음.
• 예시:
  • 운영체제: Linux
  • 웹 서버: Apache, Nginx
  • 브라우저: Mozilla Firefox
  • 데이터베이스: MySQL, PostgreSQL
  • 버전관리 시스템: Git

3. 오픈소스 소프트웨어의 특징

4. 오픈소스의 장점

• 비용 절감: 무료로 사용할 수 있는 경우가 많음
• 높은 확장성: 직접 기능을 추가하거나 수정 가능
• 빠른 버그 수정: 다수의 개발자들이 빠르게 문제를 발견하고 수정함
• 기술 공유 및 학습: 실제 동작하는 코드에서 학습 가능

5. 오픈소스의 단점

• 전문적인 기술 필요: 수정이나 커스터마이징 시 고급 기술 필요
• 책임 불명확: 문제가 발생했을 때 공식 지원이 제한적일 수 있음
• 보안 리스크: 잘못된 사용이나 미검증 라이브러리는 보안 취약점이 될 수 있음

Kafka란?

Apache Kafka의 개념

분산 스트리밍 플랫폼으로, 대량의 데이터를 빠르고 안정적으로 전달하고 처리할 수 있는 메세지 큐 시스템.

→ “데이터를 잘게 쪼개서 빠르게 보내고, 다른 곳에서 읽게 해주는 시스템”

Kafka가 필요한 이유

전통적인 시스템에서는 DB에 직접 저장하거나, REST API로 전달했지만 여러 문제점들이 발생한다.

• 대용량 실시간 데이터 처리 어려움
• 송 수신자가 직접 연결되어야 한다. (각 개체가 직접 연결하며 통신)
  • 전송속도가 빠르고 전송 결과를 신속하게 알수 있는 장점이 있다
    • 특정 개체에 장애가 발생한 경우 메세지를 보내는 쪽에서 대기 처리 등 개별적으로 해주지 않으면 장애가 전파될 수 있다.
    • 참여하는 개체가 많아질수록 각 개체를 연결해야함 (시스템이 커질수록 확장성이 떨어짐)
• 처리 순서/장애 복구 어려움
• 데이터 파이프라인 관리의 어려움
  • 각 애플리케이션과 데이터 시스템 간의 별도의 파이프라인이 존재하고, 파이프라인 마다 데이터 포맷과 처리 방식이 다르다
  • 새로운 파이프라인 확장이 어려워지면서, 확장성 및 유연성이 떨어진다
  • 데이터 불일치 가능성이 있어 신뢰도가 감소한다

모든 시스템으로 데이터를 전송할 수 있고, 실시간 처리도 가능하며, 급속도로 성장하는 서비스를 위해 확장이 용이한 시스템을 만들자!

⇒ 이렇게 모든 이벤트/데이터의 흐름을 중앙에서 관리하는 카프카가 탄생하게 되었다!

• 비동기 큐 기반으로 실시간 처리가 가능하다.
• 송 수신자 직접 연결 없이 Kafka가 중간에서 버퍼 역할을 수행한다.
• 파티션, 오프셋, 복제(replication) 구조로 극복이 가능하다.
• 모든 이벤트/데이터의 흐름을 중앙에서 관리할 수 있다.
• 새로운 서비스/시스템이 추가되도 카프가가 제공하는 표준 포맷으로 연결하면 되므로 확장성과 신뢰성이 증가한다.
• 개발자는 각 서비스간 연결이 아닌, 서비스들의 비즈니스 로직에 지중이 가능하다.

카프카의 동작 방식 및 특징

→ 카프카를 적용한 후 Linked-in 데이터 처리 시스템

카프카는 Pub - Sub 모델의 메세지 큐 형태로 동작한다.

⇒ 메세지 큐(Message Queue)란?

• 메세지 큐는 메세지 지향 미들웨어를 구현한 시스템으로 프로그램(프로세스) 간의 데이터를 교환할 때 사용하는 기술이다.

• producer: 정보를 제공하는 자
• consumer: 정보를 제공받아서 사용하려는 자
• Queue: producer의 데이터를 임시 저장 및 consumer에 제공하는 곳

주목해야할 부분이 바로 Queue 인데, MQ에서 메세지는 End-to-End 간에 직접적으로 통신하지 않고, 중간에 Queue를 통해 중개된다는 점이다.

MQ 장점

• 비동기: queue라는 임시 저장소가 있기 때문에 나중에 처리 가능
• 낮은 결합도: 애플리케이션과 분리
• 확장성: producer or consumer 서비스를 원하는대로 확장할 수 있다
• 탄력성: consumer 서비스가 다운되더라도 애플리케이션이 중단되지않고 메세지는 지속하여 MQ에 남아있다.
• 보장성: MQ에 들어간다면 결국 모든 메세지가 consumer 서비스에게 전달된다는 보장을 제공한다.

메세지 브로커 / 이벤트 브로커

• 메세지 브로커
  • publisher가 생산한 메세지를 메세지 큐에 저장하고, 저장된 데이터를 consumer가 가져갈 수 있도록 중간 다리를 해주는 브로커(broker)라고 볼 수 있다. 보통 서로 다른 시스템 (혹은 소프트웨어) 사이에서 데이터를 비동기 형태로 처리하기 위해 사용한다. (대규모 엔터프라이즈 환경의 미들웨어로서의 기능)
  • 이 구조를 pub/sub 구조라고 하며 대표적으로는 Redis, RabbitMQ 소프트웨어가 있고, GCP의 pubsub, AWS의 SQS같은 서비스가 있다. 이와 같은 메세지 브로커들은 consumer가 큐에서 데이터를 가져가게 되면 즉시 혹은 짧은 시간 내에 큐에서 데이터가 삭제되는 특징들이 있다.
• 이벤트 브로커
  • 이벤트 브로커 또한 기본적으로 메세지 브로커의 큐 기능들을 가지고 있어 메세지 브로커의 역할도 수행한다.
  • 큰 차이점은 publisher가 생산한 이벤트를 이벤트 처리 후에 바로 삭제하지 않고 저장하여, 이벤트 시점이 저장되어 있어서 consumer가 특정 시점부터 이벤트를 다시 consume 할 수 있는 장점이 있다. (ex. 장애가 일어난 시점부터 그 이후의 이벤트를 다시 처리할 수 있음)
  • 대용량 처리에 있어 메세지 브로커보다는 더 많은 양의 데이터를 처리할 수 있는 능력이 있다. 이벤트 브로커에는 Kafka, AWS의 kinesis 같은 서비스가 있다.

Pub/Sub 모델

• 비동기 메세지 전송 방식. 발신자의 메세지에는 수신자가 정해져 있지 않은 상태로 publish 한다.
• 이를 구독한 Subscribe을 한 수신자만 정해진 메세지(Topic)을 받을 수 있다.
• Publisher 와 Subscriber는 오로지 Topic 정보만 알 뿐, 서로에 대해 알지 못한다. → 서로의 결합도가 낮다.
• 수신자는 발신자가 없어도 원하는 메세지만 수신할 수 있으며, 이런 구조 덕분에 높은 확장성을 확보할 수 있다.

• LinkedIn에서 개발된 pub-sub 모델의 메시지큐 방식 기반, 분산 메세징 시스템이다.
  • Event: Kafka에서 producer와 consumer가 데이터를 주고받는 단위.
  • producer: kafka에 이벤트를 게시(post,pop)하는 클라이언트 어플리케이션
  • Consumer: Topic를 구독하고 이로부터 얻어낸 이벤트를 받아 처리하는 클라이언트 어플리케이션
  • Topic: 이벤트가 모이는곳. producer는 topic에 이벤트를 게시하고, consumer는 topic을 구독해 이로부터 이로부터 이벤트를 가져와 처리. 게시판 같은 개념.
  • Partition: Topic은 여러 Broker에 분산되어 저장되며, 이렇게 분산된 topic을 partition이라고 함
  • Zookeeper: 분산 메서지의 큐의 정보를 관리

동작 원리

1. publisher는 전달하고자 하는 메세지를 topic을 통해 카테고리화
2. subscriber는 원하는 topic을 구독함으로써 메세지를 읽음
3. publisher와 subscriber는 오로지 topic 정보만 알 뿐, 서로에 대해 알지 못한다.
4. kafka는 broker들이 하나의 클라스터로 구성되어 동작하도록 설계
5. 클러스터 내, broker에 대한 분산처리는 Zookeeper가 담당

특징

• Kafka Streams를 활용하여 동적라우팅을 구현
• 단순한 메세지 헤더를 지는 TCP 기반 custom 프로토콜을 사용 → 대체가 어려움
• 변경 불가능한 시퀸스 큐로, 한 파티션 내에서는 시간 순서를 보장함. 하지만 여러 파티션이 병렬로 처리할 때는 시간 순서 보장 못함
• 이벤트를 삭제하지 않고 디스크를 저장함으로 영속성이 보장되고, 재처리가 가능

장점

• 이벤트가 전달되어도 삭제하지 않고 디스크에 저장
• 고성능, 고가용성, 분산처리에 효과적
• producer 중심적 (많은 데이터를 병렬 처리)

단점

• 범용 메세징 시스템에서 제공되는 다양한 기능이 제공되지 않음.

Kafka vs RDB

카프카 구성요소

• 카프카는 저장소기 때문에 디스크를 많이 쓴다. 그렇기 때문에 주기적으로 데이터를 초기화하는 동작이 필요하다. → 카프카 토픽에 있는 데이터는 retension을 할수 있다.(retension: 보관 주기)
  • 보관 시기에 도달하면 그 데이터는 날라간다.
  • 이런 경우에는 Index Exception이 난다. 그래서 이 경우에는 Consumer에서 처리를 해줘야한다.
    • 그래서 Consumer는 이런 경우를 대비해 처리 로직이 필요함
      • 에러 발생 시
        • 가장 최신 오프셋(=latest)으로 이동하거나
        • 가장 처음 오프셋(=earliest)으로 재설정해야 함
    • 보통 Consumer 설정(auto.offset.reset)으로 처리 방향을 지정함
      • latest → 제일 최신 데이터부터 읽음
      • earliest → 가능한 가장 오래된 데이터부터 다시 읽음

Topic

• 각각의 메시지를 목적에 맞게 구분
• 메세지를 전송하거나 소비할때 Topic을 반드시 입력
• Consumer는 자신이 담당하는 Topic의 메시지를 처리
• 한개의 토픽은 한 개 이상의 파티션으로 구성

partition

• 분산 처리를 위해 사용
• Topic 생성시 Partition의 개수를 지정할 수 있음
• 파티션이 1개라면 모든 메세지의 순서가 보장
• 파티션 내부에서 각 메시지는 offset(고유번호)로 구분
• 파티션이 여러개라면 Kafka 클러스터가 라운드 로빈 방식으로 분배해서 분산처리되기 때문에 순서가 보장되지 않음
• 파티션이 많을수록 처리량이 좋지만 장애 복구 시간이 늘어남

Offset

• Consumer에서 메시지를 어디까지 읽었는지 저장하는 값
• Consumer Group의 Consumer 들은 각각의 파티션에 자신이 가져간 메시지의 위치정보를 기록
• Consumer 장애 발생 후 다시 살아나도, 전에 마지막으로 읽었던 위치에서부터 다시 읽어들일 수 있음
• 자바에 변수 선언 → 메모리 할당됨 → 변수를 free처리하면 메모리는 날라감.
• 카프카의 Consumer 오프셋 최댓값은 2의 63승 -1. 이 상한값은 실제 한계를 훨씬 뛰어넘는 값이다.

Producer

• 메시지를 만들어서 카프카 클러스터에 전송
• 메시지 전송 시 Batch 처리가 가능
• key값을 지정하여 특정 파티션으로만 전송이 가능
• 전송 acks 값을 설정하여 효율성을 높일 수 있다.
• ACKS=0 -> 매우 빠르게 전송. 파티션 리더가 받았는지 알 수 없다.
• ACKS=1 -> 파티션 리더가 받았는지 확인. 기본값
• ACKS=ALL -> 파티션 리더 뿐만 아니라 팔로워까지 메시지를 받았는 지 확인

Consumer

• 카프카 클러스터에서 메세지를 읽어서 처리
• 메세지를 Batch 처리할 수 있다
• 한 개의 Consumer는 여러 개의 토픽을 처리할 수 있다.
• Consumer는 Consumer 그룹에 속한다.
• 한개 파티션 같은 컨슈머 그룹의 여러개의 컨슈머에서 연결할 수 없다.

Broker

• 실행된 카프카 서버를 말한다.
• Producer와 Consumer는 별도의 애플리케이션으로 구성되는 반면, Broker는 카프카 자체이다.
• Broker(각 서버)는 Kafka Cluster 내부에 존재한다.
• 서버 내부에 메세지를 저장하고 관리하는 역할을 수행한다.

Zookeeper

• 분산 애플리케이션 관리를 위한 코디네이션 시스템
• 분산 메시지 큐의 메타 정보를 중앙에서 관리하는 역할

Broker(서버)의 부가설명

Kafka 브로커는 "하나의 서버"가 맞지만, 여러 브로커가 서로 "노드처럼 연결된 클러스터"를 이룬다.

• 브로커(Broker) = Kafka 서버 하나야. (예: 1번 서버, 2번 서버, 3번 서버)
• 클러스터(Cluster) = 여러 브로커가 모여서 하나의 덩어리처럼 동작하는 구조.

브로커끼리 네트워크로 연결되어 있어서, 서로 데이터를 주고받고 협력해. 그런데 1번 브로커 → 2번 브로커 → 3번 브로커로 "순서대로" 연결된 건 아님.

Kafka는 모든 브로커가 하나의 클러스터 안에서 서로 "평등하게" 연결되어 있다.

(예를 들어 1번 브로커가 2번 브로커에도 접근할 수 있고, 3번 브로커에도 직접 접근할 수 있는 형식)

그림으로 표현

• Kafka 브로커 하나가 Kafka 서버 하나를 담당한다

복사편집
[Broker1] ↔ [Broker2]
    ↕           ↕
[Broker3] ↔ [Broker4]

이런 식으로 모두가 서로 연결돼서, 필요한 데이터를 주고받고 있음.

• 클러스터 안에는 리더(Leader) 역할을 하는 브로커가 있고, 나머지는 팔로워(Follower) 가 돼서 리더를 따라간다.
• 어떤 토픽(Topic) 의 데이터(=파티션 데이터)는 특정 브로커가 "리더"로 맡고, 다른 브로커는 복제(Replication)를 해서 데이터를 같이 저장한다.

요약

• 브로커는 각각 서버 하나를 의미한다.
• 여러 브로커가 클러스터를 이룬다.
• 브로커 간에는 1-2-3 식 순차 연결이 아니라, 모두 연결된 네트워크처럼 통신한다.
• 특정 데이터(파티션)는 특정 브로커가 리더가 되고, 다른 브로커가 복제본을 가진다.

하나의 브로커 안에는 토픽이 여러 개 있을 수 있나?

• 하나의 브로커는 수십, 수백 개의 토픽을 가질 수 있다.
• 그리고 각 토픽은 다시 여러 개의 파티션으로 나뉘어져 있을 수 있다.
• 결국 브로커는 다양한 토픽의 다양한 파티션 데이터들을 "파일 시스템"에 저장하고 관리한다.
• 현업에서 브로커를 적게 두는 경우 → 비용적인 측면이 큼.

주요 설계 특징

왜 하나의 topic을 여러개의 partition으로 분산시키는가?

• 병렬로 처리하기 위해 분산 저장한다.
• 카프카의 토픽에 메세지가 쓰여지는 것도 어느정도 시간이 소비된다. 몇 천건의 메세지가 동시에 카프카에 write 되면 병목현상이 발생할 수 있다.
• 따라서 파티션을 여러개 두어서 분산 저장함으로써 write 동작을 병렬로 처리할 수 있다.
• 다만, 한번 늘린 파티션은 절대 줄일 수 없기 때문에 운영 중에, 파티션을 늘려야 하는건 충분히 검토 후에 실행되어야 한다.
• 즉, 최소한의 파티션으로 운영하고 사용량에 따라 늘리는 것을 권장한다.
• 파티션을 늘렸을때 메세지는 Round-Robin 방식으로 쓰여진다. 따라서 하나의 파티션내에서는 메세지 순서가 보장되지만, 파티션이 여러개일 경우는 순서가 보장되지 않는다.

잠깐! Round-Robin 방식이란?

• 여러 작업(프로세스)을 공평하게 돌아가면서 처리하는 방법이.
• 각 작업한테 시간 조각(time slice, time quantum)을 공평하게 나눠주고, 주어진 시간이 지나면 다음 작업으로 넘어간다.
• 이렇게 모두가 차례대로 기회를 얻는 구조.

라운드 로빈 vs 우선순위 스케줄링 차이점

• 라운드 로빈:

  👉 순서만 지킨다. 우선순위 상관없이 모두 차례로 실행한다.

• 우선순위(priority) 스케줄링:

  👉 높은 우선순위 프로세스를 먼저 실행한다.

  낮은 우선순위 프로세스는 높은 우선순위가 끝날 때까지 기다려야 한다.

(브로커가 죽는다)
↓
(Zookeeper가 감지)
↓
(Controller가 새 리더 고른다)
↓
(Zookeeper에 새 리더 정보 업데이트)
↓
(브로커/Consumer/Producer들이 새 리더를 따라간다)

Consumer Group은 왜 존재할까?

• consumer의 묶음을 consumer group이라고 한다.
• counsumer group은 하나의 topic에 대한 책임을 갖고있다.
• 즉, 어떤 consumer가 down 된다면, 파티션 재조정을 통해 다른 컨슈머가 해당 파티션의 sub을 맡아서 한다. offset 정보를 그룹간에 공유하고 있기 때문에 down 되기 전 마지막으로 읽었던 메세지 위치부터 시작한다.
• 브로커마다 각각의 파티션이 존재한다. 파티션의 개수가 컨슈머 보다 많이지는것은 가능하다. 파니션이 여러개, 컨슈머 그룹이 있는 컨슈머가 하나라고 가정해보자. 근데 컨슈머가 그 파티션에 있는 데이터를 다 읽어들일 수 있다. 하지만, 절대로 컨슈머의 갯수는 파티션의 갯수를 넘을 수 없다. 데이터의 중복성 때문에

Kafka는 그럼 어떨때 쓰는거야?

Kafka는 "데이터를 빠르게, 실시간으로, 많이 보내야 할 때" 사용한다.

특히, 여러 시스템이 데이터를 주고받거나, 처리하거나, 저장하는 과정이 분리되어 있어야 할 때 적용된다!

🛠️ Kafka가 적용될때

🧩 예시 시나리오 ①: 쇼핑몰 주문 처리

🧾 순서

1. 사용자가 상품을 주문 → order-created라는 Kafka 토픽에 메시지 생성
2. 결제 서비스가 해당 메시지를 구독하여 결제 처리
3. 배송 시스템은 order-paid 토픽을 구독해서 배송 시작
4. 분석 시스템은 order-completed 토픽을 통해 통계 적재

plaintext
복사편집
[주문 페이지]
   ↓ Kafka (order-created)
[결제 시스템]
   ↓ Kafka (order-paid)
[배송 시스템]
   ↓ Kafka (order-delivered)
[데이터 분석]

→ 각 시스템이 독립적으로 메시지를 받아 자기 할 일만 수행함 (비동기 처리).

🧩 예시 시나리오 ②: 로그 수집 시스템

plaintext
복사편집
[사용자 웹/앱 로그]
     ↓
 Kafka (user-log 토픽)
     ↓
[ElasticSearch] ← 검색
[Hadoop]        ← 배치 분석
[실시간 대시보드] ← 시각화

• Kafka는 로그 수집기이자 중앙 허브 역할
• 로그가 일단 Kafka에 들어오면 여러 분석 시스템이 동시에 읽어서 활용

📌 Kafka 도입을 고려하는 시그널

🛑 Kafka를 굳이 쓰지 않아도 되는 경우

🔚 정리

Kafka는 “데이터를 여러 곳으로, 실시간으로, 안정적으로 전달해야 할 때”

→ "데이터의 허브" 역할을 한다!

저는 최근에 React와 Spring Boot(localhost:3000 & localhost:8080)를 이용해 동해선 광역전철을 홍보를 위한 정보를 제공하는 웹 프로젝트를 완성했습니다. 그러나 문득 혼자서 프론트엔드 배포와 백엔드 배포를 해본 경험이 없기에 문득 이번 프로젝트를 실제 서비스를 구축하여 로컬 ➡️ 배포의 흐름 과정을 이해하는 과정을 통해 개발자로써 한 단계 더 성장하고 싶어 이번 글을 남기게 되었습니다. 저는 우선 클라우드가 무엇이고 어떻게 등장하게 되었는지 역사적인 Flow를 통해 정리하고 가는것이 모든 배포과정의 일련의 과정이자 기반이라고 생각되어 이번 새로운 시리즈의 첫 포스팅은 Cloud가 나타내게 된 역사적 배경에 대해 알아보는 시간을 가져보겠습니다!

✅ History Flow - For Cloud Service

🔹 1. 과거: 물리적 서버 & 저장 매체의 한계 → 가상화(Virtualization) 기술의 등장

USB, CD 같은 과거의 디지털 저장 매체는 급속도로 증가하는 데이터에 비해 용량이 턱없이 부족했습니다. 2000년대를 거쳐, 수많은 사용자들의 요청이 들어오면 감당하기 벅찬 트래픽과 주문량으로 서버는 감당하기 점점 힘들어졌습니다.

🔹 2. 가상화(Virtualization) 기술의 등장

그렇지만 가상화 등장함으로써 어느정도 서버가 감당할수 있게 되었습니다.

💡 가상화(Virtualization)란?
실제로 존재하지 않지만 가상의 컴퓨팅 환경을 만들어 여러 운영체제나 소프트웨어를 시뮬레이션 할 수 있는 기술

가상화 등장전에는 하나의 컴퓨터(하드웨어)에 하나의 운영체제, 하나의 애플리케이션을 쌓아서 운영할 수 있었다면, 가상화 등장 이후에는 하나의 하드웨어에 가상머신을 두어 여러개의 운영체제나 애플리케이션을 둘 수 있게 되었습니다! 그러나 역시 시대의 발전이 워낙 빨라, 가상화기술도 점점 한계를 보이기 시작했습니다. 운영체제 마다 별도의 자원을 차지하기 때문에 성능적으로 부담이 증가하고, 운영체제 부팅 및 시간이 오래걸리기 때문에 빠른 배포가 어려웠습니다.

🔹 3. 컨테이너(Container) 기술의 발전

가상화의 한계에 떠오른것이 바로 컨테이너(Container) 기술의 등장입니다. 컨테이너 기술은 기존의 가상화보다 빠르게 애플리케이션을 실행하도록 도와주었습니다. 대표적인 컨테이너 기술로는 Docker(도커)가 있습니다! 컨테이너 기술은 가상화 보다 가벼운 환경이기 때문에 운영체제를 따로 포함하지 않습니다. 또한 컨테이너 이미지를 사용하여 즉시 실행이 가능하고, 개발환경과 배포환경의 운영이 동일하게 유지되므로 일관성이 유지됩니다. 컨테이너 기술이 발전하면서 클라우드 컴퓨팅(Cloud Computing) 개념이 등장하게 됩니다.

💡 컨테이너(Container)란?
운영체제(OS) 수준에서 격리된 가벼운 환경을 제공하여, 애플리케이션과 필요한 라이브러리, 설정 등을 한 번에 패키징하여 실행할 수 있도록 하는 기술

🔹 4. 클라우드 컴퓨팅의 등장

과거에는 기업이나 개발자가 직접 서버를 구매하고, 설치하고, 유지보수를 했습니다. 그렇지만 클라우드 컴퓨팅이 등장하면서 필요한 만큼의 서버의 저장공간을 인터넷에서 빌려쓰는 방식으로 변화하였습니다!

💡 클라우드 컴퓨팅(Cloud Computing)이란?
인터넷을 통해 가상 서버, 데이터베이스, 네트워크, 소프트웨어 등을 제공하는 서비스

✅ 클라우드의 장점

• 필요한 만큼 사용 & 비용 절감 (사용한 만큼만 요금 지불) ⇒ OnDemand(온디멘드, 수요에 반응한다)
• 확장성(Scalability) → 트래픽 증가 시 자동으로 리소스를 확장 가능
• 서버 유지보수 부담 감소 → 보안 패치, 업그레이드를 클라우드 제공업체가 담당

✅ 클라우드 컴퓨팅의 유형

*💡 대표적인 클라우드 서비스 제공 업체 *

• AWS (Amazon Web Services)
• GCP (Google Cloud Platform)
• Azure (Microsoft Azure)

💡 인프라 ⇒ IaaS (network + storage + computing)

• 인프라만 제공
• OS를 직접 설치하고 필요한 소프트웨어를 개발해서 사용
• 즉 가상의 컴퓨터를 하나를 임대한것 ex) EC2 Instance

• 💡 플랫폼 ⇒ PaaS(network + storage + computing + OS,Runtime)*

• 인프라 + OS + 런타임 제공
• 바로 코드만 올려서 돌릴 수 있도록 구성
• 예시: Firebase , Google App Engine 등

• 💡 소프트웨어 ⇒ Saas(필요한 소프트웨어 모든 것을 제공)*

• 서비스 자체를 제공
• 다른 세팅 없이 서비스만 이용
• 예시: Gmail, Dropbox, Slack, Google Docs
  > 💡 **클라우드 서비스의 유형**| 유형 | 설명 | 예시 | | --- | --- | --- | | **IaaS (Infrastructure as a Service)** | 가상 서버, 네트워크, 스토리지 등의 인프라 제공 | AWS EC2, GCP Compute Engine | | **PaaS (Platform as a Service)** | 애플리케이션 개발을 위한 플랫폼 제공 | AWS Elastic Beanstalk, Heroku | | **SaaS (Software as a Service)** | 웹 기반 소프트웨어 서비스 제공 | Gmail, Google Docs, Dropbox |

다음 포스팅에는 AWS Cloud 사용한 서버 환경 구성에 대해 알아보는 시간을 가져보겠습니다! 이번 포스팅도 찾아와주셔서 감사합니다 ❤️❤️❤️

Spring Boot의 CORS 설정

CORS 설정에 들어가기에 앞서, 우선 CORS가 무엇인지부터 알고 가는 시간을 가져봅시다!

CORS(Cross-origin-resource-Sharing)란?

CORS는 Cross-origin-resource-Sharing)의 줄임말로, 교차 출처 리소스 공유를 의미하며, 교차 출처는 ‘ 다른 출처’라고 생각하면 쉽습니다. 즉, 웹 브라우저에서 실행되는 스크립트가 다른 도메인의 리소스에 접근할 수 있도록 하는 보안 기술입니다. 보안 정책으로 인해 브라우저는 동일 출처 정책(Same-origin-policy) 따르며, 이는 웹페이지에서 로드된 문서나 스크립트가 동일한 출처(프로토콜, 호스트, 포트가 동일)에서만 리소스에 접근할 수 있는 것을 의미합니다.

• 동일 출처 정책에 위반 되는 경우
  • 프로토콜 - http / https
  • 도메인 - domain.com / other-domain.com
  • 포트번호 - port 번호 8080 / 3000
    웹 에플리케이션은 다양한 도메인 간 리소스 공유가 필요한 경우가 많습니다.( 백엔드와 프론트엔드간의 연동!)
    ⇒ 이때 필요한 것이 CORS 입니다!

Spring Boot에서 React의 요청을 허용하도록 CORS 설정을 추가합니다! 아래는 WebConfigurer를 사용하여 Spring Boot에서 CORS 설정하는 코드입니다.

• 우선 WebConfig.java 를 파일을 어느 경로에 두어야 하는지도 중요합니다. 우선, java/프로젝트 명에 오른쪽클릭 → New → Package를 클릭해서 WebConfig.java 파일을 생성합니다.

  

![](https://velog.velcdn.com/images/ronaldo_7/post/c71a177c-e45d-49be-b3c8-d92d4ad30e50/image.png)

WebConfig.java

package service.socialloginwebapp.Config;

import org.springframework.context.annotation.Configuration;
import org.springframework.web.servlet.config.annotation.CorsRegistry;
import org.springframework.web.servlet.config.annotation.WebMvcConfigurer;

@Configuration
public class WebConfig implements WebMvcConfigurer {

    @Override
    public void addCorsMappings(CorsRegistry registry) {
        registry.addMapping("/**") // 모든 경로에 대해 CORS 허용
                .allowedOrigins("http://localhost:3000") // React 포트 허용
                .allowedMethods("GET", "POST", "PUT", "DELETE", "OPTIONS") // 허용할 HTTP 메서드
                .allowedHeaders("*") // 모든 헤더 허용
                .allowCredentials(true); // 쿠키 및 인증 정보 허용
    }
}

• @Configuration
  • 이 클래스가 Spring의 설정 클래스가 되도록 하는 어노테이션 입니다.
• WebMvcConfigurer
  • Spring MVC 추가 설정을 위해 WebMvcConfigurer 구현합니다.
• addCorsMappings 메서드
  • CORS 정책을 정의하는 핵심 메서드입니다.
  • addMapping(”**/): 모든 경로에 대해 CORS 설정을 허용합니다.
  • allowedOrigins("http://localhost:3000"): React 개발 서버(포트 3000)에서의 요청을 허용합니다.
  • allowedMethods("GET", "POST", "PUT", "DELETE", "OPTIONS"): 허용할 HTTP 메서드를 지정합니다.
  • allowedHeaders("*"): 모든 헤더를 허용합니다.
  • allowCredentials(true): 쿠키 및 인증 정보를 포함한 요청을 허용합니다.

Tip

• 배포 환경 설정 배포 시에는 allowedOrigins에 실제 프론트엔드 서버의 URL을 추가해야 합니다. 예를 들어, https://my-frontend-app.com와 같은 URL을 설정합니다.
  • 보안 강화 필요에 따라 허용할 경로(addMapping)나 HTTP 메서드(allowedMethods)를 더 구체적으로 설정하여 보안을 강화할 수 있습니다.

간단한 Test API 작성

Spring Boot와 React의 연동을 확인하기 위해 REST API를 작성합니다.

TestController.java

package service.socialloginwebapp.Controller;

import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

@RestController
public class TestController {

    @GetMapping("/api/hello")
    public String sayHello() {
        return "Hello from Spring Boot!";
    }
}

• 연동이 성공하면 React 화면에 (localhost:3000)에 연결된 API(api/hello)에는 Hello from Spring Boot! 를 반환합니다.

React의 CORS 설정

Axios의 설정

• React의 API 호출을 위해 Axios Instance를 생성합니다!

  여기서 잠깐! Axios란?

  • JavaScript에서 HTTP 요청을 쉽게 처리할 수 있도록 도와주는 라이브러리입니다
    • HTTP 요청 처리 Restful API 서버 (Spring Boot)와 프론트엔드간의 데이터를 주고받기 위해 GET,POST,PUT,DELECT 등의 HTTP 요청을 보냅니다.
    • 기본 설정 관리 - axios.create() 사용하여 baseURL과 공통으로 사용하는 headers를 설정합니다. 이렇게 기본 설정을 해놓으면 각 요청마다 반복적으로 설정하지 않아도 됩니다
      • headers: API 요청에 포함되는 공통 헤더를 지정합니다. 여기서는 JSON 데이터를 보내기 위해 Content-Type: application/json 헤더를 설정
    • axiosInstance를 생성하여 프로젝트 전반에서 같은 설정으로 API 요청을 재사용할 수 있습니다. 이를 통해 코드가 간결해지고 유지보수성이 향상됩니다.

AxiosInstance.js의 경로

import axios from 'axios';

const axiosInstance = axios.create({
  baseURL: 'http://localhost:8080/api', // Spring Boot API baseURL
  headers: { //헤더
    'Content-Type': 'application/json',
  },
});

export default axiosInstance;

테스트 페이지 작성

frontend/src/pages/TestPage.js 경로에 연동을 위한 테스트 페이지 작성합니다.

import React, { useEffect, useState } from 'react';
import axiosInstance from '../api/axiosInstance';

const TestPage = () => {
    const [message, setMessage] = useState('');

    useEffect(() => {
        axiosInstance.get('/hello') // Spring Boot API 엔드포인트 호출
            .then(response => {
                setMessage(response.data);
            })
            .catch(error => {
                console.error('Error fetching data:', error);
                setMessage('Failed to fetch data from server.');
            });
    }, []);

    return (
        <div>
            <h1>React와 Spring Boot 연동 테스트</h1>
            <p>{message}</p>
        </div>
    );
};

export default TestPage;

라우팅 설정

• 라우팅(Routing)이란?

  • 웹 애플리케이션에서 사용자가 특정 URL로 접속했을때, 어떤 페이지(컴포넌트)를 렌더링 할지 결정하는 과정을 말합니다. 일반적으로 전통적인 웹 애플리케이션은 서버가 각 페이지를 제공하지만, React와 같은 싱글 페이지 애플리케이션(SPA)은 클라이언트 측에서 라우팅을 처리를 합니다!

• React Router의 간단한 개념

  • BrowserRouter
    • 애플리케이션의 라우팅을 설정하는 기본 컴포넌트 입니다
    • URL 변화를 감지하고 적절한 컴포넌트를 렌더링 합니다.
  • Routes
    • 각 경로(URL)에 대한 설정을 포함하는 컨테이너 입니다
    • 여러개의 Route를 포함하여 URL에 따른 컴포넌트를 렌더링 합니다
  • Route
    • 개별 경로를 정의하며, 경로에 따라 어떤 컴포넌트를 렌더링할지 지정합니다.
    • path 속성으로 URL을 지정하고, element 속성으로 렌더링할 컴포넌트를 설정합니다.

라우팅 코드 → frontend/src/App.js 경로에 라우팅 설정에 대한 코드를 작성합니다.

import React from 'react';
import { BrowserRouter as Router, Route, Routes } from 'react-router-dom';
import TestPage from './pages/TestPage';

function App() {
  return (
      <Router>
        <Routes>
          <Route path="/" element={<TestPage />} />
        </Routes>
      </Router>
  );
}

export default App;

→ 브라우저에서 http://localhost:3000으로 접속하면, TestPage 컴포넌트의 내용이 렌더링됩니다.

실행 및 결과 확인

• Spring Boot + React를 동시에 실행시켜 결과를 확인합니다. 위에서 말한 것 처럼, 연동이 성공하면 Hello from Spring Boot! 를 반환하고 실패하면 Failed to fetch data from server 를 반환할 것입니다!

Spring Boot의 서버 실행

./gradlew bootRun

React의 서버 실행

npm start

결과 화면

→ 올바르게 연동이 완료된 것을 확인할 수 있습니다!!! 여기까지 따라오셨다면 React와 Spring Boot의 연동은 성공하신 겁니다 ㅎㅎ

다음 포스팅에는 MySql 스키마 생성과 JDBC 라이브러리를 이용하여 스프링과 MySQL을 연동해보고 테스트 하는 시간을 가져보도록 하겠습니다 ❣️

스프링의 정의

• 엔터프라이즈용 Java 어플리케이션 개발을 편하게 할수 있는 오픈소스 경량급 어플리케이션 프레임워크

  • 프레임워크란?

    어떠한 목적을 쉽게 달성할 수 있도록 해당 목적과 관련된 코드의 뼈대를 미리 만들어둔것.

  • 어플리케이션 프레임워크

    어플리케이션 프레임워크를 개발하는데에 있어 필요한 모든 업무 분야 및 모든 기술과 관련된 코드들의 뼈대를 제공

스프링의 특징

• POJO 프로그래밍 지향(스프링의 가장 큰 특징)

  Plain Old Java Object → 순수 자바만을 통해 생성한 객체를 의미. 즉, 다른 기술을 사용하지 않는 순수한 Java만을 사용하여 만든 객체

  Import문을 통하여 라이브러리의 메서드를 사용하고 있는 개체는 순수한 자바만을 사용한 것이 아니므로 신기술이 등장하거나 코드를 모두 고쳐야하는 상황에서 해당 기술을 사용하고 있는 모든 객체들의 코드를 전부 바꾸어주어야함

  반면, POJO는 순수 자바만을 사용하여 만든 객체이므로 특정 기술이나 환경에 종속되지 않아 외부 기술이나 규약의 변화에 얽메이지 않아, 보다 유연하게 변화와 확장에 대체할 수 있다. POJO 사용해 비즈니스 로직을 구현하면 객체지향 설계를 제한없이 적용할 수 있으면서, 코드가 단순해져 테스트와 디버깅 또한 쉬워진다.

  

**POJO 프로그래밍을 위해 스프링이 지원하는 기술은IoC/DI**, **AOP**, **PSA가 있음.**

## **IoC / DI (Inversion of Control / Dependency Injection, 제어의 역전 / 의존성 주입)**

자바는 객체지향언어이므로 객체들 간의 관계를 적절히 맺어주는것은 중요한 요소. A 인스턴스가 B 인스턴스의 메소드를 호출하고 있다면 이는 의존관계를 맺은 것이고 “A가 B에 의존하고 있다” 라고 설명. 만약, A가 사용할 객체를 B가 아니라, 새롭게 C를 정의해서 사용하고자 한다면 어떻게 해야 할까. 

![](https://velog.velcdn.com/images/ronaldo_7/post/8f073f73-bd28-42e5-9b19-db7fbfaba93f/image.png)


**만약 기존에 B를 사용하던 객체가 A 뿐만 아니라, 수십 또는 수백개가 있다면 모든 객체의 코드를 수정해주어야 한다.**

그러나 스프링을 이용하면 변화가 발생한 상황에 최소한의 수정만으로 변화를 유연하게 수용이 가능함. 

![](https://velog.velcdn.com/images/ronaldo_7/post/485bec06-5da8-4532-8f87-6cbd89cfe6ca/image.png)


**A는 자신이 사용할 객체를 스스로 생성하지 않고, 생성자를 통해 외부로부터 받아오고 있다.** 즉, A는 자신이 사용할 객체를 알지 못하며, 그저 `i`에 할당된 인스턴스에 **`example()`**이라는 메서드가 존재한다는 것만 알고 있다.

누군가 A가 사용할 객체를 결정하고 생성해서 A가 인스턴스화될 때 인자로 전달해주어야만 한다. 그래야 A는 B의 것이든, C의 것이든 **`example()`** 메서드를 호출할 수 있을 것이기 때문이다. 그 누군가가 무엇일까?

그 누군가가 바로 스프링이다. 스프링을 사용하면 애플리케이션의 로직 외부에서 A가 사용할 객체를 별도로 설정할 수 있습니다. **개발자가 설정 클래스 파일에 A가 사용할 객체를 C로 설정해두면, 애플리케이션이 동작하면서 스프링이 설정 클래스 파일을 해석하고, 개발자가 설정해둔대로 C 객체를 생성하여 A의 생성자의 인자로 C를 전달해둔다.**

이처럼 **개발자가 아닌 스프링이 A가 사용할 객체를 생성하여 의존 관계를 맺어주는 것을 IoC(Inversion of Control, 제어의 역전)라고 하며, 그 과정에서 C를 A의 생성자를 통해 주입해주는 것을 DI(Dependency Injection, 의존성 주입)라고 한다…**

# **AOP (Aspect Oriented Programming, 관심 지향 프로그래밍)**

애플리케이션을 개발할 때에 구현해야 하는 기능들은 크게 **공통 관심 사항**과 **핵심 관심 사항**으로 분류할 수 있다. 먼저, **핵심 관심 사항은 애플리케이션의 핵심 기능과 관련된 관심 사항**으로, 커피 주문 애플리케이션을 예로 든다면 메뉴 등록하기, 주문하기, 주문 변경하기 등이 있을 것임.

반면, **공통 관심 사항은 모든 핵심 관심 사항에 공통적으로 적용되는 관심 사항들을 의미한다.** 예를 들어, 메뉴 등록하기, 주문하기, 주문 변경하기 등 모든 핵심 관심 사항에는 로깅이나 보안 등과 관련된 기능들이 공통적으로 적용된다.

이 때, 핵심 관심 사항과 공통 관심 사항이 코드에 아래와 같이 함께 모여 있으면 필연적으로 **공통 관심 사항과 관련된 코드가 중복됨**. 이처럼 코드가 중복되어져 있는 경우, **공통 관심 사항을 수행하는 로직이 변경되면 모든 중복 코드를 찾아서 일일이 수정해주어야만 합니다.**

![](https://velog.velcdn.com/images/ronaldo_7/post/b4b51fe1-c5ac-4c19-b3d8-2f232b7b0234/image.png)


코드의 중복이라는 문제를 해결하기 위해서는 공통 관심 사항과 관련된 기능들을 별도의 객체로 분리해낸 다음, 분리해낸 객체의 메서드를 통해 공통 관심 사항을 구현한 코드를 실행시킬 수 있도록해야한다. 이렇게 어플리케이션 전반에 걸쳐 적용하는 공통기능을 비즈니스 로직으로부터 분리해내는 것을 AOP라고 함.

## **PSA (Portable Service Abstraction, 일관된 서비스 추상화)**

스프링은 자바 백엔드 개발에 있어 핵심적인 역할을 수행하는 프레임워크이다. 백엔드 개발에 있어서 데이터베이스는 떼어낼수 없는 개념이고, 웹서버는 데이터베이스와 소통하며 웹 클라이언트의 요청을 처리해야한다. 데이터베이스의 종류는 MySQL, Oracle, Maria DB, Mongo DB 다양하다.

만약 MySQL을 사용하여 개발을 완료, 후에 Maria DB로 데이터베이스를 바꿔야 하는 상황을 가정하면 엄청난 양을 수정해야한다. 

그러나 스프링을 사용하면 동일한 사용방법을 유지한 채로 데이터베이스를 바꿀 수 있다. 이는 **스프링이 데이터베이스 서비스를 추상화한 인터페이스를 제공해주기 때문에 가능하다. 즉, 스프링은 자바를 사용하여 데이터베이스에 접근하는 방법을 규정한 인터페이스를 적용하고 있고 , 이를 JDBC(Java Database Connectivity)라고 함**

이러한 JDBC처럼 **특정 기술과 관련된 서비스를 추상화하여 일관된 방식으로 사용될 수 있도록 한 것을 PSA(Portable Service Abstraction, 일관된 서비스 추상화)라고함.

## **스프링부트(Spring Boot)**
**스프링 부트는 스프링으로 어플리케이션을 만들때 필요한 설정을 간편하게 처리해주는 별도의 프레임워크이다.** 
스프링 부트를 사용하면 초기 설정을 간편하게 할 수 있는 것 외에도 몇 가지 장점이 있다. 기존에는 배포를 할 때에 별도의 외장 웹 서버를 설치하고, 프로젝트를 War 파일로 빌드하여 배포를 진행했는데, 이러한 방식은 처리 속도가 느리며 번거롭다는 단점을 가진다. 반면, **스프링 부트는 자체적인 웹 서버를 내장**하고 있어, 빠르고 간편하게 배포를 진행할 수 있습니다. 또한, **스프링 부트를 사용하면 독립적으로 실행 가능한 Jar 파일로 프로젝트를 빌드할 수 있어, 클라우드 서비스 및 도커와 같은 가상화 환경에 빠르게 배포할 수 있음.**



다음 시간에는 **스프링부트**에 대한 포스팅으로 찾아뵙겠습니다❣️

운영체제

• OS:Mac OS
• IDE:IntelliJ
• Shell: Zsh

Spring Boot 프로젝트 생성

• IntelliJ에서 New Projrct 클릭!

• 클릭 후 Generators에서 Spring Initializr 선택

• Name: 본인이 개발하려는 프로젝트의 방향에 대한 이름으로 지어주면 됩니다
• Language: Java로 세팅해둡시다.
• Type: Gradle로 설정합니다.
• JDK: 21 말고 무조건 17!! 로 설정해둡시다. 17이 없을경우 JDK 17을 다운받으셔야 합니다.
• Java: 이 역시 JDK 버전과 맞는 17로 설정합시다.

의존성 설치 단계

• Spring 이 처음 나올때는 의존성을 일일이 다 잡아서 설치해야합니다만, Spring Boot는 여러 의존성들을 프로젝트 생성 단계에서 설치할 수 있습니다!
• Spring Boot Initializr에서 제공하지 않는 의존성도 있기 때문에 프로젝트를 개발하면서 의존성을 추가해야되는 경우도 있습니다! 그러나 Spring Boot에서 의존성을 추가하는 작업은 아주 간단하기 때문에 걱정은 안하셔도 됩니다! 🦾

추가한 초기 의존성

• 저는 일단 소셜 로그인을 구현해보기 위해서 이렇게 의존성을 추가했습니다!
• 각 의존성에 대한 설명을 조금 해보겠습니다
  • Spring Web:
    • RESTful API 및 HTTP 요청/응답 처리를 위한 기본 모듈입니다.
      • 클라이언트(React)와 통신할 백엔드 개발에 필수입니다!!
  • Lombok:
    • Getter/Setter, 생성자 등 반복적인 코드를 줄여주는 편리한 도구.
  • Spring Boot DevTools:
    • 코드 변경 시 애플리케이션을 자동으로 리로드하여 개발 속도 향상.
  • Spring Web Services:
    • SOAP 기반 웹 서비스를 구현하거나 사용할 때 필요.
    • 현재 프로젝트에서는 소셜 로그인에는 직접적으로 필요하지 않을 수 있음.
  • Spring Security:
    • 인증 및 권한 관리를 위한 기본 프레임워크.
    • OAuth2와 연동하여 로그인 처리 가능.
  • OAuth2 Client:
    • 소셜 로그인을 구현하기 위한 필수 의존성.
    • Google, Facebook, GitHub 등의 OAuth2 인증 처리 가능.
  • Spring Data JPA:
    • 데이터베이스 연동 및 ORM(Object-Relational Mapping)을 지원.
    • MySQL과 함께 사용할 경우 적합.
  • H2 Database:
    • 테스트용으로 내장형 데이터베이스를 사용.
    • 개발 초기 단계에서 빠르게 데이터베이스를 구축하고 테스트 가능.
  • Validation:
    • 사용자 입력 값 검증에 사용.
    • 소셜 로그인과 더불어 폼 데이터(예: 프로필 정보, 추가 입력 값 등) 검증에 유용.
  • MySQL Driver:
    • MySQL 데이터베이스와 연결하기 위해 필요.
    • 프로덕션 데이터베이스로 MySQL을 사용할 때 필수.

초기 프로젝트 생성 후 화면

• create를 누르신 분이라면 이제 이렇게 화면이 뜨실 겁니다! 영어도 많고 조잡해 보이지만 천천히 저희의 목표를 달성하기위해 차근차근 진행해보자구요!

Spring Boot 실행

이제 백엔드의 초기설정은 어느정도 되었으니 서버 실행을 통해 문제없이 돌아가는지 확인해볼까요?

./gradlew bootRun

• 위 명령어를 터미널에 쳐서 서버를 실행시키거나 intellij 오른쪽 상당에 화살표 모양을 클릭해 서버를 실행시킵니다!

→ 정상적으로 서버가 실행이 되었으면 8080포트에 실행이 되고, 위 이미지와 같은 화면이 나오실껍니다. 여기까지 따라오셨나요?

이제 백엔드 프로젝트 초기 설정은 어느정도 되었으니 React 프론트엔드 프로젝트를 생성할 차례입니다. 따라오세요!

React 프로젝트 생성

터미널을 찾아라!

• 일단, 왼쪽 아래를 보시면 터미널이라는 메뉴가 보이실겁니다. 이걸 Click! 해주세요. 앞으로 저희가 프로젝트에 React를 설치하기 위해 명령어를 입력할 프롬프트입니다.

• 터미널을 누르면, 이렇게 나오텐데 본인 프로젝트를 설정해둔 경로에 따라 저와는 조금 다를 수 있다는 점 인지해주시면 감사하겠습니다!

리액트 프로젝트 생성

npx create-react-app frontend

• React 프로젝트 생성: Spring Boot 프로젝트 폴더와 별도로 React 프로젝트 폴더를 생성해야 합니다! 위에 명령어를 그대로 입력하시면 됩니다.

• 시간이 조금 소요될 수 있다는 점 !!!! 잊지마세요
• 설치가 완료되었다면, 리액트 프로젝트를 생성하기 전과 구조가 약간 다른것을 확인할수 있어요!

리액트 프로젝트 설치 후 전체 프로젝트 구조 변화

• Frontend라는 폴더가 생겨났고 앞으로 프론트엔드 쪽 코드를 개발하거나 수정할때는 거의 모든 코드가 저 폴더 안에서 이루어집니다.

frontend 폴더로 이동

cd frontend

• cd 명령어로 frontend 폴더로 이동합니다!

React 의존성 설치

• 아까 스프링 부트 초기 설정에서 의존성을 설치하는 부분이 있었죠? 리액트 역시 의존성을 초기에 설치를 하는데요(이후에 의존성 추가해도 큰 문제는 없습니다).

• 프로젝트에 필요한 라이브러리를 설치하는 과정입니다.

npm install react-router-dom axios @mui/material @emotion/react @emotion/styled

• 우선적으로, 저는 React Router, axios, Material-ui(MUI)를 설치하였습니다.
  • React Router: 페이지 이동을 위한 라우터입니다.
  • axios: 백엔드와 프론트엔드를 HTTP통신으로 이어주는 라이브러리입니다.
  • Material-UI (MUI): 간단한 UI 구성.
• 저는 더 다양한 리액트의 라이브러리를 경험해보고자 추가적으로 라이브러리를 설치 하였습니다! 저와 같이 함께 하실 분은 따라와 주세요😃

상태관리 관련

• Redux
  • 에플리케이션의 전역 상태 관리를 합니다.
  • 로그인 관리, 사용자 세션, 테마 또는 복잡한 상태 관리를 효율적으로 처리합니다.

npm install @reduxjs/toolkit react-redux

• Zustand
  • Redux보다 더 가벼운 상태관리 도구입니다.

npm install zustand

스타일링 관련

• Styled-components
  • CSS-in-JS 방식으로 컴포넌트를 스타일링합니다.
  • CSS 와 JavaScript를 통합하여 React 컴포넌트 스타일링을 효율적으로 관리가 가능합니다.

npm install styled-components

• Tailwind CSS
  • 유틸리티 기반의 CSS 프레임워크입니다.
  • 빠르고 일관된 스타일링을 적용할 수 있습니다

npm install -D tailwindcss postcss autoprefixer
npx tailwindcss init

HTTP 요청 관리

• React Query (TanStack Query)
  • 서버 상태 관리 및 캐싱 역할을 합니다.
  • Axios보다 더 효율적으로 API 데이터를 관리하며, 캐싱 및 리패칭 기능을 제공합니다.

npm install @tanstack/react-query

폼 관리

• React Hook Form
  • 폼 상태와 유효성 검사 관리를 합니다.
  • 로그인, 회원가입 같은 폼 처리를 간단한 API로 폼 관리를 쉽게 배울 수 있습니다.

npm install react-hook-form

아이콘 및 유틸리티

• React Icons
  • 다양한 아이콘을 쉽게 추가할 수 있습니다

npm install react-icons

• Moment.js 또는 Day.js
  • 날짜와 시간을 관리하는 역할을 합니다.
  • 시간 기반 데이터(예: 게시글 작성 시간)를 다룰 때 유용합니다.

npm install dayjs

테스트

• Jest + Testing Library
  • React 컴포넌트와 API의 단위 및 통합 테스트 작성에 용이합니다.

npm install --save-dev jest @testing-library/react @testing-library/jest-dom

애니메이션

• Framer Motion
  • 애니메이션 및 전환 효과 구현에 용이합니다.

npm install framer-motion

리액트 실행

이제 필요한 라이브러리 설치가 끝났으면 리액트가 정상적으로 돌아가는지 확인을 해봐야겠죠??

npm start

이 명령어를 통해 리액트를 실행하면, 프론트엔드를 담당하는 리액트의 포트가 정상적이고, 리액트가 정상적으로 돌아가기 위한 필수적인 라이브러리가 설치되었다면 정상적으로 밑에 이미지 화면이 나와야합니다.

여기까지 진행이 완료되었다면 Spring Boot와 React의 초기 설정과 실행은 완료되었고, 다음 포스팅에서 Spring Boot와 React의 연동 준비 과정에 대해 포스팅 해보겠습니다! 긴 글 읽어주셔서 감사합니다. 다음 포스팅에서 뵙겠습니다 ❣️

백트래킹(BackTracking)이란?

• 어떤 문제를 풀 때 모든 경우의 수를 체크해보면서, 해가 아닌수의 경우를 만나면 그 이전 상태로 되돌아가면서 다른 케이스를 체크하는 알고리즘입니다. (또는 되추적이라고 합니다)

DFS(깊이우선탐색)와 BackTracking

우선, 본격적인 비교에 앞서 간단하게 깊이우선탐색이 무엇인지 간단하게 집고 넘어가봅시다. 오늘은, 간단하게 어떤 느낌인지 찍먹 해보는 느낌으로 머릿속에 인지해두고, 이후 포스팅에서 깊이우선탐색과 너비우선탐색 알고리즘에 대해 자세히 다뤄보겠습니다.

DFS(Depth- Firsh-Search)

• 깊이 우선 탐색으로 가능한 모든 경로를 탐색합니다.(그래프에서 깊은 부분을 우선적으로 탐색하는것입니다)
• 모든 경로를 탐색하는 특징으로 불필요할것 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 줄이진 못합니다.

백트래킹(BackTracking)

• 알고리즘 기법중 하나로 재귀적으로 문제를 해결하되 현재 재귀를 통해 확인 중인 상태가 제한조건에 위배가 되는지 확인하고, 해당 상태가 위배되는경우, 해당상태를 제외하고 다음단계로 넘어갑니다.
• 쉽게 말하면, 해를 찾는 도중 해가 없을것이라고 판단되면, 되돌아가서 해를 찾는다는(BackTrack) 알고리즘입니다.
• 여기서 더 이상 탐색할 필요가 없다는 상태를 제외한다라고 하는데, 이를 가지치기라고 합니다.

백트래킹은 모든 경우의 수에서 조건을 만족하는 경우를 탐색하는 것이기 때문에, 완전탐색기법인 DFS와 BFS 로 구현이 가능합니다.

백트래킹 특성에서 조건에 부합하지 않으면 이전 수행으로 돌아가야 함으로 BFS보다는 DFS이 구현하기 더 편하기 때문에 주로 DFS를 사용합니다.

백트래킹 알고리즘은 언제 사용해야할까?

백트래킹 알고리즘은 모든 경우의 수를 탐색하는 문제에서 특히 유용합니다! 하지만 단순히 모든 경우의 수를 탐색하는 것 뿐만 아니라 탐색 중 불필요한 경로를 가지치기하여 성능을 최적화할 수 있다는 점에서 유용합니다.

순열과 조합 생성

• 특정 범위에서 모든 순열 또는 조합을 거쳐야 하는 문제
• 중복없이 모든 경우의 수를 나열해야 하거나 특정 조건을 만족해야하는경우. ex) N과M, 문자열의 순열 생성, 로또번호 조합 나열

  경로 탐색 문제

• 모든 가능한 경로를 탐색해야하지만, 특정 조건을 만족하는 경로만 선택하는 문제

  조합 최적화 문제

• 모든 경우의 수를 탐색하여 최적의 값을 찾는 문제
• 일반적으로 그리디 알고리즘과 동적 프로그래밍 방법으로 문제를 풀 수 없을때 사용합니다.

=> 그러나 탐색해야하는 공간이 매우 큰 경우, 가지치기가 어렵다면 백트래킹 알고리즘을 적용하기에 현실적으로 어려울수도 있습니다! 그렇기 때문에 문제를 마주할때, 그리디 알고리즘과 동적 프로그래밍도 같이 고려해야합니다!

백트래킹 예시

예시1) 3 * 3 행렬게임

• 규칙: 3 *3 행렬이 존재할때 3개의 숫자를 모두 선택하는데, 단 선택한 숫자들의 행과 열은 모두 중복되면 안된다. (즉 뽑아내는 행과 열이 모두 달라야한다.)

• R은 루트노트 즉, 아무 숫자도 선택하지 않은 상태

1. 첫 번째 행에서 숫자 2, 4, 또는 3 중 하나를 선택.
2. 두 번째 행에서 숫자를 선택하되, 이전 단계에서 선택한 열을 제외.
3. 세 번째 행에서 숫자를 선택하되, 이전 두 단계에서 선택한 열을 제외.

코드동작

package BackTracking;

import java.util.ArrayList;
import java.util.List;

public class BacktrackingExample {
    static int[][] board = {
        {2, 4, 3}, // Row 0
        {1, 3, 7}, // Row 1
        {6, 5, 6}  // Row 2
    };
    static boolean[] visited; // 열 선택 여부를 나타내는 배열
    static int N = 3; // 행렬 크기 (3×3)
    static int[] result; // 현재 경로에서 선택된 숫자를 저장
    static List<int[]> allResults = new ArrayList<>(); // 모든 결과를 저장

    public static void main(String[] args) {
        visited = new boolean[N]; // 열 방문 여부 초기화
        result = new int[N]; // 선택된 숫자를 저장할 배열

        backtrack(0); // 백트래킹 시작 (첫 번째 행부터)

        // 모든 결과 출력
        for (int[] res : allResults) {
            for (int num : res) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

    static void backtrack(int row) {
        // 기저 조건: 모든 행에서 숫자를 선택한 경우
        if (row == N) {
            allResults.add(result.clone()); // 결과 저장
            return;
        }

        // 현재 행(row)의 가능한 열 탐색
        for (int col = 0; col < N; col++) {
            if (!visited[col]) { // 해당 열이 선택되지 않았다면
                visited[col] = true; // 열 선택
                result[row] = board[row][col]; // 숫자 선택
                System.out.printf("Row %d -> Col %d 선택: %d%n", row, col, board[row][col]); // 디버깅 메시지
                backtrack(row + 1); // 다음 행으로 이동
                visited[col] = false; // 열 선택 해제 (백트래킹)
            }
        }
    }
}

main 메서드

public static void main(String[] args) {
    visited = new boolean[N]; // 열 방문 여부 초기화
    result = new int[N]; // 선택된 숫자를 저장할 배열

    backtrack(0); // 백트래킹 시작 (첫 번째 행부터)

    // 모든 결과 출력
    for (int[] res : allResults) {
        for (int num : res) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

• visit배열과 result배열을 초기화 합니다.
• bracktrack(0)를 호출하여 백트래킹 탐색을 시작합니다.
• 탐색이 끝난후 저장된 모든 결과(allResults) 출력합니다.

기저조건

if (row == N) {
    allResults.add(result.clone()); // 결과 저장
    return;
}

• 현재 탐색중인 행이 N(행렬의 크기)와 같다면, 모든 행에서 숫자를 선택합니다.

열탐색

for (int col = 0; col < N; col++) {
    if (!visited[col]) { // 해당 열이 선택되지 않았다면
        visited[col] = true; // 열 선택
        result[row] = board[row][col]; // 숫자 선택
        backtrack(row + 1); // 다음 행으로 이동
        visited[col] = false; // 열 선택 해제 (백트래킹)
    }
}

• if( !visited[col]) → 현재열이 선택되지 않았다면!
  • 현재 행(row)에서 가능한 열(col)을 순회하며 선택하지 않은 열을 찾습니다.
  • 선택한 열(col)을 visited[col] = true로 표시하고, 해당 숫자를 result[row]에 저장합니다.
  • 다음행으로 이동하여(row+1) 백트래킹을 수행합니다.
  • 현재열의 탐색이 끝나면 선택을 해제(visited[col] = false)하여 다음 경로를 탐색할 수 있게 합니다.

백트래킹 동작 과정

초기 상태

• row = 0 (현재 탐색 중인 행은 첫 번째 행)
• 가능한 열(col)은 모두 선택 가능: col = 0, 1, 2.
• 아직 아무 숫자도 선택되지 않았고, visited = [false, false, false].

첫 번째 선택 (첫 번째 행, 첫 번째 열)

• 현재 상태: row = 0, col = 0
• 숫자 2를 선택합니다 (board[0][0]).
• 선택한 열 col = 0은 방문 표시: visited = [true, false, false].
• 현재 경로(result): [2, _, _].
• 다음 단계:
  • 행을 한 칸 아래로 이동: backtrack(1) 호출.

두 번째 선택 (두 번째 행, 두 번째 열)

• 현재 상태: row = 1, 가능한 열은 col = 1, col = 2 (왜냐하면 col = 0은 이미 방문했음).
• 선택한 열: col = 1 → 숫자 3을 선택 (board[1][1]).
• 선택한 열 col = 1은 방문 표시: visited = [true, true, false].
• 현재 경로(result): [2, 3, _].
• 다음 단계:
  • 행을 한 칸 아래로 이동: backtrack(2) 호출.

세 번째 선택 (세 번째 행, 세 번째 열)

• 현재 상태: row = 2, 가능한 열은 col = 2 (왜냐하면 col = 0과 col = 1은 이미 방문했음).
• 선택한 열: col = 2 → 숫자 6을 선택 (board[2][2]).
• 선택한 열 col = 2은 방문 표시: visited = [true, true, true].
• 현재 경로(result): [2, 3, 6].
• 기저 조건:
  • 현재 행(row = 2)에서 숫자를 선택했으므로, 모든 행에서 숫자를 선택한 상태입니다 (row == N).
  • 경로 [2, 3, 6]을 allResults에 저장.

백트래킹 (마지막 행에서 되돌아가기)

• 현재 상태: 탐색을 종료하고 이전 단계로 돌아가기 위해 백트래킹을 시작.
• 백트래킹 동작:
  • 열 선택 해제: col = 2 방문 취소 → visited = [true, true, false].
  • 현재 경로에서 선택된 숫자를 제거: [2, 3, _].
  • 이전 단계(row = 1)로 돌아갑니다.

두 번째 행에서 백트래킹 계속

• 현재 상태: row = 1, visited = [true, true, false].
• 마지막에 선택한 열(col = 1) 해제: visited = [true, false, false].
• 현재 경로에서 선택된 숫자를 제거: [2, _, _].
• 다음 탐색:
  • 두 번째 행에서 col = 2를 선택해 새로운 경로를 탐색.

새로운 탐색 및 백트래킹 반복

1. 백트래킹으로 탐색을 계속 진행하면서 모든 가능한 숫자 경로를 탐색.
2. 새로운 경로가 완성될 때마다 결과를 저장.
3. 마지막까지 탐색을 마치면 최종적으로 allResults에 모든 경로가 저장됩니다.

전체 탐색 과정 시각화

백트래킹의 핵심 포인트

1. 탐색 제한: 이미 선택된 열(visited)은 제외하여 중복을 방지.
2. 결과 저장: 기저 조건(row == N)에 도달하면 결과를 저장.
3. 되돌아가기: 선택을 해제하고 이전 상태로 되돌아가 새로운 경로를 탐색.

문제를 통해 백트래킹의 동작을 완벽하게 이해해봅시다!

백준_기본문제_15649_N과M

→ 백트래킹을 이용하여 1-N까지 자연수에서 중복없이 길이가 M인 수열을 출력하는 문제라고 생각이 듭니다!

코드

package Baekjoon;

import java.io.*;
import java.util.*;
//아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성
//1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
//중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력
//수열은 사전 순으로 증가하는 순서로 출력
public class beckjoon15649 {
    static int N,M;
    static boolean[] visited;
    static List<Integer> sequence = new ArrayList<>(); // 현재 수열 저장
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nums = br.readLine().split(" ");
        N = Integer.parseInt(nums[0]); //1부터 N까지 자연수
        M = Integer.parseInt(nums[1]); //중복없이 M개를 고른 수열

        visited = new boolean[N+1];
        backtrack(0);//탐색 시작
    }
    public static void backtrack(int depth){
        if(depth == M){ //길이가 M인 수열이 완성된 경우
            for(int i =0; i<M; i++){
                int num = sequence.get(i);
                System.out.print(num + " ");
            }
            System.out.println();
        }
        for(int i=1; i<=N; i++){
            if(!visited[i]){//숫자 i가 아직 사용되지 않은 경우
                visited[i] = true;// 방문처리
                sequence.add(i);//수열에 추가
                backtrack(depth+1);//재귀호출
                visited[i] = false;
                sequence.remove(sequence.size()-1);//수열에서 제거
            }
        }
    }

}

중복방지의 핵심

visit boolean 배열로 방문 여부를 관리

  if (!visited[i]) {
      // 방문하지 않은 숫자만 처리
  }

• visited[i]: 숫자 i가 이미 수열에 포함되어있는지 확인하는 배열입니다.

• 특정 숫자가 이미 포함되어있는 경우 visited[i]=true로 해당 숫자는 다시 선택되지 않습니다.

• 따라서, 중복되는 수열 (2 2 , 3 3..)같은 수열은 출력되지 않습니다.

• 재귀호출 후 상태 복구(visited[i] == false)*

  visited[i] = true; // 숫자 i 사용
  sequence.add(i); // 수열에 추가
  backtrack(depth + 1); // 재귀 호출
  visited[i] = false; // 숫자 i 사용 해제
  sequence.remove(sequence.size() - 1); // 수열에서 제거

• 재귀 호출을 통해 수열을 완성한 후, 현재 숫자를 다시 사용할수 있도록 상태를 복구합니다.

• 이 과정에서 visited[i] == false로 설정되어 다음 경우의 수를 탐색할때는 이 숫자를 다시 선택할수 있게 합니다.

• suquence.remove(sequence.size()-1) : 중복되지않은 수열을 출력후 다시 상태를 복구하기 위해 사용됩니다.

  • 입력: N = 3, M = 2
    • 초기 상태:
      • sequence = []
    • 탐색 과정:
      1. i = 1 선택 → sequence = [1]:
         • 재귀 호출 시작.
      2. 재귀에서 i = 2 선택 → sequence = [1, 2]:
         • 길이가 2이므로 출력: 1 2.
         • 재귀 종료 후 복구 → sequence = [1].
      3. 다음 숫자 선택: i = 3 → sequence = [1, 3]:
         • 길이가 2이므로 출력: 1 3.
         • 재귀 종료 후 복구 → sequence = [1].
      4. 복구 후 반복문으로 돌아가 i = 2 선택 → sequence = [2]:
         • 이후 탐색 반복...

  ⇒ 백트래킹에는 상태복구가 필수적입니다!!

백준_심화문제_9663_N-Queen

→ 퀸은 열 ,행 , 대각선 선으로 움직일 수 있음! 만약 N*N 체스판 위에 N개의 퀸이 놓여있을때 그 N개의 퀸이 서로 공격하는 경우의 수를 제외해야함!

코드

package Baekjoon;

import java.io.*;

//N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제
//N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램
public class beckjoon9663 {
    static int[] queen; //각 행에 놓은 퀸의 위치 저장
    static int N; //체스판 크기
    static int count = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); //퀸 N개
        queen = new int[N];

        solve(0); //0행부터 탐색 시작
        System.out.println(count); //해결 방법 갯수 출력
    }
    //row번째 행에 퀸 배치 시도
    public static void solve(int row){
        if(row ==N){ //모든 퀸을 배치한 경우
            count++; //해결 방법 증가
            return;
        }

        for(int col =0; col< N; col++){
            if(isSafe(row,col)){ //현재 위치에 퀸 배치가 가능한지 확안
                queen[row] = col;//퀸 배치
                solve(row+1); //다음 행으로 이동
                //백트래킹: 이전으로 돌아와 다른 경우 탐색
            }
        }
    }
    public static boolean isSafe(int row, int col){
        for(int i=0; i<row; i++){
            //현재 퀸을 놓으려는 위치 (row, col)가 이미 배치된 퀸들과 충돌하는지 확인하는 부분
            //같은 열 || 같은 대각선 확인
            if (queen[i] == col || Math.abs(queen[i] - col) == Math.abs(i - row)) { // Math.abs 숫자의 절댓값을 계산하는 메서드
                return false;
            }
        }
        return true;
    }
}

변수 초기화

  public class beckjoon9663 {
      static int[] queen; //각 행에 놓은 퀸의 위치 저장
      static int N; //체스판 크기
      static int count = 0;

      public static void main(String[] args) throws IOException{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          N = Integer.parseInt(br.readLine()); //퀸 N개
          queen = new int[N];

          solve(0); //0행부터 탐색 시작
          System.out.println(count); //해결 방법 갯수 출력
      }

왜 N*N 체스판인데 2차원 배열은 쓰지않고 1차원 배열을 이용하는걸까?

1차원 배열로도 문제를 풀수있고 공간 복잡도 최적화에 더 적합하기 때문입니다.

• int[N][N] 2차원 배열은 N*N 공간이 필요하지만 int[N]으로 문제를 풀면 N공간의 배열만 필요하기 때문에 더 적합합니다.

  퀸 배치 시도

  static void solve(int row) {
        if (row == N) { // 모든 퀸을 배치한 경우
            count++; // 해결 방법 증가
            return;
        }
  
        for (int col = 0; col < N; col++) {
            if (isSafe(row, col)) { // 현재 위치에 배치 가능한지 확인
                queen[row] = col; // 퀸 배치
                solve(row + 1); // 다음 행으로 이동
                // 백트래킹: 다시 돌아와서 다른 경우 탐색
            }
        }
  }

• if (row ==N) : 현재 행이 N에 도달했다는 것은 모든 퀸을 성공적으로 배치

• 해결방법의 경우의 수 count의 갯수를 늘리고 종료합니다.

• for(int col =0; col < N; col++)

  • 현재 행의 각열(col)에 퀸을 배치할 수 있는지 시도합니다.
  • row = 0이면 1번째 행의 모든 경우의 수를 탐색하고 그 후에 row=1이면 두번째 행을 탐색합니다.

• isSafe(row,col) → 이 행과 열에 퀸을 배치할수 있는지를 판단합니다.

• queen[row] : 각 퀸의 행에 놓은 열의 번호를 저장합니다.

• 재귀호출 : solve(row+1) 퀸을 현재 row,col에 배치후에 , 다음 행에 퀸을 배치하기 위해 재귀적으로 solve 함수 호출합니다.

  충돌여부 판단

  public static boolean isSafe(int row, int col) {
    for (int i = 0; i < row; i++) {
        // 현재 퀸을 놓으려는 위치 (row, col)가 이미 배치된 퀸들과 충돌하는지 확인
        if (queen[i] == col || Math.abs(queen[i] - col) == Math.abs(i - row)) {
            return false;
        }
    }
    return true;
  }

• (row,col)→ 현재 퀸을 놓으려는 행과 열입니다.

• for(int i =0; i<row; i++) : 현재 이미 배치된 퀸의 행.

  • 그렇다면 queen[i]는 이미 배치된 퀸의 열이겠죠?

• 이제 충돌 여부를 검사하는 조건문이 들어옵니다.

  • queen[i]==col : 같은 열에 충돌하는 조건입니다.

  • Math.abs(queen[i]-col) - Math.abs( i - row) : 대각선에서 충돌하는 조건입니다,.

    → 이렇게 충돌하는 경우에는 false 반환하여 현재 놓으려는 퀸의 위치가 안전하지 않다는것을 알리기위해 return false;를 반환합니다.

    → 충돌조건에서 통과하면 퀸을 그 자리에 놓아도 안전하다는 뜻이기 때문에 retuen true; 를 반환 합니다.

• 백트래킹, 재귀적 사고, 제약 조건 처리, 데이터 구조 활용, 수학적 사고, 그리고 문제 해결 능력을* 요하는 수준이 낮지않은 문제였습니다.

오늘은 백트래킹의 개념과 문제풀이를 통해 백트래킹 알고리즘에 대해 상세하게 알아보았습니다. 다음 포스팅은 DFS & BFS로 찾아보겠습니다❣️

→ 병합 정렬을 이용한 문제,,, mergeSort() 함수 생성 그리고 재귀를 이용하여 N개의 배열에서 K번째로 정렬되는 숫자를 출력하게 하면 되는건가?

코드

package Baekjoon;

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

//병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해라
public class beckjoon24060 {
    static int[] A; //입력배열
    static int[] temp; //병합 과정에서 임시로 사용될 배열
    static int count = 0; //저장 횟수 추정
    static int result = -1; //k번째 저장된 값을 저장
    public static void main(String[] args) throws IOException{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        String[] nums = br.readLine().split(" ");
        int N = Integer.parseInt(nums[0]);// 배열의 크기
        int K = Integer.parseInt(nums[1]); //병합 정렬의 저장 횟수
        //String 배열을 stream으로 변환 -> 스트림은 배열이나 컬렉션의 요소를 하나씩 처리할 수 있는 연속된 데이터의 흐름임.
        //.mapToInt-> 스트림의 각 요소를 변환하는 작업 수행
        A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        temp = new int[N];

        mergeSort(0,N-1,K);

        //K번째 값이 저장이 되지 않은 경우
        if(result == -1){
            System.out.println(-1);
        }else {
            System.out.println(result);
        }
    }
    public static void mergeSort(int left, int right, int K){
        if(left < right){
            int mid = (left + right) / 2;
            mergeSort(left, mid, K); // 왼쪽 절반 정렬
            mergeSort(mid + 1, right, K); // 오른쪽 절반 정렬
            merge(left, mid, right, K); // 병합
        }
    }
    public static void merge(int left,int mid, int right,int K){
        int i = left; //왼쪽 배열 시작
        int j = mid+1; //오른쪽 배열 시작
        int t = 0; //임시 배열 인덱스

        // 두 부분 배열 병합
        while (i <= mid && j <= right) {
            if (A[i] <= A[j]) {
                temp[t++] = A[i++];
            } else {
                temp[t++] = A[j++];
            }
        }

        //왼쪽 배열 남은 부분 자리
        while(i <= mid){
            temp[t++] = A[i++];
        }
        //오른쪽 배열 남은 부분 자리
        while(j <= right){
            temp[t++] = A[j++];
        }
        //임시 배열을 원본 배열로 복사
        for(int k=0; k<t; k++){
            A[left+k] = temp[k];
            count++; //저장 횟수 증가
            if(count ==K){
                result = A[left+k]; // K번째 저장된 값 저장
                return;// 더 이상 작업하지 않음
            }
        }
    }
}

→ 병합 정렬(Merge Sort)을 구현하여 배열을 오름차순으로 정렬하는 동안 K번째로 저장되는 값을 추적 하는 문제!

문제 요구사항

• 병합 정렬을 수행하면서 정렬된 값이 배열에 저장될때, 저장 순서대로 몇번째 값인지 추적해야합니다.
• K번째로 저장되는 값을 출력하되, K번째 저장작업보다 전체 배열의 병합정렬의 저장 작업이 작으면 -1을 출력하게 합니다.

static int[] A; //입력배열
static int[] temp; //병합 과정에서 임시로 사용될 배열
static int count = 0; //저장 횟수 추정
static int result = -1; //k번째 저장된 값을 저장

⚒️ 왜 static 전역변수를 썼을까?

• Static 키워드는 클래스 변수를 의미합니다.
• Static으로 선언된 변수는 클래스에 모든 메서드에서 공유되고, 인스턴스를 생성하지 않아도 접근이 가능합니다.
• 여기서, 병합정렬을 하는데 재귀함수(mergeSort) 사용하여 배열을 나누고 병합하는데, 이 과정에서 공유되는 데이터가 필요하기 때문입니다!

Main 함수

public static void main(String[] args) throws IOException {
    BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
    String[] nums = br.readLine().split(" ");
    int N = Integer.parseInt(nums[0]); // 배열의 크기
    int K = Integer.parseInt(nums[1]); // 병합 정렬의 저장 횟수

    A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    temp = new int[N];

    mergeSort(0, N - 1, K);

    // K번째 값이 저장되지 않은 경우
    if(result == -1) {
        System.out.println(-1);
    } else {
        System.out.println(result);
    }
}

• main 함수는 프로그램의 입력 처리와 병합 정렬 호출, 그리고 결과 출력까지 전반적인 흐름을 관리합니다.
• 특히,mergeSort(0 , N-1, K); 를 호출하여 배열 전체 구간의 [0,N-1]를 병합 정렬 합니다.

MergeSort 함수

public static void mergeSort(int left, int right, int K) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(left, mid, K); // 왼쪽 절반 정렬
        mergeSort(mid + 1, right, K); // 오른쪽 절반 정렬
        merge(left, mid, right, K); // 병합
    }
}

• 분할(Divide)을 통해 재귀적으로 분할합니다!
• 병합(Merge)을 통해 분할된 배열을 정렬합니다!

int mid = (left + right) / 2;
mergeSort(left, mid, K); // 왼쪽 절반 정렬
mergeSort(mid + 1, right, K); // 오른쪽 절반 정렬
merge(left, mid, right, K); // 병합

• left와 right 기준으로 배열을 절반으로 나눕니다.
• mid = (left + right) / 2를 통해 중간지점을 찾습니다.
• 왼쪽 절반 [left, mid] 와 오른쪽 절반[mid+1, right] 로 나누어 mergeSort를 재귀적으로 호출합니다!
• merge(left, mid, right, K) 병합 과정에서 K번째 저장 작업을 추적하기 위해 전달되는 값입니다.

Merge 함수

public static void merge(int left, int mid, int right, int K) {
    int i = left; // 왼쪽 부분 배열의 시작 인덱스
    int j = mid + 1; // 오른쪽 부분 배열의 시작 인덱스
    int t = 0; // 임시 배열(temp) 인덱스

    // 두 부분 배열 병합
    while (i <= mid && j <= right) {
        if (A[i] <= A[j]) {
            temp[t++] = A[i++];
        } else {
            temp[t++] = A[j++];
        }
    }

    // 왼쪽 배열의 남은 값 처리
    while (i <= mid) {
        temp[t++] = A[i++];
    }

    // 오른쪽 배열의 남은 값 처리
    while (j <= right) {
        temp[t++] = A[j++];
    }

    // 병합된 결과를 원래 배열 A에 복사
    for (int k = 0; k < t; k++) {
        A[left + k] = temp[k];
        count++; // 저장 횟수 증가
        if (count == K) {
            result = A[left + k]; // K번째 저장된 값 저장
            return; // 더 이상 작업하지 않음
        }
    }
}

• 두 정렬된 부분을 하나의 정렬된 배열로 병합합니다.

while (i <= mid && j <= right) {
    if (A[i] <= A[j]) {
        temp[t++] = A[i++]; // 왼쪽 배열 값이 작거나 같으면 temp에 저장
    } else {
        temp[t++] = A[j++]; // 오른쪽 배열 값이 작으면 temp에 저장
    }
}

• 왼쪽 배열과 오른쪽 배열을 비교하여 작은 값을 임시배열인 temp에 저장합니다.
• 각각의 인덱스 ( i 또는 j)를 증가시킵니다.

왼쪽 배열의 남은 값

while (i <= mid) {
    temp[t++] = A[i++]; // 왼쪽 배열에 남은 값을 temp에 저장
}

오른쪽 배열에 남은 값

while (j <= right) {
    temp[t++] = A[j++]; // 오른쪽 배열에 남은 값을 temp에 저장
}

• 한쪽 배열이 모두 temp에 복사된 후, 다른 쪽 배열에 남아 있는 값들을 그대로 temp에 추가합니다.

병합 결과를 원본 배열에 복사

for (int k = 0; k < t; k++) {
    A[left + k] = temp[k];// 병합된 값을 원본 배열로 복사
    count++; // 저장 횟수 증가
    if (count == K) { //K번째 저장된 값 추척
        result = A[left + k]; // K번째 저장된 값 저장
        return; // 더 이상 작업하지 않음
    }
}

표로 풀어쓴 과정!

병합정렬(MergeSort)은 나누어질 수 없을때까지 분할을 하며 이후에 정렬을하며 병합을 합니다. 분할을 반복하는 과정에서 재귀(Recursion)함수가 필수적으로 쓰이며, 시간복잡도는 O(n)입니다. 이해가 쉽게 문제에 대한 코드를 쪼개서 풀이를 했으니 여러분들도 이번 기회에 병합정렬에 대한 정확한 동작을 이해하시고 넘어가셨으면 합니다!! 다음 포스팅에서 뵙겠습니다❣️

📌 정렬의 개념

• 정렬은 데이터를 특정 기준에 따라 오름차순(Ascending) 또는 내림차순(Descending)으로 배열하는 작업입니다.
• 정렬은 대부분의 코딩테스트에서 문제 해결의 기본 도구로 사용되며, 다음과 같은 상황에서 자주 등장합니다:
  • 데이터를 정리하여 탐색이나 검색을 빠르게 하기 위해
  • 특정 조건에 따라 데이터를 조합하거나 그룹화하기 위해
  • 순서를 기반으로 한 로직을 구현하기 위해

📌 정렬 알고리즘의 분류

• 정렬 알고리즘은 크게 비교 기반 정렬과 비비교 기반 정렬로 구분할 수 있습니다.

1. 비교기반 정렬

데이터 간의 비교를 통해 정렬을 수행하여, 일반적으로O(Nlog⁡N) 이상의 복잡도를 가집니다.

• 버블 정렬 (Bubble Sort)
• 삽입 정렬 (Insertion Sort)
• 선택 정렬 (Selection Sort)
• 퀵 정렬 (Quick Sort)
• 병합 정렬 (Merge Sort)
• 힙 정렬 (Heap Sort)

2. 비비교 기반 정렬

데이터를 비교하지 않고, 데이터의 특징(값의 범위 등)을 활용하여 정렬합니다.

대표적인 알고리즘:

• 계수 정렬 (Counting Sort)
• 기수 정렬 (Radix Sort)
• 버킷 정렬 (Bucket Sort)

📌 정렬 알고리즘의 종류와 특징

아래는 주요 정렬 알고리즘의 종류와 특징을 정리한 표입니다:

Java에서는 Arrays와 Collections 클래스의 메서드를 사용하여 효율적으로 정렬을 구현할 수 있습니다. 라이브러리를 활용하면 간단한 코드로 정렬을 처리할 수 있으면서도 다양한 상황에 맞는 정렬 알고리즘을 학습할 수 있습니다. 아래는 정렬 알고리즘의 종류와 Java 예시 코드를 소개합니다.

📌 정렬 알고리즘의 Java 예시 코드

1️⃣ 버블 정렬 (Bubble Sort)

📌 알고리즘 설명

• 인접한 두 원소를 비교하여, 필요하면 자리를 바꿉니다.
• 한 번의 반복(iteration)으로 가장 큰 값이 맨 뒤로 이동합니다.
• 전체 배열이 정렬될 때까지 반복합니다.

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) { // 인접 원소 비교
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        // 결과 출력
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

2️⃣ 삽입 정렬 (Insertion Sort)

📌 알고리즘 설명

• 두 번째 원소부터 시작하여, 해당 원소를 정렬된 부분 배열의 올바른 위치에 삽입합니다.
• 데이터가 이미 정렬된 경우 매우 효율적입니다.

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};

        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;

            // key 값보다 큰 값들을 오른쪽으로 이동
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }

        // 결과 출력
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3️⃣ 선택 정렬 (Selection Sort)

• 배열에서 가장 작은 원소를 찾아 첫 번째 자리로 이동합니다.
• 나머지 배열에 대해 이 과정을 반복합니다.

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};

        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;

            for (int j = i + 1; j < arr.length; j++) {//i+1부터 끝까지 탐색
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // 최소값 인덱스 갱신
                }
            }

            // 최소값과 교환
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }

        // 결과 출력
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

4️⃣ 퀵 정렬 (Quick Sort)

📌 알고리즘 설명

• 피벗(pivot)을 기준으로 데이터를 두 부분으로 나누고, 각 부분을 정렬합니다.
• 재귀적으로 동작하며, 대부분의 경우 효율적입니다.
• 평균적으로 O(NlogN)의 시간 복잡도를 가집니다.
• 퀵 정렬은 재귀적 구조를 사용하므로 “분할 정복” 패턴을 학습하는데 유용합니다.
• Java의 Arrays.sort()는 Dual-Pivot Quick Sort를 기본으로 사용합니다. 코딩테스트에서 효율적인 라이브러리를 사용할 때 퀵 정렬 기반 알고리즘이 동작할 가능성이 큽니다.

📌 퀵 정렬의 동작

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        // 퀵 정렬 호출 (배열 전체를 정렬)
        quickSort(arr, 0, arr.length - 1);

        // 결과 출력
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
        // 퀵 정렬 메서드 (재귀적으로 배열을 정렬)
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
                 // 배열을 피벗을 기준으로 두 부분으로 나누고, 피벗의 위치 반환
            int pivotIndex = partition(arr, low, high);
              // 피벗 왼쪽 부분 정렬 (재귀 호출)
            quickSort(arr, low, pivotIndex - 1); 
            // 피벗 오른쪽 부분 정렬 (재귀 호출) 
            quickSort(arr, pivotIndex + 1, high);
        }
    }
        // 배열의 구간을 피벗을 기준으로 나누는 메서드
    public static int partition(int[] arr, int low, int high) {
            // 피벗 선택 (구간의 마지막 원소를 피벗으로 설정)
        int pivot = arr[high];
        // i는 피벗보다 작은 값을 저장할 위치를 추적
        int i = low - 1; //피벗보다 작은 값들을 저장할 마지막 위치를 가리키도록 한다.
                // low부터 high-1까지 반복하며 피벗과 비교
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
                // 피벗을 올바른 위치(i+1)로 이동
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }
}

5️⃣ 병합 정렬 (Merge Sort)

📌 알고리즘 설명

• 배열을 두 부분으로 나누고, 각각을 정렬한 후 병합합니다.
• 재귀적으로 동작하며, 항상 O(NlogN) 복잡도를 가집니다.

📌 병합정렬의 동작과정

📌 병합정렬의 동작

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        mergeSort(arr, 0, arr.length - 1);//mergeSort 함수를 호출하여 배열 전체를 정렬

        // 결과 출력
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2; //중간 지점 계산
            mergeSort(arr, left, mid); //왼쪽부분 정렬
            mergeSort(arr, mid + 1, right); //오른쪽부분 정렬
            merge(arr, left, mid, right); //정렬된 두 부분 정렬
        }
    }

        //병합 함수
    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; //임시 배열 생성
        int i = left //왼쪽 구간 시작 인덱스
        int j = mid + 1 //오른쪽 구간 시작 인덱스
        int k = 0; //k: temp 배열 인덱스

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++]; //왼쪽값 선택
            } else {
                temp[k++] = arr[j++]; //오른쪽값 선택
            }
        }
                //왼쪽구간에 남은 값 추가
        while (i <= mid) temp[k++] = arr[i++];
          //오른쪽구간에 남은 값 추가
        while (j <= right) temp[k++] = arr[j++];

                //병합된 결과를 원래 배열에 복사
        for (int t = 0; t < temp.length; t++) {
            arr[left + t] = temp[t];
        }
    }
}

오늘은 정렬의 종류에 대해 공부해보았습니다! 다음 포스팅에서는 병합정렬 문제풀이를 하며 같이 공부해보도록 합시다!

• 함수 내부에서 ‘자기 자신을 호출하는 함수’. 이를 통해 함수가 자신을 반복적으로 호출하면서 원하는 결과를 얻을수 있습니다.
• 단, 재귀 함수를 사용하는 경우 함수 호출이 계속해서 쌓이기 때문에 호출 스택이 받아져서 성능 저하가 될 수도 있음. 따라서 재귀함수를 작성할때에는 무한루프에 빠지지않도록 종료 조건을 명확히 설정해 줘야합니다.

💡호출스택이란?

• 프로그램에서 함수나 메서드를 호출할 때 해당 함수나 메서드의 실행이 끝날 때까지 실행되는 다른 함수나 메서드의 호출 정보를 저장하는 자료구조입니다.
• 이 스택은 함수가 호출될 때마다 그 함수의 호출 정보를 저장하고 함수의 실행 결과가 반환되면 해당 함수의 호출 정보를 스택에서 제거합니다.

⇒ 재귀 알고리즘은 문제를 해결하기 위해 재귀 함수를 사용하는 알고리즘을 의미합니다

재귀 함수를 활용한 예시

팩토리얼 계산방법

💡 팩토리얼 이란?

• 자연수 n에 대해서 1부터 n까지의 모든 자연수를 곱한 값을 의미합니다.
  • ex) factorial(5) = 5 * 4 * 3 * 2 * 1 = 120

코드

public class Main {
    public static void main(String[] args) {
        System.out.println(factorial(5)); // 5! = 5 * 4 * 3 * 2 * 1 = 120
    }

    public static int factorial(int n) {
        if (n == 0) { // 기본 케이스
            return 1;
        } else { // 재귀 케이스
            return n * factorial(n - 1);
        }
    }
}

N 자연수 합 계산 방법

• sumNatualNumber() 함수에 파라미터를 넘길 경우 재귀함수를 반복하여 결괏값을 반환해 주는 함수
  • ex) 5라는 파라미터를 넘겼경우 5+4+3+2+1 = 15 가 됩니다.
  • 그러므로 sumNatualNumber(5) 의 결괏값은 15입니다.

코드

public class Main {
    public static void main(String[] args) {
        System.out.println(sumNaturalNumber(5)); // 15
    }

    public static int sumNaturalNumber(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n + sumNaturalNumber(n - 1);
        }
    }
}

거듭제곱(pow) 계산

💡 거듭제곱(pow)이란?

• 하나의 숫자(밑)를 다른 숫자(지수)만큼 곱하는 것입니다.

  • 파라미터로 base 밑과 exponent 지수를 인자로 받아서 거듭제곱을 수행하는 함수입니다.

    파라미터로 2와 5를 넘겼으면 2의 5승인 32가 결괏값이 됩니다.

코드

public class Main {
    public static void main(String[] args) {
        System.out.println(power(2, 5)); // 15
    }

    public static int power(int base, int exponent) {
        if (exponent == 0) {
            return 1;
        } else {
            return base * power(base, exponent - 1);
        }
    }
}

• Math.pow()와 같은 결과값을 갖습니다.

문자열 뒤집기

💡reverseString() 함수를 통해 문자열의 값이 O가 되면 문자열을 반환하고 그렇지 않으면 첫번째 문자를 마지막 문자와 바꾸고 나머지 문자열에 대해 reverseString() 함수를 재귀적으로 호출한 결과를 반환합니다.

코드

public class Main {
    public static void main(String[] args) {
        System.out.println(reverseString("hello")); // "olleh"
    }

    public static String reverseString(String str) {
        if (str.length() == 0) {// Base Case: 문자열 길이가 0이면 그대로 반환
            return str;
        } else {
            return reverseString(str.substring(1)) + str.charAt(0);
        }
    }
}

• str.substring(1)은 문자열의 첫 번째 문자를 제외한 나머지 부분을 반환합니다.
• reverseString(str.substring(1))은 나머지 부분을 뒤집습니다.
• 뒤집힌 나머지 부분에 현재 문자열의 첫 번째 문자(str.charAt(0))를 덧붙입니다.

재귀함수를 이용한 알고리즘: 피보나치 수열, 유클리드 호제법, 이진탐색 이항 계수

피보나치 수열(Fibonacci sequence) : 경우의 수 계산

💡 피보나치 수열이란?

• 이전 두항의 합이 다음 항의 수열을 의미합니다. 즉, 첫째항과 둘째항이 1 이고 이후 모든 항은 바로 앞으로 두항의 합으로 이루어지는 수열을 의미합니다.
• 피보나치 수열의 예로 [1, 1, 2, 3, 5, 8, 13, 21, 34,...]과 같은 형태로 구성이 됩니다.

코드

public static int fibonacci(int n) {
    if (n == 0) {
        return 0; // Base Case 1: n이 0이면 0 반환
    } else if (n == 1) {
        return 1; // Base Case 2: n이 1이면 1 반환
    } else {
        return fibonacci(n-1) + fibonacci(n-2); // Recursive Case: 이전 두 항의 합
    }
}

1. 기본 조건 (Base Case):
   • 재귀 호출을 멈추는 조건입니다.
   • 입력값 n이 0이면 0을 반환, n이 1이면 1을 반환합니다.
2. 재귀 호출 (Recursive Case):
   • fibonacci(n-1)과 fibonacci(n-2)를 호출하여 두 값을 더한 결과를 반환합니다.
   • 이는 피보나치 수열의 정의에 따라 이전 두 항의 합을 계산하는 방식입니다.

개선방법

• 중복 계산을 줄이기 위해 메모이제이션(Memoization) 또는 동적 계획법(Dynamic Programming)을 사용하여 효율적으로 계산할 수 있습니다.

코드(메모이제이션 적용 코드)

public class Main {
    private static int[] memo;

    public static void main(String[] args) {
        int n = 5;
        memo = new int[n + 1]; //크기가 n+1인 배열 memo 생성
        System.out.println(fibonacci(n)); // 5
    }

    public static int fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (memo[n] != 0) return memo[n]; // 이미 계산된 값 반환
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2); // 계산 후 저장
        return memo[n];
    }
}

• 메모이제이션을 통해 기본 재귀 함수의 중복 호출 문제를 해결하여 실행 속도가 크게 향상됩니다

기본 재귀 함수의 문제점

기본 재귀 함수는 중복된 계산이 많습니다. 예를 들어, fibonacci(5)를 계산할 때:

• fibonacci(4)와 fibonacci(3)을 계산합니다.
• fibonacci(4)는 다시 fibonacci(3)과 fibonacci(2)를 계산합니다.
• fibonacci(3)는 또 fibonacci(2)와 fibonacci(1)을 계산합니다.

결과적으로 같은 값(fibonacci(3) 등)을 여러 번 계산하게 됩니다. 이러한 중복 호출 때문에 시간 복잡도가 O(2^n)로 매우 비효율적입니다.

메모이제이션의 개선

메모이제이션은 이미 계산한 값을 저장하여 중복 계산을 방지합니다.

작동 방식

1. 저장소 배열(memo) 준비:
   • 크기가 n + 1인 배열 memo를 생성합니다.
   • 배열은 피보나치 수열의 값을 저장합니다.
   • 예: memo[5]에는 fibonacci(5)의 값이 저장됩니다.
2. 값을 저장하고 재사용:
   • 피보나치 값을 계산하면 memo[n]에 저장합니다.
   • 이후 동일한 값이 필요할 때, 이미 저장된 값을 바로 반환합니다.

중복 호출 방지

• 계산된 값은 memo 배열에 저장되므로, 동일한 값에 대해 재계산하지 않습니다.
• 예를 들어, fibonacci(3)은 처음 계산 후 memo[3]에 저장되며, 이후 호출 시 바로 반환합니다.

시간 복잡도

• 각 fibonacci(n)은 최대 한 번만 계산됩니다.
• 배열 접근(memo[n])은 O(1)의 시간 복잡도를 가집니다.
• 전체 시간 복잡도는 O(n)으로 대폭 개선됩니다.

공간 복잡도

• memo 배열을 저장하기 위한 O(n)의 추가 공간이 필요합니다.

유클리드 호제법(Euclidean Algorithm) : 최대 공약수 계산

💡 유클리드 호제법/알고리즘이란?

• 두수의 최대공약수(GDC)를 찾기 위한 알고리즘입니다.
• 큰수를 작은수로 떨어지게 하여 수를 반복적으로 취하여 나머지가 0이 될때까지 작동하는 방법을 의미합니다. 그때 작은수가 최대공약수입니다.
  • 최대공약수(GCD)란?
    • 최대공약수는 두 정수의 공통된 약수 중 가장 큰 수를 의미합니다. 예를 들어:
    • m = 48, n = 18일 때, 공약수는 1, 2, 3, 6이며, 최대공약수는 6입니다.

코드

public static int gcd(int m, int n) {
    if (n == 0) {
        return m;
    } else {
        return gcd(n, m % n);
    }
}

• 두 수 m과 n의 최대공약수는 n과 m % n의 최대공약수와 같습니다.
  • 예: gcd(48, 18) = gcd(18, 48 % 18) = gcd(18, 12)
• 나머지가 0이 될 때, 나누는 수가 최대공약수입니다.

알고리즘의 단계

1. 나머지 r = m % n을 계산합니다.
2. gcd(n, r)을 재귀적으로 호출합니다.
3. n == 0이 되면, m이 최대공약수입니다.

이진탐색(Binary Search) 알고리즘

💡 이진 탐색(Binary Search) 알고리즘이란?

• 정렬된 배열에서 원하는 데이터를 빠르게 찾기위한 알고리즘입니다.

이진탐색 알고리즘의 알고리즘 순서

1. 초기조건 확인
   • 배열이 정렬되어 있는지 확인해야 합니다. 이진 탐색은 정렬된 배열에서만 작동합니다.
   • 탐색 범위의 시작점 low와 끝점 high를 설정합니다.
2. 중간값 계산
   • 현재 탐색 범위의 중간 인덱스 mid를 계산합니다. (low+high)//2
3. 중간값 비교
   • 배열의 중간값 arr[mid]과 찾으려는 값 target 비교
     • Case 1: arr[mid] == target
       • 값을 찾은경우 인덱스 mid를 반환
     • Case2: arr[mid] < target
       • 찾으려는 값이 더 크므로, 왼쪽 절반을 버리고 오른쪽 절반만 탐색합니다. 즉, low는 mid + 1 로 바꿈
     • Case3: arr[mid] > target
       • 찾으려는 값이 더 작으므로, 오른쪽 절반을 버리고 왼쪽 절반만 탐색합니다. 즉, high는 mid -1 로 바꿈
4. 반복
   • 위 과정을 low ≤ high 될때까지 반복합니다.
5. 결과 반환
   • 값을 찾으면 해당 인덱스를 반환합니다
   • 탐색 범위가 끝나고도 값을 찾지 못하면, -1 (또는 값이 없음을 나타내는 특수 값)을 반환합니다.

코드

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // 중간 인덱스 계산
            if (arr[mid] == target) {
                return mid; // 값을 찾음
            } else if (arr[mid] < target) {
                low = mid + 1; // 오른쪽 절반 탐색
            } else {
                high = mid - 1; // 왼쪽 절반 탐색
            }
        }

        return -1; // 값이 없는 경우
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 7, 10, 14, 18, 21};
        int target = 14;

        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("값 " + target + "는 인덱스 " + result + "에 있습니다.");
        } else {
            System.out.println("값 " + target + "는 배열에 없습니다.");
        }
    }
}

이항계수(Binomial theroem) 알고리즘

💡 이항계수(binomial theorem) 알고리즘이란?

• 조합론에서 사용되며, n개의 서로 다른 원소에서 r개의 원소를 선택하는 경우의 수를 의미합니다.
• 이항 계수 C(n,k)는 n개의 항 중에서 k개를 선택하는 경우의 수를 의미합니다.
• 예를 들어, C(5,2)는 5개의 항 중 2개를 선택하는 경우의 수를 의미하며, 값은 10입니다.

코드

public static int binomialCoefficient(int n, int k) {
    if (k == 0 || k == n) {
        return 1;
    } else {
        return binomialCoefficient(n-1, k-1) + binomialCoefficient(n-1, k);
    }
}

binomialCoefficient(n-1, k-1) + binomialCoefficient(n-1, k)의 의미?

오늘은 재귀 알고리즘에 대해 공부를 해보았습니다. 다음에는 백트래킹 알로리즘에 대한 글로 찾아뵙겠습니다!

개발자의 알고리즘과 자료구조에대해 정확히 알고있는지 확인하고 그 문제해결 능력을 확인하기위해 채용과정에서 사용되는 시험방법

평가요소

• 기술 역량 : 프로그래밍 문법, 알고리즘, 자료구조 등을 평가함
• 문제 해결 능력 : 주어진 제시문을 잘 이해해서 문제를 어떻게 분석하여 어떤 해결책을 찾아 내는지 확인함
• 코드 구현 능력 : 이를 어떻게 코드로 구현하는지 파악함 (스타일 가이드, 주석 등 코드를 통한 협업을 얼마나 잘하는지도 평가함)

알고리즘 학습방법

• 자료구조
  • Array/List
  • Linked List
  • Stack
  • Quene
  • Dequene
  • Priority quene
  • Hash Table
  • Tree
  • Graph
  • Heap
• 알고리즘
  • Simulation/Implementation
  • Search
  • Sort
  • Greedy
  • Dynamic programming
  • Dijkstra
  • Floyd-Warshall
  • Prim
  • Kruscal
  • DFS
  • BFS

시간복잡도와 공간복잡도

시간복잡도

• 알고리즘을 프로그램으로 실행해 완료하는데까지 걸리는 시간
• 시간복잡도 = 프로그램 컴파일 시간 + 실행시간
  • 컴파일 시간 → 고려 안해도 됨
  • 실행시간에 따라 컴퓨터의 성능이 달라질수 있으므로 명령문의 실행빈도수를 계산해 추정

분석 방법

• 입력크기 n에 대한 실행시간의 증가율만 분석하는 점근적 분석(Asymptotic Analysis)을 활용
  • 증가율만 보기에 실행 빈도 함수의 상수항과 계수 무시하고 가장 큰 하나의 항에 대해서 차수 표기법(Order Notation)으로 시간 복잡도를 표기
  • 무시하는 이유 : 정확한 연산의 개수를 알고 싶은게 아니라 input n에 따른 증가 추세가 궁금하기 때문에 n이 커질수록 상수항과 계수의 영향력은 미미해진다

공간복잡도

• 프로그램의 실행에서 완료까지 얼마나 많은 공간(가변 공간)가 필요한지
• 총 필요 공간= 고정공간 + 가변공간
  • 고정공간
    • 입출력 횟수, 크기와 관계없이 동일함(코드 저장 공간, 단순 변수, 상수 등)
    • int, double, 크기가 정해진 배열
    • 상수 → 성능에 큰 영향을 안준다
  • 가변공간
    • 필요에 따라 동적으로 할당, 해제되는 메모리공간
    • 특정 instance에 따라서 사이즈가 달라지는 변수
    • 성능에 큰 영향을 미친다
• 통상적으로 시간복잡도와 공간복잡도는 반비례 관계에 있음
  • 최근에 하드웨어가 대용량으로 나오기 때문에 공간복잡도 < 시간복잡도

빅오 표기법(Big-O Notation)

• 실행 빈도 함수의 상한을 나타내기 위한 표기법
• 최악의 경우에도 g(n)의 수행시간 안에는 알고리즘 수행되어야함
• 일반적으로 최악의 경우를 고려한 해결책을 찾기에 Big-O를 주로 사용한다
• O(1): Hash Table에서의 검색/삽입.
• O(log N): 이진 탐색(Binary Search).
• O(N): 단순 배열 순회.
• O(N log N): 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort) 평균.
• O(N²): 중첩 반복문을 사용하는 경우.
• O(2^N): 재귀를 활용한 피보나치 수열 계산.
• O(N!): 순열(모든 경우의 수 탐색) 계산.

시간 복잡도를 기반으로 코딩 테스트에서 효율적인 풀이를 설계하는 방법

1. 문제 크기(N)를 분석하여 요구되는 시간 복잡도 범위를 추정.
   • N ≤ 1,000,000인 경우: O(N log N) 이하 필요.
   • N ≤ 1,000인 경우: O(N²)까지 가능.
2. 알고리즘 선택 기준
   • N의 크기에 따라 완전 탐색, 이분 탐색, 동적 프로그래밍 등 선택.
3. 최적화
   • 중복 계산 제거, 캐싱 사용 등.

예시) 시간 복잡도를 고려하지 않았을 경우의 문제

풀이 1: 시간 복잡도를 고려하지 않은 완전 탐색 (Brute Force)

import java.util.*;

public class TwoSumBruteForce {
    public static int[] findPair(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{nums[i], nums[j]};
                }
            }
        }
        return new int[]{}; // No pair found
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 7, 5, 4};
        int target = 9;
        int[] result = findPair(nums, target);

        System.out.println(Arrays.toString(result));
    }
}

외부루프(i): O(N)

내부루프(j): O(N)

총 시간 복잡도: O(N²)

문제점

• 답은 도출되지만 입력의 크기가 커지기 때문에 실행시간도 늘어남→ 시간복잡도에 걸려 실패

❓How resolve this problem?

→ HashMap을 사용해 시간복잡도를 최소화 한다.

import java.util.*;

public class TwoSumOptimized {
    public static int[] findPair(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();// hashMap을 이용하여 현재숫자 저장
                //<현재까지 탐색한 숫자, 해당 숫자가 존재한다는 표시>

        for (int num : nums) { //배열 nums의 첫 번째 원소부터 마지막 원소까지를 순서대로 탐색
            int complement = target - num; //목표값에서 현재숫자를 뺌 ex) 9-1=8
            if (seen.containsKey(complement)) { //seen에 complement가 존재하는지 확인
                return new int[]{complement, num}; //존재 하면 새로운 int 배열에 반환!
            }
            seen.put(num, 1); //해당 숫자(num)가 존재
        }
        return new int[]{}; // 조건을 만족하는 쌍이 없을 때 빈 배열 반환
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 7, 5, 4};
        int target = 9;
        int[] result = findPair(nums, target);

        System.out.println(Arrays.toString(result));
    }
}

단일루프: O(N)

Hash Map 조회와 삽입: O(1)

총 시간 복잡도: O(N)

⇒ 결론: 답이 도출되어도 시간 복잡도에 따라서 실행시간 더 짧게 걸린다면 훨씬 더 메리트 있는 정답이다.

Java: 코딩테스트에서 자주 쓰이는 method

라이브러리

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

변수선언

String[] arr1 = new String[5];
int[] arr2 = {1,2,3};
int N=3
int[] arr3 = new int[N];

Arrays

int arr[]= {10,8,11,2,3,0}

//오름차순 {0,2,3,8,10,11}
Arrays.sort(arr1);

//내림차순
Arrays.sort(arr1, Collections.reverseOrder());

//일부만 정렬 {2,8,10,11,3,0}
Arrays.sort(arr1,0,4);

// 4. 오름차순 정렬하면 binary search로 특정 값을 찾을 수 있다.
Arrays.binarySearch(arr1, 2);

// 5. 배열을 어레이리스트로 변환!
List list = Arrays.asList(arr1);

// 6. 배열의 특정 범위 자르기
int tmp[] = Arrays.copyOfRange(arr1, 0, 3);

length/length()/size()

• length: 배열의 길이
• length(): String related object(str.length())
• size(): Collections object

// 1. length
int[] arr = new arr[3];
System.out.println(arr.length);

// 2. length()
String str = "java";
System.out.println(str.length());

// 3. size()
ArrayList<Integer> list = new ArrayList<>();
System.out.println(list.size());

String

String str = "hello world";

//길이 반환
str.length();

//빈문자열 체크
str.isEmpty();

//문자 찾기
str.charAt(0);  // 'h' -> 문자 반환
str.indexOf("e"); //1 -> 인덱스 반환
str.lastIndexOf("r"); // 8->마지막으로 문자가 속한 인덱스 반환

// 문자 자르기
str.substring(0, 5);  //인덱스 0 이상 5미만 위치의 문자열 반환
str.substring(3); //인덱스 3 이상 위치의 문자열 반환

for(int i = 0; i < str.length(); i++) str.charAt(i);

//문자 치환(바꾸기)
//replace([기존문자],[바꿀문자]) 
str.replace('e','o'); // 모든 [기존문자]를 [바꿀문자]로 치환

//문자 반복
str.repeat(k) //k번 반복

//문자 포함 여부 판단
str.contains("hell");

//문자열을 배열로 만들고 싶을 때
String str = "12345";
String[] Arr = str.split("");
char[] cRsp = str.toCharArray();

// 대소문자 변경
str = str.toUpperCase();        // HELLO WORLD
str = str.toLowerCase();        // hello world

StringBuilder

StringBuilder sb = new StringBuilder();

sb.append("A"); //문자열 추가하기
sb.insert(1,"B"); //중간에 문자열 삽입하기
sb.delete(0,1); //문자열 삭제하기(~부터 ~까지)
sb.reverse(); // 문자열 뒤집기
sb.toString(); // 문자열 변환

String str = sb.append("A").append("B").append("C").append("D")
            .insert(4,"Java").delete(4,8).reverse().toString();  //메소드 체이닝

HashMap

HashMap<String,Integer> = new HashMap<>();// HashMap 선언

// key-value 넣기
hm.put("java",0);

//key로 값 가져오기
hm.get("java");

//containsKey()로 존재유무 확인
if(!hm.containsKey("java")){
    hm.put("java",1)
}

// keySet() 함수로 맵 순회
for(String key : hm.KeySet()) {                
    hm.get(key);
}

ArrayList

// 선언
ArrayList<String> list = new ArrayList<>();

// 삽입
list.add("java");            // {"java"}
list.add(0, "python");            // {"python", "java"} (0번째 인덱스에 삽입)

// 수정
list.set(1, "kotlin");            // {"python", "kotlin"}

// 삭제
list.remove(1);                // {"python"}

// 가져오기
list.get(1);

// 값 존재 유무 확인
list.contains("java");        // false
list.indexOf("python");        // 0 존재하면 인덱스 리턴

// 리스트 길이
list.size();

//리스트에 다른 리스트 요소가 전부 포함되어 있는지 여부 체크
list.containsAll(list2);

//문자열 타입 배열을 list로 변환
String[] temp = {"apple","banana","lemon"};
List<String> list = new ArrayList<>(Arrays.asList(temp));

//list를 문자열 배열로 변환
List<String> list = new ArrayList<>();
String[] temp = list.toArray(new String[list.size()]);

Collections 관련 메서드

int[] temp = {1,2,3,10,20};
List<Integer> list = new ArrayList<>(Arrays.asList(arr));

//정수형 list 원소 중 최대, 최소값
Collections.max(list);
COllections.min(list);

//List 정렬
Collections.sort(list);    //오름차순(ASC)
Collections.sort(list, Collections.reverseOrder()); //내림차순 (DESC)

//List 뒤집기
Collections.reverse(list);

Math 라이브러리

// 1. 최대 최소
Math.max(10, 2);
Math.min(10, 2);

// 2. 절대값
Math.abs();

// 3. 올림 내림 반올림
Math.ceil(-3.2);        // -3
Math.floor(-3.2);        // -4
Math.round(-3.26);        // -3    첫째자리에서 반올림

// 3-1. 소수 둘째, 셋째 자리에서 반올림 하고 싶다면
double a = 1.23456;
String b = String.format("%.1f", a);    // .1f는 둘째자리에서 반올림

// 4. 제곱 제곱근
Math.pow(2, 2);        // 2^2 = 4
Math.sqrt(4);        // 2