💡 조회 성능 개선을 위한 Redis와 Redis Sentinel 적용기

1. 개요

이전 프로젝트를 진행하면서, 조회 성능 개선을 위해 Redis 캐싱을 사용해 본 적이 있었고, 큰 성능 향상을 체감하였다. 하지만, 당시 마감기한에 의해 시간적 여유가 부족했기 때문에, 이번 기회에 Redis에 대해서 더욱 자세히 알아보고, 추가적으로 Redis sentinel을 통한 장애 대응 및 모니터링 시스템도 구현해볼 생각이다.

2. Redis 캐싱 전 Test

실시간 채팅 메시지인 만큼 Outbox에 많은 Event들이 쌓일 것이고, ChatMessage와 Outbox 중에서 ChatMessage는 메시지 만의 고유 특성을 유지하기 위해서, Outbox에 idempotency Key(멱등성 키)를 넣어서, 조회를 통해 중복 메시지 발생을 유지한다.

1) 테스트 환경

Outbox 개수: 50 Number of Threads (users) : 3000 Ramp-up period (seconds): 10 Loop Count: 5

2) 테스트 결과

Average(평균 응답시간): 794ms(0.8초) Throughput(처리량): 1262req/sec

위 기준으로 Jmeter를 통해 조회 성능을 체크해본 결과 위 와 같은 결과가 발생하였다. 대규모 트래픽을 예상해서, 스레스 수를 3000으로 잡다보니, 처리량은 괜팒지만 평균 응답속도가 0.8초 만큼의 측정되며 버벅임을 피할 수 없었다.

이로 인해, 대용량 트래픽이 예상되므로, Redis 캐싱을 사용한 조회 성능과 비교해보려고 한다.

3. Local Cache vs Global Cache

1. Local Cache

• 애플리케이션 서버 로컬에 캐시 저장소를 두고 데이터 처리
• 로컬 Cache로 접근 ( 데이터 조회 속도 증가 )
• 애플리케이션 서버 Scale-out시 ( 데이터 정합성 X ) => 데이터 전파 필요

2. Global Cache

• Cache 서버 별도로 존재 ( 각 애플리케이션에서 접근 )
• Cache 서버로 접근 ( 데이터 조회 속도 감소 )
• 애플리케이션 서버 Scale-out => 공통된 캐시 저장소 사용 ( 데이터 정합성 OK)

우리 프로젝트는 MSA 기반 서비스일 뿐 아니라, 여러 서버에서 Redis를 사용하고, Redis Sentinel을 통해 모니터링과 장애 대응을 진행할 것이기 때문에 특성상, Global Cache를 사용햇다.

4. Redis Cache 적용

1) 고려사항

Redis Cache를 적용하기 전에, 생각해야하는 고려사항이 존재했다. 단순한 접근이 아니라, 운영적인 측면에서도 고민을 했다.

우선,Redis는 Docker에 띄워 외부DB와 비슷한 형태로 사용될 것이기 때문에 Redis와의 통신 중 네트워크 장애나 다른 장애들에 의해서 행위가 유실될 수 있다는 문제가 존재한다. 이는 결국 "원자성"을 위협하는 문제로 이어진다.

따라서, 단순히 Redis를 이용해서 캐싱을 적용하는 것 뿐 아니라, 운영적인 측면에서 장애를 대처해야 하며, 원자성을 유지하는 방식은 2가지가 존재한다.

1) Lua Script를 사용해서 다양한 Redis 명령어를 하나의 스크립트로 묶어 하나의 >트랜잭션 처리로 원자성을 보존 2) Redis Cache에서 1차적으로 원자성 처리(ex. AOF, RDB) + Outbox 테이블의 >Unique 처리를 통해 2차적으로 원자성 처리

위 방식 중, 우리 서비스의 실시간 채팅에서는 outbox에 저장되는 이벤트의 멱등성 키 중복 처리만 필요했기 때문에 1번을 사용하게 되었다.

2) Redis Cache 원자성 처리 고려사항

실제로 Redis Cahce의 원자성 처리를 고려하여 여러가지 방식이 존재하였다. 내가 고민했던 방식은 3가지 였고, 현재 Redis Sentinel을 통해 failover 처리가 되어있으므로 해당 사항도 고려 사항에 포함시켜서 고민하였다.

1) 모든 노드(Master,Slave) AOF 적용, 2) Master에만 AOF(AOF‑only) 적용 3) AOF+RDB 혼용(Hybrid) 방식

음.. 하지만 찾아보고 공부할수록, AOF나 RDB를 통해서 따로 백업해둔다는게 결국 실시간 채팅 서비스에서 단순 멱등성 키 중복조회를 위한 캐시로 사용할 것이 때문에 너무 오버엔지니어링이라고 생각했다. 하지만 더욱 깊이 바라볼 수 있는 시간이였고, 향후 필요에 의해 다시 적용해볼 생각이다.

3) Redis 적용

5. Docker로 Redis와 Redis Sentinel 띄우기

현재 프로젝트에서는 MSA 기반 서비스를 구성하고 있기 때문에, Redis와 Redis Sentinel 모두 Docker Compose를 통해 서버를 띄워서 사용했다.

1) Docker-Compose.yml 설정

  # Redis & Redis Sentinel 설정
  redis-master:
    image: redis:latest
    command: redis-server
    container_name: "redis-master"
    networks:
      - infra

  redis-slave-1:
    image: redis:latest
    command: redis-server --slaveof redis-master 6379
    links:
      - redis-master
    container_name: "redis-slave1"
    networks:
      - infra

  redis-slave-2:
    image: redis:latest
    command: redis-server --slaveof redis-master 6379
    links:
      - redis-master
    container_name: "redis-slave2"
    networks:
      - infra

  sentinel-1:
    build: sentinel
    ports:
      - "5003:26379"
    env_file:
      - .env
    depends_on:
      - redis-master
      - redis-slave-1
      - redis-slave-2
    container_name: "sentinel1"
    networks:
      - infra

  sentinel-2:
    build: sentinel
    ports:
      - "5004:26379"
    env_file:
      - .env
    depends_on:
      - redis-master
      - redis-slave-1
      - redis-slave-2
    container_name: "sentinel2"
    networks:
      - infra

  sentinel-3:
    build: sentinel
    ports:
      - "5005:26379"
    env_file:
      - .env
    depends_on:
      - redis-master
      - redis-slave-1
      - redis-slave-2
    container_name: "sentinel3"
    networks:
      - infra

docker-compose.yml파일에 위 설정을 추가해서 진행하였으며, Redis의 장애 사항 대응을 위해 Master 1개, Slave 2개로 설정하여 장애 상항을 대비하였다. ( 기존 Master가 장애로 down 되면, 투표에 걸쳐 Slave 1개가 Master로 승격 ) 추가적으로 Sentinel은 홀수 개(예: 3개)로 구성하여, 과반수 투표(Quorum) 기준인 2를 만족시킬 수 있도록 설계하였다.

2) 추가 conf 파일 설정 (이미지로 적용되어서 빌드됨)

Dockefile

Dockerfile 설정에서는 Sentinel 실행에 필요한 sentinel.conf파일을 이동시키고, 권한 부여 및 entrypoint 파일도 실행시킨다. entrypoint 명령어를 통해 Sentinel이 빌드되고, 컨테이너 동작후 entrypoint 파일이 실행된다.

sentinel-entrypoint.sh

entrypoint 파일에서는 Sentinel 설정을 적용 및 실행

sentinel.conf

Sentinel 실행에 필요한 설정 파일이다. 핵심 부분은 sentinel resolve-hostnames yes를 설정해줘야 sentinel monitor 명령어에서 redis-master를 찾을 수 있다. (설정하지 않으면.. 연결 안됨🥲)

3) Master/Slave/Sentinel 설정 확인

1. redis-master(Master) replication 설정 확인

# redis-master 실행
$ docker exec -it redis-master redis-cli -p 6379

# replication 설정 확인
$ info replication

Master 노드를 통해 replication 정보를 조회해보면, Slave 노드로 설정한 2개의 주소가 조회되는 것을 보아 잘 적용된 것으로 보인다. 추가적으로, master-failover_state: no-failover 설정을 통해 sentinel을 통해 잘 모니터링 되고 있음을 의미한다.

2. Sentinel을 통한 master, slave와 sentinel 개수 및 설정 확인 사진을 통해 보이는 것 처럼, Redis Sentinel도 총 3개 설정되어있고, Master 노드와 Slave 갯수를 잘 가르키고 있어 잘 설정된 것을 확인할 수 있다.

4) Redis Sentinel 장애 감지 및 failover 처리 확인

장애 사항시 Redis Sentinel이 잘 모니터링하고 있고 장애를 즉시 감지하는지 / failover를 처리하여 서비스 중단 없이 Slave를 Master로 승격 시키는지를 확인하기 위해서, 실행 중인 Master 노드를 중단하고 확인해 볼 생각이다.

1. redis-master 중단 전/후 Sentinel log 비교

<Master Redis 중단 전>

<Master Redis 중단 후>

위의 중단 전/후를 비교해보면, Master 노드인 redis-master가 중단되는 순간 failover 처리를 하는 것을 볼 수 있다

1. Sentinel이 모니터링 중, redis-Master의 장애를 판별 (주관적 장애 감지)
2. 다른 Sentinel들도 모니터링 후, 투표하여 장애 정확히 판별 (객관적 장애 감지)
3. Failover 시작 (Slave 중 1개 Master 로 승격)
4. 승격 대상 Slave 선택
5. 선택된 Slave를 Master 노드로 전환 완료

위 과정을 통해, 중단 없이 Slave가 Master로 승격되어 중단없이 진행되는 것을 확인하였고, Sentinel이 빠르게 장애를 판단하여 처리하는 것을 확인할 수 있었다.

2. Master/Slave 노드 변경 확인

<Master Redis 중단 전>

<Master Redis 중단 후>

위를 비교해보면, 실제 Master 노드인 redis-master가 중단되고 나면, 투표를 거쳐 redis-slave1과 redis-slave2 중에 하나가 Master 노드로 승격하는 것을 확인 할 수 있다. 또한, redis-master도 다시 재 실행하면, Slave로 편입되어 지는 것을 볼 수 있다.(다시 Master로 돌아가지는 X)

이로써 Docker-compose를 통해 Redis와 Redis Sentinel을 모두 띄워서, 설정 확인과 failover 처리까지 모두 완성되었다. (+ 향후 Sentinel에서 문제 발생시 알림 보내주는 기능 추가 예정)

참고 블로그 https://coding-review.tistory.com/533

💡 코딩 테스트 준비를 위한 문제를 풀면서, 신기하고 유용한 메소드를 정리해보자

1. bit_length

n = -37
bin(n) # -0b100101
n.bit_length() # 6

부호와 선행 0을 제외하고, 이진수로 정수를 나타내는 데 필요한 비트 수를 돌려줍니다: x 가 0이 아니면, x.bit_length() 는 2^(k-1) <= abs(x) < 2^k 를 만족하는 유일한 양의 정수 k 입니다. 동등하게, abs(x) 가 정확하게 반올림된 로그값을 가질 만큼 아주 작으면, k = 1 + int(log(abs(x), 2)) 가 됩니다. x 가 0이면, x.bit_length() 는 0 을 돌려줍니다.

2. bit_count

n = 19
bin(n) # 0b10011
n.bit_count() # 3

정수 절대값의 이진 표현에서 1의 총 개수를 반환

3. map()

citations = [9,6,5,1]
answer = max(map(min, enumerate(citations, start=1)))

map함수는 기존 자료형을 바꾸는 용도로만 사용했는데, 위와 같이도 사용이 가능하다.

1. enumerate(citations, start =1) start=1 옵션을 줘서, 시작 index를 1로 설정해서 index와 value 도출
2. map(min,enumerate(citations, start=1)) map을 통해서 분류할 기준을 min으로 잡을 수 있다. 그럼 (index,value) 중 작은 값만 도출

4. zip()

def solution(progresses, speeds):
    Q=[]
    for p, s in zip(progresses, speeds):
        if len(Q)==0 or Q[-1][0]<-((p-100)//s):
            Q.append([-((p-100)//s),1])
        else:
            Q[-1][1]+=1
    return [q[1] for q in Q]

zip()는 반복하며, 넣은 2가지 배열의 원소를 하나씩 가져와서 넣어주는 메소드이다. ( 단 길이가 다르다면 작은쪽에 맞춰짐 ) ex) progresses = [0,1,2] / sppeds = [A,B] => [0,A], [1,B] +) 추가적으로 math.ceil 방식을 사용하지 않고, 올림을 하는 방법이 제시되었다.

** 음수로 만들어서 나누기를 하면 자동으로 내림이 되는 것을 이용해서 올림 사용** ex) -3 // 2 = -2 ( 내림이 됨) => 3//2 올림 구하고 싶으면 -(-3//2)로 구하면 올림이 가능하다 👍🏻

5. reduce()

def solution(clothes):
    from collections import Counter
    from functools import reduce
    cnt = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
    return answer

reduce 메소드는 lambda를 사용해서, 함수를 계산해주는 메소드이다. reduce(function, iterable, 초기값)으로 선언된다.

reduce(lambda x, y: x*(y+1), cnt.values(), 1) -1 이 경우에는 x의 초기값은 1 ( 곱셈의 경우는 1, 덧셈의 경우는 0) y는 cnt.values()가 돌면서 하나씩 들어감 x*(y+1)의 결과값은 x에 들어감

6. any()

def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer             

any 메소드는 iterable 객체 안에 값이 하나라도 True에 해당하는 값이 있으면 True, 없으면 False를 반환한다. 따라서 위와 같은 경우, queue를 전체 순회하면서 cur[1] < q[1]이면, 즉, 현재 값보다 큰 값이 존재하면, append를 해준다.

7. max()

pro = [(1,1), (5,2), (3,3)]
max_pro = max(pro, key=lambda x: x[1]) # (3,3)
max_pro = max(pro) # (5,2)

max 메소드 역시, key를 통해서 최댓값을 판단하는 기준을 지정할 수 있다. 위 코드를 참고하면, pro가 [(a,b)]로 되어있을때, 기존 max(pro)는 a를 기준으로 최댓값을 찾는다. 따라서 , key=lambda x: x[1]로 설정해주면 b를 기준으로 최댓값을 찾을 수 있다.

8. divmod()

x, n = 14, 3
q, r = divmod(x, n)    # (4,2)

divmod(a,b) 메소드는 a // b, a % b 값을 모두 반환해주며, (a // b, a % b)의 형태로 반환해준다. 실제로 진수를 계산할 경우, 직접 q = x//n와 같은 방식 없이 위 같은 방식을 많이 사용하기 때문에 알아두도록 하자!!

💡 MongoDB에 @Transactional을 적용하기 위해 replica-set을 설정해보자!!'

1. 문제상황

위와 같이 Kafka에 Outbox 패턴을 적용하기 위해서는 하나의 트랜잭션 내부에서 메시지 내용도 ChatMessage에 저장하고, Outbox도 저장해야한다.

위 코드로 진행하다 보니 하나의 트랜잭션 내부에서 chatMessageRepository에서의 save와 outboxRepository의 save를 통해 "다중 도큐먼트 트랜잭션"이 발생하여 위와 같은 오류가 발생하였다.

💡 단일 노드의 MongoDB에서는 다중 도큐먼트 트랜잭션을 처리할 수 없다.(replica-set 설정 필요)

2. 해결방법

1) 기존 DB 데이터 백업 (for migration)

# 기존 DB를 백업한 dump 생성
$ mongodump --db=snail --out=./dump

기존에는 Local 환경에서 snail 이라는 데이터 베이스를 사용했기 때문에 이를 migration 하기 위해서 해당 데이터를 dump 파일로 백업을 진행한다.

2) docker-compose를 통한 replica-set 환경 구성

docker-compose.yml 파일 생성

# docker-compose.yml 파일 수정 (해당 파일이 존재하는 경로에서 실행)
$ sudo vim docker-compose.yml 

위와 같이 일단 MongoDB replica-set 설정을 위해서 docker-compose.yml 파일에 추가 설정을 해준다. 운영 환경 차원에서 Replica-set은 "홀수개"로 설정하는 것이 바람직 하기에, 총 3개를 선언하였다.

replica-set 인증에 사용될 mongodb.key 권한 설정

# mongodb 키 생성 ( MAC M1 기준 )
sudo openssl rand -base64 756 | sudo tee /Users/hyeok/.ssh/mongodb.key > 
/dev/null


# 권한 설정
sudo chmod 400 ~/.ssh/mongodb.key

replica-set 인증에 필요한 key 권한을 설정해준다.

docker-compose 백그라운드 환경에 실핼 및 확인

# 백그라운드 환경에 docker-compose 실헹
$ docker compose up -d

# 현재 docker에 띄워져 있는 컨테이너 확인
$ docker ps -a

docker compose를 통해 mongoDB replica-set을 띄워진 것을 확인할 수 있다.

3) Replica-set 설정

docker 환경 접속 후 replica 설정 지정

# docker container 접속
docker exec -it mongo1 /bin/bash

# bockerl 계정 몽고 쉘 접속 (root 계정)
mongosh -u bockerl -p bockerl

# admin 데이터 베이스 사용
use admin

# replication 초기화
rs.initiate()

# mongo2 복제세트 추가
rs.add({_id: 1, host: "mongo2:27017"})

# mongo3 복제세트 추가
rs.add({_id: 2, host: "mongo3:27017"})

위 과정을 따라서 진행하면, 컨테이너 내부에 들어가 replica-set 설정을 위해 mongo2 복제 세트 설정을 추가해준다.

replica-set 설정 확인

$ rs.config()
$ rs.status()

설정 후, 위 메소드를 사용해서 상태를 확인해보면, replica-set이 잘 설정되었으면, mongo1은 primary로 mongo2는 secondary로 잘 설정된 것을 확인할 수 있다.

4) 데이터베이스 마이그레이션 적용

local에 저장되어 있는 dump 파일을 컨테이너에 옮기기

<실패 과정>

# docker-compose.yml 파일이 존재하는 곳에서 실행
docker exec -it mongo1 mongorestore \
  -u bockerl -p bockerl \    
  --authenticationDatabase admin \   # 인증 db
  --db snail /dump/snail

위 방식을 사용해서 dump 파일을 옮기려고 시도하였지만.. 오류가 발생했다;;

오류 발생.. 해결해보자..🥲

MongoDB 공식 블로그를 참고해서 해결하였고, 위 공식 문서에 동일한 오류를 처리할 수 있는 방식을 소개해뒀다.

<성공 과정>

# 1. 본인이 dump를 저장해둔 파일을 나의 mongo1 컨테이너에 복사한다.
$ docker cp /Users/hyeok/desktop/dump mongo1:/dump

# 2. Migration 하기 위해 복사한 dump를 컨테이너에 저장 ( 나의 경우: snail)
docker exec -it mongo1 mongorestore \
  -u bockerl -p bockerl \
  --authenticationDatabase admin \
  --db snail /dump/snail

위 방식을 통해서 먼저 dump 파일을 컨테이너에 복사하고, 불러와서 저장하는 과정이 필요하였다

rs0 [direct: primary] test> use snail
switched to db snail
rs0 [direct: primary] snail> show dbs
admin   140.00 KiB
config  160.00 KiB
local   440.00 KiB
snail   120.00 KiB
rs0 [direct: primary] snail> show collections
chatMessage
GroupChatRoom
PersonalChatRoom
rs0 [direct: primary] snail> db.createUser({ user: "bockerl", pwd: "bockerl", roles: [{ role: "readWrite", db: "snail"}] })

오예~🎉🎉🎉🎉🎉 데이터 마이그레이션을 성공하였고, 실제로 snail 데이터 베이스의 collections를 보면 잘 옮겨져 있는것을 알 수 있다!!

5) user 생성

snail 데이터베이스를 사용할 수 있도록 bockerl 라는 user를 생성하였다. 이제 모든 설정이 완료 되었고, 먼저 MongoDB compass 연결과 프로젝트 연결만 남았다.

3. 결과

1) MongoDB Compass에서의 연결

mongodb://bockerl:bockerl@localhost:27017,localhost:27018,localhost:27019/snail?authSource=snail&replicaSet=rs0

실제로 Docker 설정한 설정과 로컬에서 연결할 포트번호 및 사용 데이터베이스를 잘 입력해줘서 replica-set 등록을 진행한다.

보이는 것과 같이 MongoDB의 replica-set 등록이 잘되는 것을 확인할 수 있고, local을 통해 Docker에 띄워진 MongoDB를 성공적으로 연결하였다.

2) 실제 프로젝트 테스트

실제 프로젝트에서는 위와 동일하게 설정하여 진행하엿으며, 이는 위의 compass의 등록과 유사하다.

최종적으로 기존에 단일노드에서의 @Transactional로 인한 다중 도큐먼트 트랜잭션으로 발생한 오류가 발생하지 않고, 실제로 Replica-set 설정으로 인해 Docker에 떠있는 MongoDB에 잘 저장된 것을 확인수 있었다~🥲🥲🥲🥲🥲🥲ㅍ

4. 주의사항 (Trouble Shooting)

1) 꼭.. 정말 꼭 현재 본인 로컬 mongoDB가 연결 포트를 잡아먹고 있는지 확인하자

실제로 삽질을 할때, 이 로컬DB가 실행되고 있었고, 27017포트를 할당하고 있어서 계속 연결이 안되고 timeout이 발생하엿다.. 꼭꼭 확인해보도록 하자

2) docker-compose.yml 파일에서 외부에서 접근할 포트를 잘 확인하자

  mongodb1:
    image: mongo
    container_name: mongo1
    hostname: mongo1
    restart: always
    ports:
      - "27017:27017"
    environment:
      MONGO_INITDB_ROOT_USERNAME: bockerl
      MONGO_INITDB_ROOT_PASSWORD: bockerl
    command: mongod --replSet rs0 --keyFile /etc/mongodb.key --bind_ip_all
    volumes:
      - ./db1:/data/db
      - ~/.ssh/mongodb.key:/etc/mongodb.key

  mongodb2:
    image: mongo
    container_name: mongo2
    hostname: mongo2
    restart: always
    ports:
      - "27018:27018"
    environment:
      MONGO_INITDB_ROOT_USERNAME: bockerl
      MONGO_INITDB_ROOT_PASSWORD: bockerl
    command: mongod --replSet rs0 --keyFile /etc/mongodb.key --bind_ip_all
    volumes:
      - ./db2:/data/db
      - ~/.ssh/mongodb.key:/etc/mongodb.key

  mongodb3:
    image: mongo
    container_name: mongo3
    hostname: mongo3
    restart: always
    ports:
      - "27019:27019"
    environment:
      MONGO_INITDB_ROOT_USERNAME: bockerl
      MONGO_INITDB_ROOT_PASSWORD: bockerl
    command: mongod --replSet rs0 --keyFile /etc/mongodb.key --bind_ip_all
    volumes:
      - ./db3:/data/db
      - ~/.ssh/mongodb.key:/etc/mongodb.key


networks:
  infra:
    driver: bridge

이것이 나의 docker-compose.yml파일인데 기존에는 컨테이너 내부 연결을 전부 27017로 통일했었다. (ex. 27018:27017) 이렇게 진행하다보니 외부(local)에서는 계속 27018,27019로 접근하여도, Docker 내부에서는 27017로 되어있기 때문에 매치되지 않아서 연결이 실패하는 것이였다.

사실 제대로 작성된 글이 많지는 않았고, 정말 뒤죽박죽이었다... 2일을 밤을 새서 결국은 해결해내니까 정말 뿌듯.. 내가 설정을 진행하면서 했던 삽질과 문제원인을 소개하고자 한다. 꼭 다른 사람들은 나와 같은 경험을 하지 않았으면 한다.

5. Failover를 위한 추가 설정 ( + 2025.04.08)

추가적으로 MongoDB replica-set을 설정하면서, 조금 더 failover에 적합한 설정을 변경해주었다.

1) Election Timeout & Heartbeat Interval 설정

1. heartbeatIntervalMillis 2000 -> 1000 (헬스 체크 간격 2초 -> 1초)
2. electionTimeoutMillis 10000 -> 5000 (Primary 장애 감지 후 선출 타임아웃 10초 > 5초)

heartbeat와 electionTimeout 설정은 failover 시 장애 감지 및 새로운 Primary 선출을 보다 빠르고 효율적으로 수행하여, 데이터 정합성을 유지하고 서비스 중단 없이 원활한 전환을 도모하는 데 중요한 역할을 한다.

2) Catch-up 설정

1. catchUpTimeoutMillis

-1 -> 2000 (새 Primary가 Oplog 따라잡도록 부여되는 시간 즉시 -> 2초) 2. catchUpTakeoverDelayMillis 30000 -> 1000 (새 Primary 승격 후 요청 처리전 대기 30초 -> 1초)

catchUp 설정은 기존 Primary 장애시 새로운 Primary가 선출되면서 데이터 동기화를 완료하고 정상적인 처리로 전환하기 위한 설정이다. 또한, failover 시 데이터 정합성을 유지하고, 서비스 중단 없이 원활한 전환을 도모하는 데 도움을 줍니다.

참고블로그

1. 전체 설정: https://jh2021.tistory.com/24
2. replica 운영 세부 설정( 관련 내용 업데이트 예정) : https://oliveyoung.tech/2024-12-17/catalog-mongo-transaction-2/

💡 MSA 기반 Kafka를 통한 채팅 서비스의 메시지 유실 막아보자!! 💪🏻

1. 개요 위와 동일한 구조로 MSA 구조의 Kafka 기반 실시간 채팅 서비스를 구현하였다.

동작방식은 아래와 같다

1. Client가 메시지 전송 (sendMessage 메소드 실행)
2. DB에 메시지 전송
3. Kafka Producer를 통해 메시지를 Kafka Broker로 전송
4. KafkA Consumer가 Broker에서 본인에게 해당하는 메시지 가져옴
5. Stomp를 통해서 해당 채팅방을 구독중인 Client에게 전송

하지만, 만약 전송한 메시지가 "유실"된다면??

만약 메시지가 유실된다면, 실시간 채팅 서비스에서 메시지가 유실된다면, 실제로 전송하는 사용자와 받는 사용자의 메시지가 달라져서 "원자성"이 꺠지는 문제가 발생하게 된다. 따라서, 신뢰성 측면에서도 DB에 저장되는 메시지와 kafka를 통해 전송하는 메시지가 일치해야한다.

2. 문제 원인

메시지가 유실될 경우는 총 2가지가 존재한다. ( 위사진의 1번과 2번을 참고하여 보자)

1. 전송한 메시지한 메시지가 DB에는 잘 저장되지만, Kafka Broker에는 제대로 전송되지 않음

2. Kafka Broker에는 이벤트가 잘 전송되었지만, DB에는 제대로 전송되지 않음

위와 같은 경우에는 "원자성"이 지켜지지 않기 때문에, 신뢰성을 보장해줘야 한다.

3. 실제 예시

1) 성공 예시

위 처럼 Kafka 서버가 잘 띄워 져 있는 경우에는 메시지도 잘 전송되고, Consumer도 이벤트를 잘 받아서 처리하는 것을 볼 수 있다.

2) 실패 예시

만약 어떠한 오류로 인해 Kafka의 연결이 끊어지게 된다면, Producer에 의해 메시지가 전달되어도, Consumer는 아무것도 받지 못하고, 오류를 발생시킨다. 또한 실시간 채팅 서비스 관점에서 봤을때도, 메시지 전송은 되었지만, 받는 사람은 메시지 전송을 실시간으로 받지 못하고, "해당 메시지가 유실" 된 것으로 볼수있다.

물론, Retry 방식이나 ACk을 통해서 재 전송을 요청할 수 있지만, 만일 Retry를 3번 시도한 후에도, Ack이 계속 전송이 안되는 경우에는 결국 아예 메시지가 유실되게 된다.

따라서, 다른 방식을 통해 메시지 유실을 방지하여, "원자성"을 유지해야한다.

4. 해결 방법

1) Outbox 패턴 적용

+) Outbox는 @Transactional을 필수로 하기 때문에, MongoDB의 @Transactional 처리를 위한 replica-set을 설정하였다. (2번 참고)

참고 블로그 1. 2. MongoDB Replica-set 설정

💡 Github에 대용량 데이터를 올리기 위한 방법을 알아보자!!

1. 🙋🏻개요

나의 개인 Repository에 대용량 데이터를 Upload 하기 위해서 commit - push를 진행하였는데, 위와 같은 오류가 발생하였다..(20분이나 걸렸는데..ㅎ) 아마 오류를 읽어봤을 때, 한번에 올릴 수 있는 데이터의 크기를 넘어가서 발생하는 거 같았다. ( 나중에 찾아보니 한번에 올릴 수 있는 데이터의 크기는 최대 100MB까지 가능한 거 같다.)

2. ✨해결책

1. git-lfs 설치

# Mac HomeBrew 기준
brew install git-lfs

우선 대용량 데이터를 올리기 위해서는 git-lfs가 필요하기 때문에 설치를 진행하였다. 나는 터미널에서 바로 설치하였지만, 직접 사이트에 접속해서 할 수도 있다고 한다.

2. 전송할 대용량 파일을 lfs로 설정하고 보내기

// 1. lfs로 관리할 대용량 파일 설정해주기
// (주의 사항, 현재 파일 안의 파일 내부에 대용량 데이터가 속해있으면 경로까지 입력 필요)
$ git lfs track 파일명
// git lfs track "cv_models/FRcnn/output/model_final.pth"


// 2. 변경된 내용 스테이징
$ git add .gitattributes
$ git add .


// 3. 커밋
$ git commit -m "커밋 메세지"

// 4. 푸시
$ git push origin main

위 방식을 따라서 진행하면 대용량 데이터 파일이 잘 업로드 된다. 첫번째 방식에서 주의해야 할 점은 내가 올리려는 파일 내부에 대용량 파일이 있으면, 직접적인 경로를 넣어줘야 한다는 점이다!! 추가적으로 lfs 파일을 제외한 다른 여러 파일도 함께 commit & push가 가능하다.

3. 👍🏻결과

위와 같이 100MB가 넘는 대용량 파일이 잘 업로드 된것을 확인할 수 있었다. (이 파일의 크기는 무려 320MB 였다고 한다.. ㅎ)

이번 프로젝트를 진행하면서, 테스트 코드를 제대로 짜보기로 기획하였다. 따라서 한 메소드가 완성 될때마다, 동작하는 지 여부를 확인하기 위한 테스트 코드를 짜면서 발생했던 문제점들과 해결법들을 적어보고자 한다.

1. 테스트가 실제 DB에 영향을 주는 문제 발생

// 메시지를 저장할 메시징 큐
private val messageQueue: BlockingQueue<CommandChatMessageRequestDto> 
= LinkedBlockingQueue()

// 메시지 전송
val messageDto =
CommandChatMessageRequestDto(
sender = "Alice",
chatRoomId = chatRoomId,
message = "안녕하세요, Alice22입니다.",
messageType = CommandChatMessageType.CHAT,
)

session.send("/app/$chatRoomId", messageDto)

// 메시지 정상 전달 여부 확인
val receiveMessage = messageQueue.poll(5, TimeUnit.SECONDS)

기존 테스트 코드에서는 위 방식처럼 직접 기존 경로를 통해서 메시지가 전송되는 것을 확인하기 위해, send()를 사용하여 실제 구독 경로로 메시지를 전송하였고, 해당 경로를 구독 중인 사용자들에게 전송되어 실제 DB에 저장되었다. 하지만, 테스트 과정이 실제 환경에 영향을 미치면 안되므로, 메시지를 전송해도 실제 DB에 영향을 미치지 않고, DB에 잘 저장이 되는지를 확인하기 위해서 다른 방식을 사용하였다.

2. 해결과정

1. Embedded-MongoDB 적용하기

실제 DB환경에 영향을 주지 않고, 테스트 코드만을 위한 DB를 만드는 방식을 알아보니 대표적으로 2가지가 존재하였다.

1.Embedded MongoDB: Java 애플리케이션 내에서 Embedded MongoDB를 실행

• 장점: 빠른 실행 속도/ 설정 쉬움
• 단점: 실제 운영환경과는 다를 수 있음 / MongoDB의 고급 기능(샤딩, 트랜잭션 등) 제공 X / 병렬 테스트 어려움

2.TestContainer MongoDB: Docker 컨테이너에 MongoDB를 만들어서 실행

• 장점: 실제 운영환경과 동일한 MongoDB 사용 / 테스트 환경 일관성 유지 / 병렬 테스트 가능 / MongoDB 고급 기능 제공 O
• 단점: Docker 필요 / 테스트시 컨테이너 시작 시간이 추가됨 / 설정 복잡

위와 같은 장단점을 가지고 있는 2가지 방식이 있었고, 우리 프로젝트의 특성을 대입하여 봤을때, CI/CD시에도 크게 문제가 없고, 운영 하는 과정에서 장애가 적은 "TestContainer MongoDB"를 사용하기로 결정하였다. 추가적인 조사와 실험을 해본 결과 TestContainer는 서버를 실행시에는 container를 새롭게 만들어야 하기 때문에 시간이 많이 소요되었다. 따라서 운영 검증 시에 Test Container를 사용하기로 결정하였고, 빠른 속도가 중요한 단위 테스트에는 Embedded-MongoDB를 사용하기로 결정하였다.

점수: 80/100 코테 BFS+재귀 8문제 풀기 - 🔴 프로젝트에 Kotlin으로 채팅 기능 전부 구현하기 (Kafka이용) - 🔺 프로젝트 Kotlin 테스트 코드 개선사항 추가하기 - 🔴

🙋🏻2월 5주차 회고

이번주는 나에게 좋은 소식이 찾아온 한 주였다. 나름 개발을 진행하면서도 틈틈히 이력서를 써서 넣어보았었고, 아직 배우지 못한 기술 스택이나 경험들이 부족하다고 생각해서 이번 프로젝트도 더 열심히 진행한 것이었다. 물론, 아직 프로젝트가 한참 진행 중이지만, 여태까지 잘 붙지 못했던 서류를 몇번씩 고쳐가면서 열심히 써본 결과!! 붙었다.. 그것도 "카카오페이에"...ㅎㅎㅎ 사실 당시에 자소서를 쓸때에는 큰 생각없이 작성하긴 하였지만, 막상 서류가 붙고 다시 읽어보니 짜임새 있게 잘 쓰여있었던 거 같다. 최근 "아형" 취업 유튜브 특강을 들으면서 경험을 정리하고 수치화를 통해 경험을 구체화했던 경험이 나름 자소서에 잘 녹아들어가 서류에서 좋은 점수를 얻은 거 같다고 생각한다.

그래서 이번주는 카카오페이 코딩테스트를 위한 코테 알고리즘 공부를 위주로 진행하였다. 오랜만에 보는 알고리즘들을 학습하고 정리한다는 것이 쉽지는 않았지만, 그래도 쉽게 올 수 없다는 기회라는 것을 알기에 정말 열심히 준비하였다. 알고리즘들을 다시 분석하고, 문제들을 풀면서 개념을 익혔다. 하지만, 3일이라는 시간이 너무 짧았던 것인지.. 나에게는 문제가 꽤 많이 어려웠다.. 사실 카카오페이 코딩테스트 문제가 제일 어렵다는 얘기를 많이 들었지만, 역시 어려웠다..하하 그래도 코테 스터디를 열심히 진행하면서 문제 풀이 방식이나, 시간복잡도를 계산해서 사고하는 방법들을 많이 연습하고 배워서 그런지, 지난번 코딩테스트 보다는 많이 손을 댈 수 있었던 거 같다. 이번 기회에 코딩테스트 준비도 정말 많이 해야겠다고 느꼈고, 역시 취업을 위해서는 더 열심히 준비해서 갈아 넣어야 할 거 같다!! 해야할 게 정말 계속계속 늘어난다.🥲

프로젝트 개발적인 측면에서는 사실 이번주에 자소서를 적기도 하였고, 갑작스러운 코테준비도 하게 되어서, 개발에는 많이 신경을 쓰지 못하였다.. 그래도 우리가 가장 먼저 목표하였던 공모전 참가는 다행히 잘 진행하여 3/18 ~4/16일까지 진행하는 해커톤에 참가가 확정되었다. 물론 자소서, 포폴, 지원도 중요하지만 해커톤을 참가하기 위해서 이제는 프로젝트에도 좀 더 신경을 써야겠다고 생각했다. 이제는 3월의 시작이니 취업지원도, 프로젝트도, cs공부도 더더더 열심히 진행해보자 스스로에게 화이팅이다!💪🏻

📢3월 1주차 회고

코테 문제 BFS 5문제 + 재귀 3문제 우리 은행 취업 지원하기 프로젝트에 Kotlin으로 채팅 기능 구현하기(STOMP)

💡 카카오페이 코테를 준비하기 위해서 알고리즘 정리를 해보고자 한다.

1. 재귀

1. 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘
2. 특정 입력에서 자기자신을 호출하지 않고 종료되어야 함
3. 재귀는 코드는 간결하지만, 메모리/시간 측면에서는 손해를 본다 ( 반복문으로만 짜기 너무 복잡한 문제는 재귀로 시도해보자)
4. 재귀에서 자기 자신을 여러번 호출하는 것은 비효율적이다.
5. 재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 된다.

=> Tip:

1. 하나의 함수에 여러 개의 재귀함수를 선언하는 것은 좋지 않다.
2. 재귀는 메모리 초과나 시간초과를 쉽게 발생시킬 수 있으니, 시도해보고 초과가 발생하면 복잡해도 반복문으로 구현해야한다.

2. 백트래킹

1. 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
2. 해당 경로로 갔다가 해당 경로가 맞지 않으면 돌아와서 다른 경로로 가는 방식 사용
3. "상태공간트리"라고도 한다.
4. 재귀를 사용한 알고리즘

=> Tip:

1. 모든 경우의 수를 계산해야 할 때 고려할 필요 있음
2. 입력 크기가 작은 경우 많이 사용
3. 중복없이 선택하는 경우
4. 사전순 (작은수 -> 큰수) 같은 경우 주로 사용

=> 풀이 Top:

1. 조건을 통해 특정 조건에 만족하면 return하는 식으로 재귀를 빠져 나간다
2. 재귀 호출 전 상태 변경 + 재귀 호출 후 상태 복원

3. DP (다이나믹 프로그래밍)

1. 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘
2. 해당 문제의 점화식을 찾아내서 풀어야 한다.
3. 테이블을 만들어야하고, 점화식을 찾아서 초기값을 넣고 점화식에 맞춰서 원하는 값까지 도달하도록 해야한다.
4. 결국 DP는 점화식을 얼마나 빨리 찾냐의 문제이고, 유형을 최대한 많이 익혀야한다.

4. 그리디 (Greedy)

1. 현재 가장 최적인 답을 택하는 알고리즘 ( 그림처럼 현재 상황에 가장 최적인 답을 선택 )
2. 관찰을 통해 탐색 범위를 줄이는 알고리즘
3. 풀이방법 1) 관찰을 통해 탐색 범위를 줄이는 방법을 생각 (시간 복잡도를 줄일 수 있는 방법을 고안) 2) 탐색 범위를 줄여도 올바른 결과를 낸다는 것을 확인 3) 구현을 통한 풀이
4. 풀이 Tip => 그리디 풀이 100% 확신 : 짜서 제출해보고 틀리면 바로 손절 => 그리디 풀이 애매: 다른거 먼저 풀고, 마지막 2-30분 안에 도전
5. 접근 Tip => 대부분 그리디 보다는 DP가 많이 나오기 때문에, DP로 풀었는데 시간초과가 발생하거나 한 경우 Greedy를 고려해보자! => 가능한 ~~중 가장 먼저 만나는 것 택하기

5. 이분 탐색 (Binary-Search)

1. 정렬 되어 있는 배열에서 특정 데이터를 찾기 위해 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법
2. 선형탐색 : O(N) / 이분 탐색 : O(logN)
3. 파이썬에도 Binary-search를 지원하는 메소드가 존재한다. ( 사용가능하다면 추천)

   from bisect import bisect_left, bisect_right
   

array = [1, 2, 3, 4, 4, 6, 8, 9] x = 4

print(bisect_left(array, x)) # 3 print(bisect_right(array, x)) # 5

특정 값 존재 여부

def count_by_array(a, val): right_index = bisect_right(a, val) left_index = bisect_left(a, val) return right_index - left_index

특정 범위 원소 찾기

def count_by_range(a, left, right): right_index = bisect_right(a, right) left_index = bisect_left(a, left) return right_index - left_index

특정 갑의 존재 여부

print(count_by_array(array,3)) # 0보다 크면 존재, 0이면 존재하지 않음

특정 범주 내의 존재하는 총 갯수

print(count_by_range(array, -1, 3))

특정 값의 갯수

print(count_by_range(array, 4, 4))

- array가 정렬되어 있다면, bisect_left(arr,x)는 arr에서 x가 들어갈 수 있는 가장 왼쪽 인덱스를 반환한다.
- array가 정렬되어 있다면, bisect_right(arr,x)는 arr에서 x가 들어갈 수 있는 가장 오른쪽 인덱스를 반환한다.
- 위 count_by_range함수를 사용해서, 특정 범위내에 포함되는 원소의 개수를 구할 수 있다.
- 위 count_by_range함수를 사용해서 배열 array에서 원소 x의 개수를 구할 수 있다. (left와 right에 동일한 값을 넣어주면 해결)


4. **풀이 Tip**
=> 선형  탐색시에 시간복잡도가 터지는 경우에는 고려해봐야한다.
=> **정렬은 필수**
=> 파이썬 라이브러리를 사용할 수 있다면 적극 활용 ( But, 해당 배열에 선택값이 존재하는 여부만 알 수 있음)
=> start, mid, end를 잘 적용해야하고, 특정상황에 따라 mid값을 구하는 방식이 달라질 수 있음을 주의
아래와 같이 2가지 경우가 발생할 수 있음. 가끔 1번은 무한루프를 발생시키기도 한다.
( 기존 1번 방식때로 진행하였는데 무한루프가 발생한다. 하면 st와 en의 index가 1차이날 경우를 보고 다시 판단하면 된다)
    1) mid = (start + end) / 2
    2) mid = (start+end+1) / 2
=> **유형 고착시키기**
```python
# 특정 갯수가 포함되어 있는지
def binary_search(target):
    st = 0
    en = N-1

    while(st <= en):
        mid = (st+en)//2
        if target == card[mid]:
            return True
        elif target < card[mid]:
            en = mid - 1
        else:
            st = mid + 1

## 특정 원소의 갯수 구하기
# 하위 값
def lower_bound(target):
    st = 0
    en = N

    while(st < en):
        mid = (st+en)//2
        if target <= card[mid]:
            en = mid
        else:
            st = mid + 1

    return st

# 상위 값
def upper_bound(target):
    st = 0
    en = N

    while(st < en):
        mid = (st+en)//2
        if target < card[mid]:
            en = mid
        else:
            st = mid + 1

    return st

5-1. 매개변수 탐색 (Parametric-Search)

1. 조건을 만족하는 최소/최댓값을 구하는 문제(최적화 문제) -> 결정문제로 변환해 이분탐색 수행 ex) N개를 만들 수 있는 랜선의 최대 길이 (최적화) / 랜선의 길이가 X일때 랜선이 N개 이상인지 여부 (결정)

2. 조건은 위와 같은 함수 형태로 나타냈을 때, 증가함수 or 감소함수로 일정해야한다. (뒤죽박죽이면 불가)

3. 접근 Tip: => 최소 or 최대값에 대한 얘기 있을 경우에 범위가 무지막지하게 큰경우 => 시간 복잡도에게 N하나를 logN으로 떨어트려야 할 경우 고민해봐야 한다. ex) O(N^2) -> O(NlogN)

6. 투포인터

1. 배열에서 이중 For문 (O(n^2))으로 풀어야할 문제를 2개의 포인터를 사용해서 1개의 For문으로 푸는 알고리즘
2. 위 방식과 동일하게, 하나의 배열의 for문에서 2개의 포인터가 움직이면서 계산하는 알고리즘이다.
3. 투포인터 -> 이분탐색 / 이분탐색 -> 투포인터 모두 가능하다.
4. 정렬되어 있는 경우 주로 사용

7. 소수구하기 - 에라토스테네스의 체

코딩테스트에서 소수를 구할 경우 많이 사용되는 방식이다. 기존에는 이중 for문을 이용한 O(N^2)의 시간복잡도를 가지고 있지만, 이 경우는 O(N√n )을 가진다.

# 0과 1은 먼저 False 처리
prime = [False,False] + [True] * (N-1)

for i in range(2, int(n**0.5)+1):
    if prime[i]:
        # i의 배수에 해당하는 수는 전부 False 처리 ( 2,3 등을 제외하기 위해 *2 )
        for j in range(2*i, N+1, i):
            prime[j] = False

위 방식을 통해 범주를 줄이고, 크기를 키워가면서, 해당하는 수의 배수를 전부 제거해주면 소수인 것 들만 True를 가지고 있다.

8. 우선순위 큐

파이썬에서는 heapq라는 우선순위 큐 라이브러리를 제공한다. (heapq는 Min Heap) heap은 최소 큐라고도 불리고, 가장 작은 값을 반환하기에 수월하다.(반대로 -를 붙여서 가장 큰 값을 반환하기도 수월하다.)

우선순위 큐 (Priority Queue)는 힙(Heap)의 키(Key)를 우선순위로 사용하므로, 우선순위 큐의 구현체가 된다.

Heapq Method

heappush ( 해당 node의 index와 우선순위 같이 넣어줌) - O(logN) 아이템 삽입

heappop - O(lognN) 우선 순위가 가장 높은 or 낮은 노드 삭제

heap[0] - O(1) 우선 순위가 가장 높은 or 낮은 노드 조회

+) 배열을 통해 이진 트리를 구성하고, 부모노드, 자식노드를 찾는법

9. 트리(Tree)

BFS와 DFS는 기존 방식과 동일하게, Deque와 Stack or 재귀를 사용해서 푼다 Tip은 2차원 배열을 통해 1 - 2가 연결되어 있으면 graph[1][2] = graph[2][1] = 1을 통해 저정하거나, graph[1].append(2)를 통해서 각 인덱스와 연결된 노드를 저장해서 풀도록 하자 ( 해당 노드의 부모 노드를 저장할 경우에는 따로 부모배열을 선언하자)

이제, DFS와 BFS를 제외한, 순회에 대해서 알아보도록 하자

1) 레벨순회

레벨순회 = 높이순으로 방문하는 방식 (정점 노드부터 시작) 레벨 순회는 1-2-3-4-5-6-7-8 순으로 순회하며 BFS를 사용하면 자식노드를 넣어주면 해결가능

2) 전위순회

전위순회 = 정점 - 왼쪽 - 오른쪽 순으로 순회한다. (재귀를 사용) 전위 순회는 1-2-4-5-6-3-6-7 순으로 순회하며, DFS를 통해서 해결 가능하다.

3) 중위순회

중위순회 = 왼쪽 - 정점 -오른쪽으로 순회한다. (가장 왼쪽부터 순회) 중위순회는 4-2-5-8-1-6-3-7 순으로 순회한다.

4) 후위순회

후위순회 = 왼쪽 - 오른쪽 -정점으로 순회한다. (정점보다 오른쪽을 먼저 거침) 후위순회는 4-8-5-2-6-7-3-1 순으로 순회한다.

10. 다익스트라 알고리즘

1. 하나의 시작점부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘
2. 최단거리를 구할 때 사용되는 DFS,BFS,DP,Dijkstra 알고리즘 중 하나
3. 간선의 비용이 음수일때는 사용할 수 없다.
4. 최단 거리는 여러 개의 최단거리로 구성되어있다. (DP와 동일) ( 하나의 최단거리를 구할 때, 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다.)

💡 bfs 중 시작하자마자 종료되는 조건을 잘 헤아려야 하는 문제

import sys
from collections import deque

input = sys.stdin.readline

M, N, K = map(int, input().rstrip().split(' '))

graph = [[0] * N for _ in range(M)]
total_square = []
cnt = 0

def bfs(x,y):

    dq = deque()
    dq.append((x,y))
    graph[y][x] = 1
    square = 1

    #상하좌우
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]

    while dq:
        x, y = dq.popleft()
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]
            if 0 <= nx < N and 0 <= ny < M and graph[ny][nx] == 0:
                graph[ny][nx] = 1
                dq.append((nx,ny))
                square += 1

    return square

for _ in range(K):

    left_x , left_y, right_x, right_y = map(int, input().rstrip().split(' '))

    # 사각형 해당 영역 먼저 넣기
    for i in range(left_y, right_y):
        for j in range(left_x, right_x):
            graph[i][j] = -1

# bfs 넣기        
for y in range(M):
    for x in range(N):
        if graph[y][x] == 0:
            total_square.append(bfs(x,y))
            cnt += 1

print(cnt)
print(' '.join(map(str,sorted(total_square))))

• bfs문제를 많이 풀어봤지만, 늘 느끼는거는 각 문제들마다 bfs이지만 접근법이 조금씩은 다 다르다는 것이다.
• 이 문제에서의 차이점은 우리가 벽의 범주에 해당하는 입력값을 받아서 벽을 만들어야된다는 점이다. 먼저 벽을 전부 만들고 나서, bfs를 돌려주는 방식으로 진행하였고, 결과값 자체가 이동가능한 영역의 갯수와 각 영역의 넓이를 구해야 했기 때문에, bfs에 들어갈때마다 cnt를 +1 해주고, bfs 내부에서도 영역의 넓이값을 계산해줘야 했다.
• 문제를 풀면서 만났던 문제는 어떻게 영억의 넓이를 구할 것인가와 들어가자마자 벽을 만났을 때가 문제였다. 이 문제는 특정 지점에 도달하는 최솟값을 구하는것이 아니였기 떄문에, 순회하면서 dq에 들어갈때 square에 1을 더해 총 영역의 넓이를 계산하였다. 또한 들어가자마자 벽을 만날 경우를 대비하여, 처음 입장시부터 입력받은 시작점 값을 계산해주는 방식으로 해결하였다.

점수: 60/100 코테 BFS 10문제 풀기 - 🔴 프로젝트에 Kotlin으로 채팅 기능 전부 구현하기 (Kafka이용) - 🔺 프로젝트에 Kotlin으로 알림 기능 전부 구현하기 (Redis이용) - ❌

🙋🏻2월 4주차 회고

이번주는 개발에 크게 신경을 못쓴 한주였다. 사실 이번주 금요일에 졸업식이 있었기 때문에, 평소처럼 매일매일 공부하고 개발을 하지 못하였다. 그래도 나름 알차게 코테 준비를 하면서 BFS 문제도 열심히 풀었고, 이번에 사실 당근과 카카오페이 인턴 공고가 올라와서 해당 공고에 지원도 진행하였다. 졸업을 하면서 약간의 취업에 대한 압박감이 높아지기도 하고, 이번에 공고에 대한 자소서를 적으면서 다시 한번 나의 자소서를 더 만져봐야하고, 끊임없이 경험들을 빠르게 쌓아나가는 것이 중요하다고 생각했다. 사실 가장 중요한 것은 이번에 진행중인 프로젝트에서 우리가 원하는, 또 공고에서 기업들이 많이 요구하는 기술 스택이 많이 들어간 만큼 다음주는 백엔드 개발에 조금 더 집중해서 진행해야겠다고 생각했다.

이번에 유튜브에서 진행하는 '아형'의 자소서 특강을 듣게 되었다. 사실 처음 자소서를 적을때 인사과인 동생이 추천해줬던 "자소서 바이블 2.0"이라는 책을 읽고, 준비하는데에 많은 도움이 되었던 기억이 있다. 그래서, 이번 기회에 자소서 특강을 들어보며 부족한 나의 자소서의 방향성을 잡고, 진행해보고자 한다. 이제는 시기상 3월에 곧 들어서고 상반기 공고도 많이 올라올 예정이니, 개발에만 집중하지는 말고, 개발과 자소서와 포트폴리오를, 코테를 전부 병행하면서 해야겠다고 생각했다. 앞으로 시간 분배가 조금 더 중요해질 거 같다.

이번 팀 프로젝트 회의에서 추가적으로 변경사항이 생겼다. 기획을 진행하다보니, 볼륨이 좀 많이 커지기도 했고, 사실 처음해보는 기술스택이 많았기 떄문에, 우리가 계획했던 2월까지 마감은 힘들 것이라고 생각하였고, 그래서 2주전에 회의를 통해 2월까지 백엔드를 마감하고, 3월에는 React와 React-native를 공부하며, 이력서에 조금 초점을 맞추기로 결정하였다. 하지만 이번 회의해서 조금 변경사항이 생겻다. 아무래도 처음해보는 Kafka나 kotlin이기도 하고, 비지니스 로직이나 성능적인 개선 사항을 좀 더 디테일하게 완성하기 위해서, 백엔드의 기간을 조금 더 늘려야겠다고 결정이 되었다. 그래도 새로운 스택인 만큼 많은 소통과 참고를 통해서 깊게 파고있는 중이며, 조금 더 집중해서 진행해볼 생각이다.

📢2월 5주차 Plan

코테 BFS+재귀 8문제 풀기 프로젝트에 Kotlin으로 채팅 기능 전부 구현하기 (Kafka이용) 프로젝트 Kotlin 테스트 코드 개선사항 추가하기

💡 sourceTree + Github에서 발생한 오류 공유

오늘도 여김없이 나를 깜짝 놀래키는 sourceTree이다.. 진짜 부정적인 경험을 너무해서 sourceTree 사용보다는 CLI를 통한 github 업로드를 진행할거다.. .반드시... 반드시이.....

1. 개요

현재 진행 중인 snail 프로젝트에서 기존 진행 중인 feat/chat 브랜치를 잘 사용하고 있었다. 위의 사진을 보는 것 처럼 당장 4일 전인 2/21에 commit push를 잘 진행하여 문제없이 github repo에는 적용이 되어 있는 것을 확인할 수 있다.

하지만 오늘 다시 개발을 위해서 sourceTree로 들어갔을 때, 기존 snail 파일이 feat/chat으로 되어 있지 않고 master branch로 설정되어 있으며, 전체 파일이 전부 등록이 되어 있지 않고, commit 내역이 전부 삭제되어 있었다... (sourceTree는 너무 당황해서 캡쳐를 해두지 못하고 삭제하였다) 위에 사진을 보는 것처럼 feat/chat 브랜치의 status를 보면 전체 파일이 전부 commit되지 않은 오류가 발생하였다.

2. 문제점 분석

1) feat/chat 브랜치의 문제인가? - ❌

처음에는 내가 개발 중인 feat/chat 브랜치의 문제가 있는지 확인하기 위해서 현재 개발중인 github repo의 network graph로 들어가서 나의 브랜치 상태를 확인해보았다. 하지만 위 사진에서 보는 것과 같이 나의 브랜치는 내가 개발해둔 상태와 동일하게 21일까지의 활동이 잘 기록된 것을 확인할 수 있었다.

2) git 내부 파일의 문제인가? - ✅

# 1. git log를 찍어보면서 문제 상태 확인하기
$ git log
$ git reflog

가장 처음으로 해당 feat/chat 브랜치에서 문제사항을 찾기 위해서 git log와 git reflog 커멘드를 통해서 실행된 로그와 커밋 해쉬를 통해서 찾아보려고 했지만, 새로 생긴 branch여서 log가 존재하지 않다고 나왔다.. What..?😂

git fsck는 git 데이터베이스 내 객체의 연결성과 유효성을 검사를 하는 메소드이고, 이 메소드를 통해서 dangling 상태의 커밋 해쉬로 부터 잃어버린 커밋을 찾으려고 하였지만, 위에서 아예 commit log 내역을 찾을 수 없기 떄문에 이 또한 의미가 없었다. 하지만 위의 사진에서 보는 것 처럼 여기서도 역시 해당 feat/chat 브랜치가 지금 막 생성된 commit을 한번도 하지 않은 브랜치라고 나타내고 있다.

드디어 오류를 해결할 수 있는 실마리가 잡혔다.. 기존에 사용하고 있는 브랜치가 pull이 되지 않아서 발생하는 문제인가 싶어서 git pull origin feat/chat을 사용해서 pull을 진행하였는데 위와 같은 바로 기존 사용하던 feat/chat 브랜치를 다른 git 프로세스가 작동되고 있어, ~.lock 파일을 생성하지 못하여서 발생하는 오류였다.

+) .lock 파일은 특정 Git 프로세스가 동작중일 때 다른 Git 프로세스가 실행되는 것을 막기 위해서 자동으로 생성 되는 파일이다.

결국 이문제가 발생했던 원인은 SourceTree을 사용하여 commit - push를 진행하였는데, 비정상으로 git이 종료되어서 .lock 파일이 남아 있기 때문에 접근이 lock이 걸려서 발생하는 문제였다.

3. 원인 분석

1) SourceTree와 Ktlint의 충돌이 문제인가? - ❌

현재 snail 프로젝트에서는 kotlin을 사용하고, Ktlint를 통해서 코딩 컨벤션에 따라 이를 준수할 수 있도록 스타일을 검사한다. 이 과정에서 commit 하기 전에 코드의 스타일을 체크하고, 스타일을 적용하지 않으면 commit을 막게 된다. 하지만 SourceTree와 같은 경우는 따로 설정을 진행하지 않으면, ktlint를 무시하고 강제로 commit-push가 일어난다. 따라서 이러한 문제 때문에 git이 비정상적으로 종료되서 .lock이 삭제되지 않는 문제인가?? 하는 생각을 하였지만... 생각해보면 지금 계속 SourceTree를 사용하여 repo에 올려왔기 때문에 이는 원인은 아닌거 같다는 생각을 하였다. +) 하지만 이번에 알게된 정보처럼 앞으로는 cli 환경에서 ktlint 검사를 진행하면서 upload를 진행해야 겠다.

2) Git 파일의 생각지 못한 충돌 or 파일 손상 - ✅

정확한 이유를 확실하게 찾지는 못하였지만, 아주 높은 가능성으로 .git 내부에 있는 .lock 파일이 손상이 되었거나, 아니면 의도치 않도록 파일이 꼬여서 git이 비정상적으로 종료되었다고 생각한다.

3. 해결방식

# 1. .git 파일 내부에 있는 .lock 파일을 제대로 삭제해준다.
$ rm /Users/hyeok/desktop/snail/.git/refs/heads/feat/chat.lock

# 2. 다시 해당 브랜치로 check out 진행
$ git checkout feat/chat

기존에 git이 정상적으로 종료가 된다면, 프로세스가 git 프로세스를 전부 활용하고 .lock 파일을 삭제하여 다른 프로세스가 git 프로세스를 이용할 수 있도록 해주어야 한다. 하지만, git이 비정상적으로 종료되었고, 그로 인해 .lock 파일이 남아있어서 실제 브랜치를 인지하지 못했기 때문에 오류가 발생하였다.

따라서 .lock 파일을 삭제하고, 다시 feat/chat 브랜치로 checkout을 진행하였다.

4. 결과

다행히 lock 파일을 삭제시켜주고 다시 조회해본 결과 이전과 동일하게 잘 적용된 브랜치로 상태가 돌아오는 것을 확인할 수 있었다!! sourceTree는 생각보다 오류를 자주 발생시키는 거 같다.. 앞으로는 CLI를 이용해서 github에 업로드 해야겠다는 생각이 들었다..🥲

참고 블로그 https://velog.io/@yona_inthe_fish/%EC%97%90%EB%9F%AC%EC%9D%BC%EC%A7%80%EC%83%88%EB%A1%9C%EC%9A%B4-%EC%98%A4

💡 1차원 bfs 유형 (코테 스터디에서 나온 접근을 살펴보자)

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int,input().split(' '))

if N == K:
    print(0)
    exit(0)

visited = [False] * 100001

def bfs():

    cnt = 0

    dq = deque()
    dq.append((N,cnt))
    visited[N] = True

    while dq:
        x, cnt = dq.popleft()
        for nx in [x-1, x+1, x*2]:

            if 0 <= nx <= 100000 and visited[nx] is False:
                if nx == K:
                    print(cnt+1)
                    return
                else:
                    visited[nx] = True
                    dq.append((nx, cnt+1))

bfs()

• 이번 문제는 코테 스터디에서 들었던 기발한 풀이법이 계속 머리속에 남는다..ㅋㅋㅋ
• 일단 이번 문제는 그렇게 어렵지 않게 접근했던거 같다.
• 동생의 위치는 K로 고정되어 있고, 수빈이 N에서 계속 적으로 움직이는 것이기 떄문에,시작점을 N으로 잡고 이동가능 경우의 수를 [n-1,n+1,2*n] 총 3개의 경우로 bfs를 적용하였다.
• visited 배열을 선언하여 지금까지 방문한 위치에는 중복으로 가지않도록 설정하여, 가장 빠른 시간을 출력하려고 하였다.

💡 코테 스터디에서 나온 기발한 풀이법

서현님

from sys import stdin as s
from collections import deque

N, K = map(int, s.readline().split())

X = max(N, K) + 2
dp = [-1] * X
dp[N] = 0
dq = deque()
dq.append(N)

while dq:
    x = dq.popleft()
    if x == K:
        print(dp[x])
        exit()
    for y in [x+1, x-1, x*2]:
        if 0<=y<X and dp[y]==-1:
            dp[y] = dp[x]+1
            dq.append(y)

• 위 코드와 같이 수빈이 이동할 수 있는 최대 경로를 X = max(N,K) + 2로 설정하였다.

  ex) 1, 15 16 - 1 을 고려하기 위해서 + 2를 진행해줘야 한다. 이렇게 하면 *2가 될수 있는 최댓값까지 고려가 가능하다. 굳이 배열을 최댓값까지 고려해줄 필요가 없다

  x / x+1 / x+2 / x+3 =>x+3은 x+1로 대처가 가능하다.

• 설명을 추가하자면, 수빈이 갈수있는 최대값은 동생의 위치 +2까지만 구하면 된다. 왜냐하면 *2를 고려해야 하기때문에 +1을 하게되면 *2를 고려하지 못하게 되고, +3을 하게되면 사실 이는 최소값을 구하는 시점에서 +1로 대체가 가능하기 떄문에 최종적으로 +2까지만 고려하면 된다.

💡 BFS 중 난이도가 많이 어렵고 시간이 오래걸린 문제이다.. 그래도 상세히 돌파하였다.

import sys
from collections import deque

# 함수 선언
def fire_bfs():

    while fire_dq:
        x, y = fire_dq.popleft()
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]

            if 0 <= nx < X and 0 <= ny < Y and graph[ny][nx] == '.' and visited_f[ny][nx] == 0:
                graph[ny][nx] = '*'
                visited_f[ny][nx] = visited_f[y][x] + 1
                fire_dq.append((nx,ny))

def sang_bfs():

    while sang_dq:
        x, y = sang_dq.popleft()

        if x == 0 or x == X-1 or y == 0 or y == Y-1:
            return visited_s[y][x]

        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]

            if 0 <= nx < X and 0 <= ny < Y and graph[ny][nx] != '#' and visited_s[ny][nx] == 0:
                if graph[ny][nx] == '*' and visited_f[ny][nx] > visited_s[y][x] + 1:
                    visited_s[ny][nx] = visited_s[y][x] + 1
                    sang_dq.append((nx,ny))
                elif graph[ny][nx] == '.':
                    visited_s[ny][nx] = visited_s[y][x] + 1
                    sang_dq.append((nx,ny))

    return "IMPOSSIBLE"

# 입력 시작
input = sys.stdin.readline

T = int(input())

for _ in range(T):

    X ,Y = map(int,input().split(' '))

    graph = [list(input().rstrip()) for _ in range(Y)]
    visited_f = [[0] * X for _ in range(Y)]
    visited_s = [[0] * X for _ in range(Y)]

    fire_dq = deque()
    sang_dq = deque()

    # 상하좌우
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]

    # 불, 상근넣기
    for i in range(Y):
        for j in range(X):
            if graph[i][j] == '@':
                sang_dq.append((j,i))
                visited_s[i][j] = 1
            elif graph[i][j] == '*':
                fire_dq.append((j,i))
                visited_f[i][j] = 1

    fire_bfs()
    print(sang_bfs())

• 이제 불 문제만 보면 구역질이 날것만 같다..ㅋㅋㅋㅋㅋ
• 기존 앞선 불! 포스팅과 동일한 문제였지만, 불!에서 기발했던 풀이 방식으로 다르게 풀어보았다.
• 불과 상근의 bfs함수를 따로 구현해서, 불을 아예 먼저 다 돌리고, 다음에 상근을 돌리는 방식으로 진행하였다.
• 핵심은 불을 먼저 다 돌리면서 걸린 날짜(이동하면 +1을 해준다)를 visited_f배열에 모두 저장을 하고 상근을 돌리면서 visited_f의 값과 visited_s 값을 비교해서 visited_s + 1이 작으면 fire보다 도달하는 날짜가 작은것이니 해당 경로는 갈 수 있음을 의미한다.
• 위 방식을 반복하면서 가장자리에 도달하면 탈출하며 return하는 방식을 사용하였다.

💡 문제가 되었던 반례

1) 처음 입장하자마자 탈출이 가능한 경우

1 2 2

[입력] .@ ..

answer:1

if x == 0 or x == X-1 or y == 0 or y == Y-1:
    return visited_s[y][x]

• 이 문제로 12%에서 약속처럼 오류가 발생하였다.
• 문제의 원인을 보자면 처음에 입장하자마자 탈출이 가능한 경우를 고려하고, 가장자리에 도달했을 경우를 대비하여 위와 같은 코드를 추가해서 해결하였다.

2) 코드의 오류 발견

1 4 3

[입력] #### ##@# #*.#

answer = "IMPOSSIBLE"

if graph[ny][nx] -!= '#' and (nx == 0 or nx == X-1 or ny == 0 or ny == Y-1):
    return visited_s[y][x]

• 생각해보니 위의 코드가 있는데 For문 내부에 필요없는 중복코드가 있었고, 이것을 삭제하니 위의 반례도 통과되고 전체적으로 해결할 수 있었다.

💡 주어지는 예시 말고, 반례를 고민하는 습관을 들이자.

💡 특정 조건에 의해 탈출할 경우 잘 고민해보자

import sys
from collections import deque 

def bfs(curr_x, curr_y, target_x, target_y):

    dq = deque()
    dq.append((curr_x, curr_y))

    # 나이트 이동방향
    dx = [-2, -1, 1, 2, -2, -1, 1, 2]
    dy = [1, 2, 2, 1 , -1, -2, -2, -1]

    while dq:
        x, y = dq.popleft()
        for idx in range(8):
            nx = x + dx[idx]
            ny = y + dy[idx]

            if nx == target_x and ny == target_y:
                return graph[y][x]

            if 0 <= nx < I and 0 <= ny < I and graph[ny][nx] == 0:
                graph[ny][nx] = graph[y][x] + 1
                dq.append((nx,ny))

input = sys.stdin.readline

T = int(input())

for _ in range(T):

    I = int(input())
    graph = [[0] * I for _ in range(I)]

    curr_x, curr_y = map(int,input().split(' '))
    graph[curr_y][curr_x] = 1

    target_x, target_y = map(int,input().split(' '))
    graph[target_y][target_x] = 2

    if curr_x == target_x and curr_y == target_y:
        print(0)
        continue

    print(bfs(curr_x,curr_y,target_x,target_y))

• 위 문제도 일반적인 bfs 문제와 동일하였지만, 기존 상하좌우와는 다르게 나이트의 이동방향에 맞춰서 이동하는 문제였다. (나이트는 가로 2칸, 세로 1칸을 움직일 수 있다.)
• 결론적으로 시작점과 목적점까지 최소 얼마나 움직였는지를 갈 수 있냐 이기떄문에, BFS를 사용하였고, 이동할 때마다 graph의 값을 +1 시켜주면서 visited 배열도 생략해주고, 목적점까지의 경로도 구할 수 있었다.
• 추가적으로 입력받은 시작점과 목적점을 bfs()에 추가하여 넣어주어, 처음부터 dq에 시작점을 넣고, 탈출 조건으로 목적점을 넣어서 풀이하였다.

💡 오답 해결

for _ in range(T):

    I = int(input())
    graph = [[0] * I for _ in range(I)]

    curr_x, curr_y = map(int,input().split(' '))
    graph[curr_y][curr_x] = 1

    target_x, target_y = map(int,input().split(' '))
    graph[target_y][target_x] = 2

    if curr_x == target_x and curr_y == target_y:
        print(0)
        break

    print(bfs(curr_x,curr_y,target_x,target_y))

• 처음에는 가장 위에 보이는 예제 입출력값에만 집중하여, 시작점과 목적점이 동시에 들어오면 0을 출력하고 종료해주는 방식을 선언했다.
• 하지만 이는 시작점과 목적점이 동일한 경우가 가장 마지막에 나올때만 성립이 되어 자꾸 16퍼에서 오답이 발생하였다.
• 따라서 해당 경우가 나와도 0을 출력해주고 다음 테스트 케이스를 받아야하기 떄문에 break 에서 continue로 변경해서 정답을 맞추었다.

💡 3차원 BFS를 익혀보자

import sys
from collections import deque 

input = sys.stdin.readline

M, N, H = map(int,input().rstrip().split(' '))
visited = [[[False] * M for _ in range(N)] for _ in range(H)]
graph = [[list(map(int,input().rstrip().split(' '))) for _ in range(N)] for _ in range(H)]

dq = deque()

# 상하좌우위아래
dx = [0,0,-1,1,0,0]
dy = [1,-1,0,0,0,0]
dz = [0,0,0,0,1,-1]

for i in range(H):
    for j in range(N):
        for k in range(M):
            if graph[i][j][k] == 1 and visited[i][j][k] is False:
                dq.append((k,j,i))
                visited[i][j][k] = True

def bfs():

    while dq:
        x, y, z = dq.popleft()
        for idx in range(6):
            nx = x + dx[idx]
            ny = y + dy[idx]
            nz = z + dz[idx]

            if 0 <= nx < M and 0 <= ny < N and 0 <= nz < H and graph[nz][ny][nx] == 0 and visited[nz][ny][nx] is False:
                dq.append((nx,ny,nz))
                graph[nz][ny][nx] = graph[z][y][x] + 1
                visited[nz][ny][nx] = True

bfs()

day = 0

for q in graph: 
    for p in q:
        if 0 in p:
            print(-1)
            exit()
        else:
            day = max(day, max(p))

print(day-1)

• 위 문제는 앞선 토마토 문제와 거의 동일한 문제이다.
• 다만 앞선 문제와는 달리 x,y,z까지 고려를 해야한다는 점이다.
• 풀이방식은 기존 토마토 문제와 아주 동일하다. 제일 먼저 익은 토마토를 dq안에 넣고 확장해가는 동일한 방식을 사용하였다.
• 다만 조금의 차이점이라면, 기존 2차원과 다르게 3차원이다보니 ,dx,dy,dz까지 필요하다는 점이였고, 각 요소의 갯수가 6개가 된다는 점이였더.
• 그 외에 추가적으로, 한줄 코딩을 이용해서 for문 3개를 이용한 입력값 받기를 한줄로 선언했다.

  graph = [[list(map(int,input().rstrip().split(' '))) for _ in range(N)] for _ in range(H)]

💡 bfs 새로운 유형 (입력값이 숫자가 아님)

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
graph = []
normal_cnt = 0
special_cnt = 0

for _ in range(N):
    graph.append(list(input().rstrip()))

def bfs(a, b, color, is_special):

    dq = deque()
    dq.append((a,b,color))    
    visited[b][a] = True

    # 상 하 좌 우
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]

    while dq:
        x ,y, color = dq.popleft()
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]
            if 0 <= nx < N and 0 <= ny < N and visited[ny][nx] is False:
                # 일반인 경우
                if is_special == False and color == graph[ny][nx]: 
                    dq.append((nx,ny,graph[ny][nx]))
                # 적록색약인 경우
                elif is_special == True and (color in ['R','G'] and graph[ny][nx] in ['R','G']):
                    dq.append((nx,ny,graph[ny][nx]))
                elif is_special == True and color == 'B' and color == graph[ny][nx]:
                    dq.append((nx,ny,graph[ny][nx]))
                else:
                    continue

                visited[ny][nx] = True


visited = [[False] * N for _ in range(N)]

# 일반은 빨, 초, 파
for i in range(N):
    for j in range(N):
        if visited[i][j] == False:
            bfs(j, i, graph[i][j], False)
            normal_cnt += 1

visited = [[False] * N for _ in range(N)]

# 적록 색약은 빨(R) == 초(G), 파
for i in range(N):
    for j in range(N):
        if visited[i][j] == False:
            bfs(j, i, graph[i][j], True)
            special_cnt += 1

print(normal_cnt, special_cnt)

• 위 문제는 기존의 bfs와 접근은 같지만, 입력이 숫자형식이 아니고, 경우의 수가 R,B,G 총 3가지가 존재하였다.
• 또한 일반인의 경우에는 RGB이고, 적록색약의 경우에는 RB이기 떄문에, 2가지 케이스를 나눠서 진행하였다.
• bfs에 넣어줄 때, bfs()를 하나만 만들고, is_special를 통해서 적록색약인지 아닌지를 판단해서 넣어주었다.
• visited 배열을 일반을 거치고 나서 한번 더 초기화 해주었는데, 생각해보니 Visited배열을 숫자로 선언하고, 일반일 경우에는 0 -> 1, 적록색약일 경우에는 1 -> 2 로 가도록 하면 visited 배열을 한번 더 초기화할 필요가 없었을거 같다.

💡 코테 스터디에서 나온 기발한 풀이법

우진

elif is_special == True and (color in 'RG'and graph[ny][nx] in 'RG'):

• 위 코드와 같이 문자열로 'RG'로 선언해도 R과 G를 따로 보고 판단한다.
• 이 방식이 기존 나의 방식에서는 배열을 선언해서 했던 방식보다 메모리 적인 측면에서 더 좋을거 같다고 생각하였다.

💡 bfs 문제 중 정말 어려웠던 문제였다.. 풀이법을 빠르게 생각하는 것이 중요하다!

import sys
from collections import deque

input = sys.stdin.readline

R, C = map(int, input().split(' '))

graph = [list(input().rstrip()) for _ in range(R)]

# 상하좌우
dx = [0,0,-1,1]
dy = [1,-1,0,0]

dq = deque()
jihun_x, jihun_y = 0, 0

# 불 위치 저장
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'J':
            jihun_x , jihun_y = j, i
        elif graph[i][j] == 'F':
            dq.append((j,i, 'F', 0))

# 지훈 위치 저장
dq.append((jihun_x,jihun_y,'J', 0)) 

def bfs():

    cnt = 0

    while dq:
        x, y, val, cnt = dq.popleft()

        if val == 'J' and (x == 0 or x == C-1 or y == 0 or y == R-1):
            return cnt + 1

        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]

            if val == 'J':
                if 0 <= nx < C and 0 <= ny < R and graph[ny][nx] == '.':
                    graph[ny][nx] = 'J'
                    dq.append((nx,ny,'J', cnt + 1))
            else:
                if 0 <= nx < C and 0 <= ny < R and graph[ny][nx] == '.':
                    graph[ny][nx] = 'F'
                    dq.append((nx,ny,'F', 0))

    return "IMPOSSIBLE"

print(bfs())

• 이번 문제는 정말 오래걸렸고, 결국은 스터디에서 hint를 얻어서 풀게 되었다.
• 삽질을 정말 많이 했고, 간단하게 삽질해봤던 부분들을 정리해보겠다. 1) visited 배열을 사용해서 visited가 False,True로 체크하는 과정을 거쳤다 - 필요 X 2) cnt를 두고, 'J'일 경우에는 cnt += 1로 매번 경우의 수를 업데이트 하였다. - X ( 이 부분은 결국 최솟값을 구해야 하고, 모든 경로의 J의 경우 수를 전부 구하는 거여서 옳지 않다.) 3) 불보다 지훈을 먼저 dq에 추가하였다. - X ( Jihun이 갈 수 있는 가장 최소의 경로로 진행하려면 불의 경로를 먼저 진행해야한다.)

< 핵심 코드 >

1) 불, Jihun 저장 코드

dq = deque()
jihun_x, jihun_y = 0, 0

# 불 위치 저장
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'J':
            jihun_x , jihun_y = j, i
        elif graph[i][j] == 'F':
            dq.append((j,i, 'F', 0))

# 지훈 위치 저장
dq.append((jihun_x,jihun_y,'J', 0)) 

• jihun은 전체에서 1번밖에 없기 때문에, 해당 위치를 jihun_x, jihun_y에 저장한다.
• 불의 위치를 jihun보다 먼저 저장해야 하기 때문에, dq에 불에 대한 정보를 추가해준다. ( 불의 정보는 x위치, y위치, Fire/Jihun, 갯수 로 이루어져 있다.) ( 여기서 갯수가 추가된 것은 경로를 진행할 때마다, 경로가 1씩 증가해줘야 하기 떄문에)
• 불의 위치를 저장하고 나서, 지훈의 위치에 대한 정보를 dq에 추가해준다.

2) 종료 조건

if val == 'J' and (x == 0 or x == C-1 or y == 0 or y == R-1):
    return cnt + 1

• dq의 맨 앞부분의 val이 J라면, (즉, Jihun이라면) cnt + 1값을 return 해주면서 종료한다.

3) dq에서 Fire와 Jihun 처리

if val == 'J':
    if 0 <= nx < C and 0 <= ny < R and graph[ny][nx] == '.':
        graph[ny][nx] = 'J'
        dq.append((nx,ny,'J', cnt + 1))
else:
    if 0 <= nx < C and 0 <= ny < R and graph[ny][nx] == '.':
        graph[ny][nx] = 'F'
        dq.append((nx,ny,'F', 0))

• graph의 값을 J로 바꿔주면서, visited 배열을 대체하였다.
• Fire의 경우에는 불이 번지면 불의 공간이 고정이기 떄문에, graph의 값을 변경해주었다.
• 범주내에 포함되며, graph값이 .이여서 확장 가능하면 Jihun일 경우에는 해당 경로로 이동해주고, cnt를 1씩 더해주었다.

4) 조건 만족시 return과 만족 아닐 시 return

while dq:

  if val == 'J' and (x == 0 or x == C-1 or y == 0 or y == R-1):
      return cnt + 1

( 생략 )

return "IMPOSSIBLE"

• J가 범주에 만족하게 되면, 탈출하고 return 해주었다.
• 범주에 만족하지 못하고, 결국 dq가 다 비게 되면 IMPOSSIBLE을 return 해주었다. ( 결국 범주에 포함되지 못하면, #이나 F에 가로 막혔다는 것을 의미한다.)

💡 코테스터디에서 나온 기발한 접근법

import sys
from collections import deque

input = sys.stdin.readline
r, c = map(int, input().split())
graph = []

q_j = deque()
q_f = deque()

visited_j = [[0] * c for _ in range(r)]
visited_f = [[0] * c for _ in range(r)]

move = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1]
]

for i in range(r):
    temp = list(input())

    for j in range(len(temp)):
        if temp[j] == "J":
            q_j.append((i, j))
            visited_j[i][j] = 1

        elif temp[j] == "F":
            q_f.append((i, j))
            visited_f[i][j] = 1

    graph.append(temp)

def bfs():
    while q_f:
        x, y = q_f.popleft()

        for i in range(4):
            nx, ny = x + move[i][0], y + move[i][1]

            if 0 <= nx < r and 0 <= ny < c:
                if not visited_f[nx][ny] and graph[nx][ny] != "#":
                    visited_f[nx][ny] = visited_f[x][y] + 1
                    q_f.append((nx, ny))

    while q_j:
        x, y = q_j.popleft()

        for i in range(4):
            nx, ny = x + move[i][0], y + move[i][1]

            if 0 <= nx < r and 0 <= ny < c:
                if graph[nx][ny] != "#" and not visited_j[nx][ny]:
                    if not visited_f[nx][ny] or visited_f[nx][ny] > visited_j[x][y] + 1:
                        visited_j[nx][ny] = visited_j[x][y] + 1
                        q_j.append((nx, ny))

            else:
                return visited_j[x][y]


    return "IMPOSSIBLE"

print(bfs())

• visited 배열을 jihun용, fire용으로 따로 두어서 진행하였다.
• fire의 경우에는 이전 visited 배열의 값에 +1을 해주면서, Fire가 번지는 일수를 같이 표현해줘서, fire가 번져나갈 수 있는 경우의 수를 먼저 진행한다.
• Jihun의 경우에는 확장하면서, .인 경우에는 자동으로 진행할 수 있고, 만약 F인 경우에는 Jihun의 visited값과 비교해서 Jihun이 작으면 확장하면서 변환해준다. ( Fire의 visited가 jihun이 확장되는 visited보다 크다면, Fire가 확장되기 전에 Jihun이 해당하는 부분에 도달했다라는 의미이기 떄문에 확장이 가능하다.)

💡 BFS의 새로운 유형 익혀보자!

import sys
from collections import deque

input = sys.stdin.readline

M, N = map(int, input().split())

graph = []
visited = [[False] * M for _ in range(N)]
day = 0

for _ in range(N):
    graph.append(list(map(int, input().split())))

def bfs():
    dq = deque()

    # 익은 토마토의 위치를 미리 전부 저장해둔다.
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                dq.append((j, i))
                visited[i][j] = True

    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    while dq:
        x, y = dq.popleft()
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]

            if 0 <= nx < M and 0 <= ny < N and graph[ny][nx] == 0 and not visited[ny][nx]:
                dq.append((nx, ny))
                visited[ny][nx] = True
                graph[ny][nx] = graph[y][x] + 1

bfs()

for k in range(N):
    if 0 in graph[k]:
        print(-1)
        exit()
    day = max(day, max(graph[k]))

print(day - 1)

• 위 문제는 생각보다 삽질을 많이 한 문제였다..ㅎ
• 일단 입력이 0과 1, -1로 구성된 배열 형태로 들어오기도 했고, 최소 날짜를 출력해야 하기 때문에 BFS로 접근해봐야 겠다고 생각했다.
• 핵심 포인트는 기존 유형처럼 값이 1인 x,y를 돌아가면서 넣어주는 것이 아니라, 처음에 쭉 순회하면서 토마토의 위치를 dq에 넣어주는 것이다.
• 토마토의 위치를 처음에 dq에 넣어주고, 해당 시점들을 중심으로 확장하였고, 익은 날짜의 최소 날짜를 구해야함으로, 확장하면서(하루가 지날 때마다) +1을 넣어주었다.
• 마지막으로 배열을 쭉 돌면서 0이 있으면(즉, 안 익은 토마토가 있으면) -1을 출력해주고, 그렇지 않으면 가장 큰 값 (즉 최대한 많은 수의 토마토를 익혔을 날짜)을 출력해준다.

💡b

import sys
from collections import deque

input = sys.stdin.readline

N ,M = map(int,input().split(' '))
graph = []
visited = [[False] * M for _ in range(N)]

for _ in range(N):
    graph.append(list(map(int,input().rstrip())))

def bfs():

    dq = deque()

    dq.append((0,0,1))
    visited[0][0] = True

    # 상 하 좌 우
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    while dq:
        x, y, cnt= dq.popleft()

        # 목적지에 도달하면 종료
        if x == M-1 and y == N-1:
            return cnt

        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]

            if 0 <= nx < M and 0 <= ny < N and graph[ny][nx] == 1 and visited[ny][nx] == False:
                visited[ny][nx] = True
                dq.append((nx,ny,cnt+1))

print(bfs())

• 위 문제도 사실 일반적인 BFS의 유형 중 하나였다.
• 다만 최소의 칸수를 구해야하기 때문에, 어떤 방식으로 진행하면 좋을지 고민을 많이 하였다.
• 나는 따로 dq안에 (x좌표, y좌표, 현재위치에 도달하는데 걸린 비용) 이렇게 3가지를 넣어주면서 계산하였다.
• 핵심 포인트는 최종 위치가 (N,M)에 도달하면 바로 탈출해서 걸린 비용을 계산해야 한다.(bfs이기 때문에, N,M에 최솟값을 가진다.)

💡 코테 스터리에서 나온 기발한 풀이법

혜진

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
dist = [[-1] * m for _ in range(n)]

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    dist[x][y] = 0  # 시작점 거리 초기화

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 1 and dist[nx][ny] == -1:
                    queue.append((nx, ny))
                    dist[nx][ny] = dist[x][y] + 1
    return dist[n-1][m-1]+1

print(bfs(0, 0))

거리를 측정하는 dist배열을 따로 선언해서 움직일 떄마다 걸린 거리의 숫자를 하나씩 증가시켜주는 방식 => 생각해보면 그냥 graph에 바로 +1을 하여서 N,M에 도달했을떄의 숫자를 출력해도 괜찮을거 같다.

💡 BFS의 가장 기본적인 유형의 문제

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int,input().rstrip().split(' '))

graph = []
visited = [[False] * m for _ in range(n)]

# 총 그림수
cnt = 0
# 그림 넓이
maxSquare = 0

for _ in range(n):
    graph.append(list(map(int,input().rstrip().split(' '))))

def bfs(a,b):

    dq = deque()

    dq.append((a,b))
    visited[b][a] = True

    square = 1

    # 상, 하, 좌, 우
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    while dq:
        x, y = dq.popleft()
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]

            if 0 <= nx < m and 0 <= ny < n and graph[ny][nx] == 1 and visited[ny][nx] == False:
                dq.append((nx,ny))
                visited[ny][nx] = True                
                square += 1

    return square


for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and visited[i][j] == False:
            maxSquare = max(bfs(j,i),maxSquare)
            cnt += 1

print(cnt)

if cnt == 0:
    print(0)
else:
    print(maxSquare)

• 위 문제는 전형적인 BFS 유형의 문제였다.
• 이번 문제는 일단 입력값 자체가 BFS에 가깝다고 생각하였고, 가장 넓은, 가장 작은과 같은 최대나 최솟값을 요구할 경우 BFS를 먼저 고려해봐야 한다.
• 최대 넓이를 구하기 위해서 bfs를 통해 visited 값이 False이고, graph값이 1인 너비의 영역을 return 받아 max함수를 이용하여 매번 가장 큰 값으로 갱신하였다.
• 영역의 갯수를 구하기 위해서 BFS에 들어갈 떄마다 cnt + 1을 해주어 영역의 갯수를 구하였다.

💡 코테 스터디 중 나온 기발한 방식

우진님: 함수의 관점에서 보면 y,x인데, 표의 느낌으로 보면 x,y이므로, x,y로 만들어서 진행한다.

• 우선, 나는 풀이를 진행할 때, dq에는 (x,y)가 들어가는 것이 함수적인 측면에서는 맞기 때문에 bfs(j,i)로 넣어준다.
• 우진님의 경우에는 함수의 관점보다는 배열의 관점을 먼저봐서 입력받을 때, Y,X의 방식으로 받아서 bfs(i,j)를 넣어준다.