최근에 서비스를 하나 출시했습니다. 이름은 블링크라고 하고 AI기반 아카이빙 앱입니다. 꽤나 맛집이니, 한번씩 들러 주시면 좋겠습니다. 링크는 글 아래 첨부할게요🙂

“줄서는 맛집 블링크가 오픈을 했습니다”

목표는 맛있는 음식을 많은 사람들에게 제공을 하는 것입니다. 하지만 맛있는 음식을 제공하기 위한 재료는 값이 비쌌어요.

거덜(?) 날 수 없었던 사장은 감당할 수 있을 만큼만 손님을 받을 수 있는 웨이팅 시스템을 도입하기로 했어요.

진정한 맛집은 손님을 빈손으로 돌려보내지 않아요. 웨이팅을 등록한 손님들에겐 시간이 걸릴지언정 빠짐 없이 메뉴를 제공합니다.

네, 이 글은 블링크가 어떻게 웨이팅을 등록한 손님들의 요청을 누락 없이 대응하는 것에 대한 이야기입니다.

AI 사용료를 통제하고 싶다

블링크는 기본적으로 AI를 사용하는 서비스입니다. AI를 활용하여 유저들이 편하게 컨텐츠 링크를 아카이빙할 수 있도록 자동으로 내용을 요약/분류 하는 기능을 제공해요. 저희는 이러한 기능을 구현하기 위해 생성형 AI를 사용하기로 하였습니다. 이렇게 결정한 이유는 이미 구축된 모델을 사용하여 앱의 시장성을 빠르게 확인하기 위함이었어요.

하지만 생성형 AI에도 단점이 있었죠. 빠른 구축이 가능하다는 장점의 이면에 요청당 비용이 발생한다는 단점이 존재하였습니다. 저희는 사이드 프로젝트이기 때문에 비용이 충분치 못했고, 비용을 통제할 방법이 필요하였습니다.

타 서비스의 해결책

AI는 비용이 값비싼 도구에 해당합니다. 비용으로 고민이 되는 것은 비단 저희뿐만이 아닐것 같았어요. 그래서 타 서비스에서는 어떻게 대응하고 있는지를 확인해보았습니다.

Chat GPT

chat GPT는 AI를 활용한 대표적인 사례이죠. 자체적으로 개발한 AI인데도 불구하고, 어느정도 사용하게 되면 사용에 제한이 걸리도록 구현이 되어 있습니다(무료 계정 기준). GPU 소모가 많다보니, 자사 리소스임에도 불구하고 제한량을 걸어둔 것으로 보입니다.

특이점으로는, 재 사용 가능 시각을 설정함으로써 사용량을 제어하는 모습을 보인다는 겁니다.

원티드

원티드 서비스에서는 이력서를 AI가 분석해주는 서비스를 제공합니다. 원티드도 생성형 AI의 API를 활용하여 서비스를 제공한다고 되어있더군요. 그래서 그런지 API quota를 고려하는 듯한 플로우를 보여줍니다.

이력서를 작성하고, AI 이력서 리뷰를 신청하면 아래와 같은 화면이 노출되며 결과가 도착하면 알림을 보내준다고 알려줍니다. 내부적으로 비동기 처리한 후에 분석이 완료되면 알림으로 피드백을 주는 것을 보이는데, 최대 24시간까지 걸린다는 것으로 보아서는 메세지큐에 저장한 후 AI 사용량 제한을 설정하여 가능한 수 만큼만 메세지큐에서 fetch하여 동시처리하게 하는 것으로 보입니다.

이렇게 하면 분석에 소요되는 시간을 유저가 대기하지 않아도 되고, 최대 동시 처리 횟수를 설정함으로써 최대 AI 사용량을 원하는대로 제어할 수 있다는 장점이 있겠네요.

AI 서비스에 공통적으로 보이는 것은 사용량에 제한을 둔다는 것이었어요. 역시 다들 비용 과다 청구에 대한 대비책을 세워두었네요. 동일하게 AI를 사용하는 블링크도 대비책이 필요하다고 생각했어요.

결과적으로는, 원티드의 형태를 차용하기로 하였습니다. API를 통해 AI를 활용한다는 공통점 그리고 텍스트 분석과 분류/요약이 절차상 유사하다는 점을 고려하여 결정하였고, 위 구조를 어떤식으로 재현할 수 있을지를 설계하기 시작하였습니다.

어떤 규칙으로 손님을 받을 것인가?

기본적으로 선착순이 제일 합리적인 규칙일 것 같습니다. 최대 동시 처리량을 정해두고 그보다 초과되는 요청은 제한을 하면 좋을것 같습니다.

웨이팅 맛집으로 앱을 비유했으니, 최대 수 만큼만 요청을 받는 것은 워크인 손님을 받는 것으로 비유하면 될까요?ㅎ

그럼 이제 고민, 식당의 좌석 수 보다 초과된 워크인 손님들은 어떻게 처리를 해야할까요?

Rate Limit: 요청량 제한 알고리즘

위 문제를 해결하기 위해 2가지 알고리즘을 찾아보았습니다.

바로 누출 버킷 알고리즘과 토큰 버킷 알고리즘인데요. 둘 다 초과 요청을 처리하기 위해 고안된 알고리즘이기 때문에 두 알고리즘을 기반으로 구조를 설계해보고자 하였습니다.

토큰 버킷 알고리즘

토큰 버킷 알고리즘은 일정한 속도로 토큰이 버킷에 추가되며, 작업이 수행되기 위해서는 버킷에서 토큰을 소비하도록 함으로써 요청량을 제한하는 방식입니다. 즉, 토큰이 충분할 때만 요청이나 작업을 처리해요. 토큰이 없을 때에는 요청을 하면 반려가 됩니다.

식당으로 따지면, 테이크아웃 전문점에서 일정한 속도로 최대 N개까지 음식을 내고, 손님들이 순서대로 사가는 알고리즘이라고 할 수 있겠네요. 음식이 없는 경우의 손님은 돌려보내는 형태를 가지고 있어요.

누출 버킷 알고리즘

누출 버킷 알고리즘은 고정된 속도로 요청을 처리합니다. 고정된 사이즈의 큐에 요청을 담아두고 큐가 가득 차면 요청을 반려하는 알고리즘입니다.

이 케이스는 일정한 속도로 음식이 나오는 테이크아웃 전문점에서 최대 N명의 사람까지만 줄을 세우고, N+1명 부터는 돌려보내는 알고리즘으로 비유할 수 있을것 같아요.

좀 이상하지만? 또 길거리에 너무 긴 줄을 세워두면 민원이 들어올 수 있으니, 대충 최대로 줄 설 수 있는 인원을 정해둔거라고 합니다. 맛집의 비애죠(?)

두 알고리즘 중 하나를 선택해서 그대로 구현을 하고 싶었지만, 저희 서비스의 신뢰도를 위해 요청을 버려지는 상황을 만들 수는 없었습니다. 공교롭게도 두 알고리즘 다 수용량을 벗어나는 요청을 그대로 유실시켜버리더라구요.

그래서 두 알고리즘을 잘 혼합하여, 유실 없이도 대기열을 제한된 분당 처리량으로 처리 할 수 있는 알고리즘으로 개량해보기로 하였습니다.

그 결과,

⭐️누출 버킷 알고리즘의 큐 사용에서 착안하여 메세지큐에 요청을 담아두고, 메세지큐에 담긴 요청들을 토큰 버킷 알고리즘을 통해 fetch하게 구성함으로써 요청의 유실 없이 대기열을 소비할 수 있도록 개량⭐️ 할 수 있었습니다!

그렇게 탄생한 구조

설계한 구조를 구조도로 정리해보자면 아래와 같습니다.

1 - 클라이언트가 API 서버에 분석/요약할 링크를 요청으로 보낸다. 2, 3 - API 서버는 메세지큐에 담고 클라이언트에게 바로 응답을 한다. 4, 5, 6 - 잔여토큰 > 0 일 경우 Worker서버에서 메세지를 fetch하여 분석/요약을 처리한다. 7 - 클라이언트에 푸시를 보내 처리가 완료됨을 알린다.

API 요청에 대해서는 메세지큐에 담기만 하고 유저에게 빠른 응답을 줌으로써 유저가 요청을 기다리지 않도록 하고, 대신 요약이 완료되면 푸시를 보내 유저가 확인할 수 있도록 설계하였습니다.

모든 요약 요청은 메세지큐에 담아 유실되지 않도록 하였고, 토큰 버킷 알고리즘에 따라 메세지를 fetch함으로써 요청 누락을 방지하면서도 요청량에는 제한을 둔 구조를 완성할 수 있었습니다.

레시피

그럼 이제 이 구조를 어떻게 구현하였는지도 공유를 해보겠습니다.

일단 저는 메세지큐로는 SQS, 토큰을 담을 버킷으로는 Redis(elasticache)를 사용했어요. 그리고 AWS의 Elastic Beanstalk Worker를 사용하여 주기적으로 Redis에 N개의 토큰을 SET하도록 하였습니다.

SQS는 메세지의 개수와 관계없이 큐의 사이즈가 무제한으로 확장되며, 완전관리형으로 제공되어 빠르게 사용할 수 있고, 서버 자체를 AWS로 구성한 만큼 SQS와의 빠른 통합도 가능했기 때문에 선택하였습니다. 비교적 저렴한 가격은 덤이었고, 타 메세지큐 대비 낮은 TPS도(300 TPS) 예상 사용량 대비 충분할 것으로 판단하였습니다.

토큰의 경우 요청당 하나가 정확하게 소비되어야하기 때문에 동시성이 중요한 이슈라고 생각하였습니다. 그래서 빠른 응답속도임에도 동시성 이슈를 방지할 수 있는 Redis를 사용하기로 하였습니다. Redis는 Lua Script를 활용해 동시성 문제를 해결할 수도 있고, atomic operation인 incrby 명령어를 활용하여 동시성 이슈를 피해 토큰을 감소시키는 것도 용이하기 때문에 Redis를 선택하였습니다.

Elastic Beanstalk Worker 같은 경우에는 cron을 설정해두면 자체 메세지큐를 활용하여 다중 서버 환경일때에도 cron 로직이 단 한번 동작시키는 것을 보장되기 때문에 안정성을 높게 평가하여 선택하였습니다.

sqs 설정

일단 SQS Config를 만들어줍니다.

@SqsListner를 사용하여 message를 가져올 예정이기 때문에 아래와 같이 설정을 하였습니다. 이 데코레이터를 사용해서 가져오는 경우 연동된 함수가 예외없이 수행되면 sqs에서 message를 자동으로 삭제합니다.

저는 메세지가 삭제되는 시점을 제가 컨트롤하고 싶어 acknowledgementMode를 MANUAL로 설정하였습니다. 이렇게 설정을 하면 acknowledgement.acknowledge() 를 함수에서 호출해주어야 정상적으로 메세지가 삭제됩니다.

@Configuration
class AwsSQSConfig(
    @Value("\${spring.cloud.aws.credentials.access-key}")
    private val awsAccessKey: String,
    @Value("\${spring.cloud.aws.credentials.secret-key}")
    private val awsSecretKey: String,
    @Value("\${spring.cloud.aws.region.static}")
    private val region: String,
) {
    /**
     * AWS SQS 클라이언트
     */
    @Bean
    fun sqsAsyncClient(): SqsAsyncClient {
        return SqsAsyncClient.builder()
            .credentialsProvider {
                object : AwsCredentials {
                    override fun accessKeyId(): String {
                        return awsAccessKey
                    }

                    override fun secretAccessKey(): String {
                        return awsSecretKey
                    }
                }
            }
            .region(Region.of(region))
            .build()
    }

    /**
     * SysAsyncClient를 사용하여 실제 메세지를 수신하는 역할을 함
     * 메세지 수신 서버에만 설정하면 됨
     */
    @Bean
    fun defaultSqsListenerContainerFactory(sqsAsyncClient: SqsAsyncClient): SqsMessageListenerContainerFactory<Any> {
        // 정확한 타입과 별개로 메세지의 json 형식만 일치하면 수신부에서 역직렬화할 수 있도록 messageConverter 설정
        val messageConverter = SqsMessagingMessageConverter()
        messageConverter.setPayloadTypeMapper { null }

        return SqsMessageListenerContainerFactory
            .builder<Any>()
            // 수동으로 메세지를 삭제하기 위해 AcknowledgementMode.MANUAL로 설정
            .configure { opt ->
                opt.acknowledgementMode(AcknowledgementMode.MANUAL)
                opt.messageConverter(messageConverter)
            }
            .sqsAsyncClient(sqsAsyncClient)
            .build()
    }

    /**
     * 메세지 발송을 위한 SQS 템플릿 설정
     * 메세지 발신 서버에만 설정하면 됨
     */
    @Bean
    fun sqsTemplate(): SqsTemplate {
        return SqsTemplate.newTemplate(sqsAsyncClient())
    }
}

API 서버에서는 아래와 같이 메세지를 적재하는 코드를 작성하여 사용했습니다. message는 json으로 직렬화되며, message를 fetch하는 코드에서는 동일한 형태의 class를 생성하여 역직렬화되도록 해야합니다.

@Component
class FeedSummarizeMessageSenderImpl(
    @Value("\${spring.cloud.aws.sqs.summary-request-queue.name}") private val queueName: String,
    private val sqsTemplate: SqsTemplate,
): FeedSummarizeMessageSender {

        // 메세지를 적재하는 함수
    override fun send(message: FeedSummarizeMessage): SendResult<FeedSummarizeMessage> {
        return sqsTemplate.send { to ->
            to
                .queue(queueName)
                .payload(message)
        }
    }
}

Worker 서버에서 메세지를 처리하는 부분은 아래와 같습니다. summarizeRequestLimiter.decreaseToken() 를 호출함으로써 로직 처리전 토큰을 하나 감소시키고, 토큰이 남아있었으면 로직을 수행하고, 메세지를 삭제합니다. 토큰이 없었을 경우에는 acknowledgement.acknowledge() 가 호출되지 않기 때문에 메세지가 삭제되지 않고 다시 fetch 될 수 있게 합니다.

sqs는 메세지를 수신할때 바로 큐에서 삭제하는 대신 메세지가 안보이도록 처리합니다. 그리고 acknowledgement.acknowledge() 가 호출이되는 시점에서야 메세지가 삭제됩니다.

acknowledgement.acknowledge() 처리되지 않는 메세지는 visibiliy timeout 이후에 큐에 다시 나타나 재 수신이 가능해집니다.

@Component
class SummaryRequestListenerImpl(
    private val feedSummarizerService: FeedSummarizerService,
    private val summarizeRequestLimiter: SummarizeRequestLimiter
) : SummaryRequestListener {

    @SqsListener("\${spring.cloud.aws.sqs.summary-request-queue.name}")
    override fun summarizeFeed(
        message: Message<FeedSummarizeMessage>,
        @Headers headers: MessageHeaders,
        acknowledgement: Acknowledgement
    ): PromptResponse? {
        // TOKEN이 남아있을 때에만 요청을 처리한다.
        if (summarizeRequestLimiter.decreaseToken() > 0) {
            // TODO 이 메서드에 요약 처리 로직을 추가해야함. 아래 메소드 구현 필요.
            val payload = message.payload
            feedSummarizerService.summarizeFeed(payload)

            // 정상적으로 요청을 처리한 경우에만 메세지큐에서 요청을 삭제한다.
            acknowledgement.acknowledge()
        }
        return null
    }
}

SummarizeRequestLimiter는 RedisClient를 활용하여 아래와 같이 구현하였습니다. decreaseToken는 decr 메소드를 활용해 redis의 토큰 값을 1감소 시키는 함수입니다.

@Component
class SummarizeRequestLimiterImpl(
    private val redisClient: RedisClient
): SummarizeRequestLimiter {

    val REFILL_TOKEN_COUNT = 15

    override fun decreaseToken(): Long {
        val remainCount = this.redisClient.decr(RedisKey.SUMMARIZE_REQUEST_TOKEN_COUNT.name).let { it ?: 0 }

        return remainCount
    }

    override fun refillToken() {
        this.redisClient.set(RedisKey.SUMMARIZE_REQUEST_TOKEN_COUNT.name, REFILL_TOKEN_COUNT.toString())
    }
}

worker 크론으로 토큰 리필

토큰을 다시 채워주는 주기적 작업을 처리하기 위해 Elastic beanstalk worker의 cron 기능을 사용하였습니다. api를 만들어두고, cron.yaml에 cron 규칙을 정의해주면 내부적으로 cron 규칙에 맞게 api 호출하여 주기적 작업이 처리되게 합니다.

저는 아래와 같이 Controller를 구성하고 cron.yaml을 추가하였습니다.

@RestController
@RequestMapping("/feed-summarizer")
class FeedSummarizerControllerImpl(
    private val feedSummarizerService: FeedSummarizerService
): FeedSummarizerController {

    @PostMapping("/refill-token")
    override fun refillToken(): ResponseEntity<Unit> {
        this.feedSummarizerService.refillToken()

        return ResponseEntity.ok().build()
    }
}

# cron.yaml

version: 1
cron:
  - name: 'refill token'
    url: '/feed-summarizer/refill-token'
    schedule: '* * * * *'

테이스팅

API를 호출하여 정상적으로 요청이 처리되는지 확인해봅시다.

토큰이 존재하는 경우

이렇게 링크를 입력하면

푸시와 함께 아래와 같이 분류 폴더와 키워드, 요약 내용이 저장됩니다.

Redis의 토큰값도 정상적으로 하는 것을 확인할 수 있었습니다. 토큰 최대값을 15로 설정해두었는데, 9까지도 잘 감소하는군요.

토큰이 없는 경우

토큰이 0일 경우에도 실험을 해보겠습니다.

연달아서 3개의 요약 요청을 보내보면,

토큰 값이 -3으로 감소하고

메세지큐에는 3개의 메세지가 남아있는 것을 확인할 수 있습니다. 토큰이 없을 경우 요청이 잘 제한 되는군요!🎉

Result

이제 저희는 AI의 최대 지출 비용을 컨트롤할 수 있는 권한을 얻었습니다. 비용 폭탄의 두려움에서 자유로워졌어요!

아래와 같은 공식으로 N을 조정함으로써 수도꼭지를 잠구고 풀듯 비용을 유연하게 제한할 수 있게되었습니다.

월별 최대 AI 사용량 지출 = 분당 토큰의 개수(N) * AI 1회 호출 비용 * 30

위와 같은 과정을 통해 요청을 유실없이 처리하면서도, 분당 처리량에 제한을 두어 비용효율적·안정적으로 요청을 처리하는 구조를 설계하고 구현할 수 있었습니다.

API에 처리량을 제한하고자 하는 니즈는 꽤나 일반적인것 같습니다. 위와 같은 구조에 비즈니스 로직만 구현하여 추가한다면 다들 어렵지 않게 처리량 제한 구조를 구현하실 수 있을 것이라고 생각합니다.

물론 아직 개선할만한 포인트는 좀 더 있을것 같습니다. 토큰 유무와 관계 없이 메세지큐에서 일단 메세지를 fetch하고 보니 메세지큐의 불필요한 요청이 꽤나 발생하는 것 같습니다. 이 부분은 좀 더 개선할 수 있을지 고민해봐야겠네요. 좀 더 추상화를 해서 인프라와 비즈니스 로직만 추가하면 바로 처리량 제한 로직을 붙일 수 있도록 개선하는 것도 좋은 과제가 될 것 같아요.

개인적으로 만족스러운 점은 문제를 확실히 정의하고 논리적인 사고 과정을 통해 문제를 풀어냈다는 점인것 같습니다.

문제를 정확히 정의한 후 필요한 지식들을 파악하고 새롭게 습득하여 빠르게 원하는 결과를 만들어 냈다는 점에서 개발자로서 한 발짝 성장한 것 같아 뿌듯하네요🙂

이 글이 비슷한 고민을 하고 있는 또 다른 개발자들에게 도움이 되었으면 좋겠습니다. 긴글 읽어주셔서 감사합니다!🤩

가기 전에 스토어 링크 하나만 첨부하고 하겠습니다. 한번씩 사용해보시고 피드백 달아주시면 매우 감사하겠습니다.

• ios
• android

개빠르게 해야함

최근에 스크럼을 하면서 트랜잭션에 대한 이야기를 나누었는데, 트랜잭션을 사용할때 간과하고 있었던 점을 깨닫게 되어 공유해보려고 한다.

트랜잭션안에 비즈니스 로직을 넣어도 될지에 대해 고민해보신분?

회사에서는 매일 스크럼을 진행한다. 간단하게 업무 내용을 공유하고, 논의해야하거나 고민중인 문제들을 같이 얘기해보곤한다. 오늘도 여느때와 다름 없는 스크럼이었는데, 색다른 주제가 나왔다. 바로 트랜잭션 안에 비즈니스 로직을 넣어도 될지 말지에 대한 주제 였다.

발단은 이러하였다.

회사에서는 Nestjs와 ORM으로 prisma를 주로 사용한다. prisma에서는 트랜잭션을 2가지 방법으로 지원하는데, 그 중 어떤 방법을 사용할지에 대한 판단이 쉽지 않다는 것이었다.

prisma에서 transaction을 사용하는 방법은 쿼리를 함수들을 리스트로 받아 트랜잭션 처리하는 방법과, 트랜잭션의 인자로 익명 함수를 받아 그 안에 트랜잭션에서 처리하고 싶은 쿼리들을 넣어 실행하는 방법이 있다. 코드로 예시를 들어보자면은 아래와 같다.

예제

첫번째 방법을 코드로 예를 들어보자면 아래와 같다.

const [posts, totalPosts] = await prisma.$transaction([
  prisma.post.findMany({ where: { title: { contains: 'prisma' } } }),
  prisma.post.count(),
])

$transaction이 트랙잭션을 적용하는 메소드인데, 인자로 함수의 리스트를 받아 전달 받은 함수를 모두 하나의 트랜잭션에서 처리한다.

이어서 두번째 방법의 예시이다.

prisma.$transaction(async (tx) => {
    // 1. Decrement amount from the sender.
    const sender = await tx.account.update({
      data: {
        balance: {
          decrement: amount,
        },
      },
      where: {
        email: from,
      },
    })

    // 2. Verify that the sender's balance didn't go below zero.
    if (sender.balance < 0) {
      throw new Error(`${from} doesn't have enough to send ${amount}`)
    }

    // 3. Increment the recipient's balance by amount
    const recipient = await tx.account.update({
      data: {
        balance: {
          increment: amount,
        },
      },
      where: {
        email: to,
      },
    })

    return recipient
  })

$transaction 메소드가 이번엔 익명함수를 인자로 받아 단순히 함수를 트랜잭셔널하게 처리한다.

비교

개인적으로 첫인상은 두번째 방법이 좋아보였다. 다들 비슷한 생각이지 않을까?

두번째 방법을 사용하면 내가 수행시키고 싶은 로직을 그대로 함수에 담아 인자로 넘기면 된다. 어찌보면 트랜잭션을 사용하지 않는 느낌이 들기도 한다. 그냥 일반 함수를 실행시키는데 알아서 트랜잭션이 되는 그런 마법같은 느낌?

하지만 두번째 방법에는 커다란 문제점이 있다. 바로 쿼리와 쿼리 결과를 서버와 DB가 주고 받는 동안에도 트랜잭션이 지속되고 있다는 점(...!)이다.

이것이 그렇게 큰 문제가 되냐고? 큰 문제가 된다. 왜냐면 트랜잭션이 지속되는 동안 락이 걸리기 때문이다. 만약 트래픽이 많은 공간인 경우 동시다발적인 요청이 수시로 들어올것인데, 각 요청마다 락이 걸린다면 대기시간이 선형으로 증가할것이다.

물론 이는 트랜잭션 공통이긴 하나, 두번째 방법 처럼 쿼리 함수 뿐만 아니라 어떤 로직이든 들어가는 것이 가능한 경우 쿼리 실행 시간이 아닌 다른 원인으로 트랜잭션이 종료되기까지의 시간이 증가하는 것이 너무나도 가능하다.

그림으로 표현하면 이렇게 표현할 수 있을것 같다.

스레드 1이 DB와 티키타카하는 동안 스레드2는 하염없이 기다릴 수 밖에 없다. 만약 스레드3가 생긴다면 얘는 또 스레드2를 목빠져라 기다릴것이다🥲.

그에 반해,

첫번째 방법은 트랜잭션 안에서 서버와 티키타카하는 것 없이 DB에서 트랜잭셔널하게 쿼리만 수행하고 결과만 서버에 던져주면 되기 때문에 상대적으로 안전하다고 볼 수 있다.

하이패스와 대면결제

현실에서 예를 들어보자면 고속도로의 하이패스와 대면 결제로 비유할 수 있지 않을까

차가 엄청 많은 명절 고속도로를 상상해 보았을때, 하이패스는 단 한번의 상호작용으로 슝하고 결제가 가능하다. 그와 반면에 대면 결제는 티키타카가 많다. _인사하고, 카드 결제인지 물어보고, 현금이면 거스름돈 세고.._🤦‍♂️

동시처리가 되지 않으니, 줄을 설수 밖에 없고, 앞에 차의 용무가 길어질 수록 뒷 차의 대기 시간은 길어져만 간다. 물론 대면 결제는 하이패스보다 다양한 요구사항을 충족할 수 있겠지만, 하이패스로 가능한 요구사항이라면 하이패스를 사용하는게 더 이득일것이다.

사실 저는 명절에 고속도로에 가질 않습니다.

그렇기 때문에 트래픽이 많은 환경이라면 두번째 사용을 지양하는 것이 좋을 것이라고 팀장님이 조언을 해주셨다. 덧붙여서 트랜잭션은 빠르게 실행하고 빠르게 끝낼 수 있는 확신이 있을때에만 사용하는게 좋다고 말씀해주셨다.

예시를 prisma라는 ORM 환경에 국한하여 제시하였지만, 다른 ORM에서도 충분히 적용될 수 있는 사항이지 않을까 한다. 특히, ORM은 아니지만 raw query를 사용하는 환경에서는 더욱 더 잘 발생할 수 있는 환경이 아닐까

결론

트랜잭션=락이라는 인식을 확실히 가져야할 것 같다. 연속적으로 실행되어야하는 쿼리를 짜야할때, 중간에 실패하면 모두 없던일로 돌리고 싶기에, 마법을 바라는 마음으로 트랜잭션을 찾게되더라.

물론 트랜잭션을 안 쓸 수는 없겠지만, 안쓰면 너무 위험할때(ex. 결제) 말고는 최대한 서버 단에서 에러에 대한 후처리를 하는것이 성능과 안정성 사이의 가장 좋은 타협이지 싶다. 또는 에러가 발생하는 것 자체는 감수하고 그 에러에 대한 대응 방법을 최대한 쉽게 하는 것도 고려해봄직 할것 같다.

그래서 내린 오늘의 찐 결론

➡️ 트랜잭션이 실행되는 동안에는 쿼리만 실행되도록 하자. 그리고, 트랜잭션 사용은 최대한 피하자(특히 트래픽이 많은 환경). 일단 서버에서 해결해보고 정 불가피하면 그 때 고민해보자.

무심코 쓴 솔루션에 메인테이너가 이모지 눌러주고간 썰

⚡️Prisma라고 아시나?

작년에 회사에서 프로젝트를 새로 배정 받으면서 Prisma라는 orm을 새로 쓰게 되었어요.

보시다시피, 차세대 typescript-Nodejs ORM이라는 정체성을 가진 아이입니다. 쿼리 빌더의 형태로 꽤나 직관적으로 DB 데이터를 가져올 수 있는 인터페이스를 제공하더군요.

또한 이미 만들어진 DB를 보고 자동으로 prisma에서 사용할 수 있도록 스키마를 만들어주는 추출해주는 기능도 꽤 쏠쏠했습니다. 그리고 이 기능이 구 서버를 새로 마이그레이션해야했던 저희의 서비스에게는 꽤 매력적이었_(다고 추측하고 있🙄)_어요.

다만..

개인적으로 원하는 기능을 지원하지 않는 경우가 종종 있었습니다. 예를들어 count 쿼리를 날릴 때 distinct로 중복을 없애고 싶었는데... 안되더라구요...?(그리고 다른 사람들도 답답했는지 이슈 제기함ㅎhttps://github.com/prisma/prisma/issues/4228)

이러한 점들 때문에 공식문서에 명시되어있는 것 이외의 것을 해보려고 하면 "과연 이걸 지원할까...?"라는 스트레스가 있었습니다.

ps. 그래서 그런지 prisma가 raw 쿼리를 잘 지원하긴 해요(아마 본인들이 제공하지 않는 부분들은 직접 쿼리를 날리라는 뜻이겠죠?), 근데 raw 쿼리를 적극 사용할거면 ORM을 쓰는 이유가 퇴색되지 않을까?라는 개인적인 의견이에요.

그리고 큰 이슈를 만나다🤦‍

가장 치명적인 이슈였던 것은 prisma가 "0000-00-00 00:00:00" 형식의 DateTime을 지원하지 않는다는 것이었어요. 해당 값이 쿼리 결과에 포함이 되면 그 행 조회가 되지 않는것이 아니라 예외가 터지면서 쿼리 결과를 모두 확인할 수 없었습니다.

저는 2017년에 출시된 Mysql5.7 버전의 DB를 쓰고 있었어요. 그때에는 "0000-00-00 00:00:00"과 같은 형식의 DateTime도 퍽 잘 사용했었나봐요. 그래서 저 문제가 아주 자주 터졌답니다.

이에대한 해결책으로 NO_ZERO_DATE이라는 옵션을 DB에 global로도 설정해보고 url파라미터도로 전달해보았는데, DB에 연결할때 prisma에서 내부적인 커넥션을 새로 생성하는지 잘 동작이 되지 않았습니다.

사용하는 Mysql 버전을 호환시키기 위한 옵션 마저 prisma에서는 제공하지 않아서...

다른 대책이 필요했습니다...!

📕해결책을 찾다

근본적으로 문제를 접근해 보았습니다. 불러오는 데이터가 문제라면은 그 데이터를 안가져오면 되는게 아닌가 싶었습니다.

"0000-00-00 00:00:00"이라는 형식이 문제면 해당 값을 null로 바꿔서 가져오면 어떨까라는 접근을 해보았습니다. 팀장님과의 논의 끝에 generated column을 도입하는 방안을 고안했어요.

사실 읽어오지 못하는 값을 null로 UPDATE 한다면 문제가 해결되긴해요. 하지만 Production DB에 대규모로 업데이트를 하는 행위는 굉장히 리스크가 있다고 판단했습니다. 그래서 최대한 기존 칼럼을 안건드리는 방향으로 가닥을 정했어요.

generated column

generated column이란 말 그대로 임의로 생성된 컬럼을 말합니다. 존재하는 값으로부터 새로운 칼럼을 만들 수 있습니다. 엑셀에서 함수가 적용된 열이라고 생각하면 편할것 같아요.

generated colum에는 VIRTUAL 타입과 STORED 타입이 있습니다. VIRTUAL 타입을 사용할 경우, 기존 칼럼에 영향도 주지 않고 원하는 데이터를 읽어올 수 있을 뿐만 아니라, 가상으로 존재하는 칼럼이라 실제 DB에는 별다른 영향을 줄 수 있어요.

저는 이 기능을 사용해서 데이터를 똑같이 갖되, 문제가 되는 데이터("0000-00-00 00:00:00" 형식의 날짜 데이터) 인 경우 null을 갖도록 하는 가상 칼럼을 만들었어요.

그리고 문제가 되는 칼럼 대신에 새로 만든 가상 칼럼을 읽어 오는 방식으로 문제를 해결했습니다👏

📑해결책을 공유하다

사실 이 문제는 prisma에서 꽤나 유서 깊은 이슈였어요. 2019년에 처음 이슈가 등록된 이후로 여태까지 많은 사람들이 고통 받고 있었습니다.

사람들이 내놓은 해결책은 대부분 "0000-00-00 00:00:00인 데이터를 null로 업데이트 해라.", "raw query를 사용해라" 였어요. 근데 이러한 방법들은 전부 리스크가 있고, orm을 사용하는 의미가 퇴색되는 해결방법이라 좋아 보이지 않았어요.

이러한 방법들보다 제가 사용한 방법이 DB 데이터를 건드리지 않아 안전하고, orm도 온전히 쓸 수 있는 최선의 방법이라고 생각했어요.

그래서 처음으로 한번 github 커뮤니티에 공유해보기로 했습니다...!

아래는 제가 실제로 prisma github에 올린 코맨트입니다. 없는 영어 실력 긁어와서 솔루션을 작성해올려보았답니다 헤헤

https://github.com/prisma/prisma/issues/5006#issuecomment-1224036491

이모지도 남았어요. 적어도 5명의 사람에겐 도움이 되었다는거겠지...?ㅎ

메인테이너의 이모지를 받다🎉

사실 글을 올린지는 꽤 됐어요. (작년 8월쯤 올렸었나?🤔) 올려놨던 글의 근황이 궁금하여 최근에 다시 들어가봤는데 뭔가 기시감을 느꼈습니다.

이 분 이름을 어디서 봤는데 어디서 봤냐면은

prisma 메인테이너신데요...?

https://github.com/janpio

그래도 꽤 투자 많이 받고 유명한 오픈소스인데... 그런곳의 메인테이너가 내 댓글 보고 이모지 달아줬다고 생각하니까... 뭔가 신기하고... 얼떨떨하고... 막그럼...😵‍💫 💫

신난다🎵

첫 github 커뮤니티 활동이었는데, 그냥 지나가는 댓글 하나 달았다고 생각했는데, 첫 시도에 메인테이너가 반응해준거면 꽤나 좋은 스타트가 아닐까??

맘만 먹으면 github 같은 개발자 커뮤니티에서 활동하는것도 생각보다 할만 할것 같다는 자신감을 얻은 경험이었습니다.

오픈소스에 컨트리뷰션을 해보는 것이 제 목표 중 하나에요. 목표긴한데 여태 엄두도 못 낸채 막연한 꿈으로 방치두었어요. 오픈소스는 감히 넘볼 수 없다는 위압감이 있었는데, 이번 경험을 통해 그런게 많이 사라진 것 같습니다. _그래요 뭐 오픈 소스도 사람이 만든건데 뭐 다 완벽하겠슴까 그 사람들도 사람이겠지요 뭐 _

다음에 한놈 잘 못 걸리면 바로 PR날린다 는 마인드로 살아보려구요. 헿

(+ 인용도 해줬는데..?)

다른 이슈 중에 generated column을 지원해달라는 이슈가 있었나봄. 그래서 "다른 사람들은 이케 쓰드라~@" 라는 식으로 내 글도 다른 이슈에서 인용해줌ㄷㄷ 😳 나... 뭐...돼..?

https://github.com/prisma/prisma/issues/6336#issuecomment-1492429927

Nest에서 passport로 인증 구현할 일이 생겼는데, 죄다 jwt 예제 밖에 없더라❗️ 다른 strategy 예제 찾아보다 빡쳐서 제가 알아낸 내용 제가 올리려구요.👿

아니 요즘같은 세상에 자료가 하나도 없는게 말이 되나요?

회사에서 NestJS로 API 서버를 구현하던 중, 인증필터를 구현하는 작업을 하게 되었습니다.

Nest는 node 기반이고, node에는 이미 너무 유명한 인증 라이브러리가 있자나요. 바로 passport!

그래서 저도 passport를 사용해서 인증을 구현하려고 했습니다. 다행히 NestJS 공식 문서에 passport를 사용해서 인증을 구현하는 예제가 있습니다. 그런데....

예제에서는 passport-jwt를 사용하네요. jwt 좋죠... 근데 저는 jwt가 아니라 단순 액세스 토큰을 발급하여 커스텀 인증 로직을 태우는 작업을 해야했습니다. 공식 문서 예제가 jwt로 되어 있어서 그런지... 다른 레퍼런스를 찾아보면 전부 jwt로 인증을 구현하는 방법만 나오고 다른 전략을 사용하는 예제는 잘 안나오더군요...

그래서...

결국 Github에 올라와있는 NestJS에서 passport를 편하게 쓸 수 있도록 추상화해놓은 nest/passport, 그리고 제가 쓰려는 passport 전략인 passport-http-bearer의 소스코드를 하나하나 뜯어보기로 했습니다...

그리고 너무 관련 자료가 없어서 너무 화가 내서 제가 공유하려구요!😡

코드를 뜯어봅시다

아래의 클래스는 요청이 들어왔을 때, 인증을 처리하는 부분이고. async validate() 함수가 호출되어 인증 여부를 판단하게 됩니다. 이 클래스를 구현한 후 미들웨어단에 등록하면 요청이 올 때마다 인증 여부를 체크할 수 있죠.

이 클래스는 각 passport 라이브러리의 Strategy를 상속을 받는 것 보니, 각 strategy에 맞게 구현해야한다는 것을 유추해볼 수 있습니다.

https://docs.nestjs.com/security/authentication#implementing-passport-jwt

코드를 보면 validate는 인자로 payload를 받습니다. 대충 유추를 해보면 payload라는 인자는 요청에서 jwt를 받는 것 같아요.

자 그럼 이것은 passport-jwt를 사용할 때의 상황이고, 그렇다면 여기서 생기는 궁금점이

1) 다른 passport 전략을 사용할 때에는 validate는 어떤 인자를 받는가?

였어요. 예제가 jwt밖에 없다보니, 다른 passport 전략을 사용했을 때에는 validate(payload:any)라는 형태로 사용하면 되는지 장담을 할 수가 없으니깐요.

그리고 constructor를 봤을 때, 부모 생성자에 여러 jwt를 가져오는 방법에관련된 여러 옵션들을 주는 것 같은데, 그러면

2) 다른 전략을 사용할 때에는 나는 어떤 옵션을 주어야하는가?

라는 의문 또한 저를 여권지옥으로 떨어뜨린 주범이었죠.

이러한 의문을 해결하려면 저 클래스가 내부적으로 어떤 인풋을 허용하고 어떻게 동작하는지를 알아야했어요.

그래서 하나하나 함수의 원형을 찾아보며 (그리고 이를 바득바득 갈면서🦷, 아니 이세상에 사람이 얼마나 많은데 이거 하나 정리해 놓은 사람이 한명도 없냐고. 아니 솔찍히 화가 나지 않아요? 누가 한명만 공유를 해놨으면 금방 할거를 며칠째 주구장창 삽질하고 있는데. 하지만 화를 내서 달라지는게 없다는걸 알면서 현타를 느끼며...^^)

하하...^^ 오픈소스를 뜯어봤습니다ㅎㅎ

일단 validate가 내부적으로 어떻게 돌아가는지는 PassportStrategy라는 클래스를 뜯어봄으로서 확인할 수 있었습니다.

//auth.jwt.strategy.ts
...
import { PassportStrategy } from '@nestjs/passport';
...

@Injectable()
export class JwtStrategy extends PassportStrategy(Strategy) {
  ...
}

PassportStrategy는 저희가 구현하려는 클래스가 상속을 받는 클래스입니다. import를 보고 nestjs/passport를 Github에서 찾아봤죠. 해당 리포지토리에서 validate를 검색했더니 아래와 같은 코드를 찾을 수 있었습니다.

//passport/lib/passport/passport.strategy.ts 

import * as passport from 'passport';
import { Type } from '../interfaces';

export function PassportStrategy<T extends Type<any> = any>(
  Strategy: T,
  name?: string | undefined
): {
  new (...args): InstanceType<T>;
} {
  abstract class MixinStrategy extends Strategy {
    abstract validate(...args: any[]): any;

    constructor(...args: any[]) {
      const callback = async (...params: any[]) => {
        const done = params[params.length - 1];
        try {
          const validateResult = await this.validate(...params);
          if (Array.isArray(validateResult)) {
            done(null, ...validateResult);
          } else {
            done(null, validateResult);
          }
        } catch (err) {
          done(err, null);
        }
      };
      /**
       * Commented out due to the regression it introduced
       * Read more here: https://github.com/nestjs/passport/issues/446

        const validate = new.target?.prototype?.validate;
        if (validate) {
          Object.defineProperty(callback, 'length', {
            value: validate.length + 1
          });
        }
      */
      super(...args, callback);

      const passportInstance = this.getPassportInstance();
      if (name) {
        passportInstance.use(name, this as any);
      } else {
        passportInstance.use(this as any);
      }
    }

    getPassportInstance() {
      return passport;
    }
  }
  return MixinStrategy;
}

하나씩 해석해보겠습니다...

이 함수는 인자로 T 템플릿을 받아요(Strategy: T). 사용하는 형태로 보면 T는 사용하려는 passport의 Strategy가 되겠네요! 오 이 클래스에 validate가 있어요! 저희가 찾던 validate인것 같습니다. 이 validate가 어디에서 사용되는지 조금 더 보는게 좋을것 같아요.

이 클래스는 내부에 Strategy를 상속 받는 MixinStrategy라는 inner 클래스가 정의되어 있네요. 아래 return을 보니 _PassportStrategy_라는 함수는 _MixinStrategy_라는 클래스를 리턴해요. 이것으로 알 수 있는 점은, 저희가 위에서 실제로 상속을 받았던 클래스는 MixinStrategy였다는 것이죠!

validate가 호출되는 것은 바로 이 클래스의 constructor의 callback 함수입니다. 이 callback함수는 super(...args, callback)이라는 코드를 통해 부모 생성자의 인자로 들어가는데요. 여기서 args는 저희가 개발할 클래스의 생성자에서 부모 생성자에 넣어준 값입니다. 또 다시 부모 생성자로 넘겨주네요. 그럼 일단 부모 클래스의 부모 클래스를 찾아봐야겠죠? 이 클래스의 부모인 Strategy, 저의 상황에서는 passport-http-bearer의 strategy를 살펴볼 필요가 있겠습니다.

그래서 passport-http-bearer의 Strategy의 소스 코드까지 뜯.어.봅.니.다...

// passport-http-bearer/lib/strategy.js 


/**
 * Module dependencies.
 */
var passport = require('passport-strategy')
  , util = require('util');

 *
 * @constructor
 * @param {Object} [options]
 * @param {Function} verify
 * @api public
 */
function Strategy(options, verify) {
  if (typeof options == 'function') {
    verify = options;
    options = {};
  }
  if (!verify) { throw new TypeError('HTTPBearerStrategy requires a verify function'); }

  passport.Strategy.call(this);
  this.name = 'bearer';
  this._verify = verify;
  this._realm = options.realm || 'Users';
  if (options.scope) {
    this._scope = (Array.isArray(options.scope)) ? options.scope : [ options.scope ];
  }
  this._passReqToCallback = options.passReqToCallback;
}

/**
 * Inherit from `passport.Strategy`.
 */
util.inherits(Strategy, passport.Strategy);

...


/**
 * Expose `Strategy`.
 */
module.exports = Strategy;

저희는 생성자를 봅니다. function Strategy(options, verify)를 보면 저희가 PassportStrategy에서 호출한 부모 생성자에 의해 callback함수가 verify로 들어가나 봅니다.

추가로,

this._realm = options.realm || 'Users';
  if (options.scope) {
    this._scope = (Array.isArray(options.scope)) ? options.scope : [ options.scope ];
  }
  this._passReqToCallback = options.passReqToCallback;

생성자의 위 코드를 보면, options라는 값에서 realm, scope, passReqToCallBack이라는 값을 꺼내오는 것을 볼 수 있습니다. 아하! passport-http-bearer에서는 realm, scope, passReqToCallBack을 옵션으로 줄 수 있나보네요. 사실 이렇게 보니 제가 하려는 것과 크게 관련이 있지는 않은 것 같아서 이런 옵션들이 있구나, 옵션 값을 이렇게 찾을 수 있었구나 정도 생각하고 넘어가면 될것 같습니다.

this._verify = verify;

라는 코드에 의해 verify는 _verify가 되네요. 그럼 _verify는 어디서 호출이 될까요. 바로 같은 파일 아래에 정의되어 있는 authenticate라는 함수에서 호출이 됩니다.

// passport-http-bearer/lib/strategy.js 
...

/**
 * Authenticate request based on the contents of a HTTP Bearer authorization
 * header, body parameter, or query parameter.
 *
 * @param {Object} req
 * @api protected
 */
Strategy.prototype.authenticate = function(req) {
  var token;

  if (req.headers && req.headers.authorization) {
    var parts = req.headers.authorization.split(' ');
    if (parts.length == 2) {
      var scheme = parts[0]
        , credentials = parts[1];

      if (/^Bearer$/i.test(scheme)) {
        token = credentials;
      }
    } else {
      return this.fail(400);
    }
  }

  if (req.body && req.body.access_token) {
    if (token) { return this.fail(400); }
    token = req.body.access_token;
  }

  if (req.query && req.query.access_token) {
    if (token) { return this.fail(400); }
    token = req.query.access_token;
  }

  if (!token) { return this.fail(this._challenge()); }

  var self = this;

  function verified(err, user, info) {
    if (err) { return self.error(err); }
    if (!user) {
      if (typeof info == 'string') {
        info = { message: info }
      }
      info = info || {};
      return self.fail(self._challenge('invalid_token', info.message));
    }
    self.success(user, info);
  }

  if (self._passReqToCallback) {
    this._verify(req, token, verified);
  } else {
    this._verify(token, verified);
  }
};

/**
 * Build authentication challenge.
 *
 * @api private
 */
Strategy.prototype._challenge = function(code, desc, uri) {
  var challenge = 'Bearer realm="' + this._realm + '"';
  if (this._scope) {
    challenge += ', scope="' + this._scope.join(' ') + '"';
  }
  if (code) {
    challenge += ', error="' + code + '"';
  }
  if (desc && desc.length) {
    challenge += ', error_description="' + desc + '"';
  }
  if (uri && uri.length) {
    challenge += ', error_uri="' + uri + '"';
  }

  return challenge;
};

authenticate(req)함수는 req를 인자로 받네요. 이 친구는 클라이언트에서 보내는 request 객체겠죠?? 좀 더 아래 코드를 살펴보니까 이런 코드가 있어요

if (req.headers && req.headers.authorization) {
    var parts = req.headers.authorization.split(' ');
    if (parts.length == 2) {
      var scheme = parts[0]
        , credentials = parts[1];

      if (/^Bearer$/i.test(scheme)) {
        token = credentials;
      }
    } else {
      return this.fail(400);
    }
  }

아하! authenticate 함수는 request의 autorization 헤더의 값을 확인해서 schema가 bearer이면, 값을 파싱하여 token에 bearer token 값을 할당하네요! 그리고 _verify에 token을 넘겨주어 저희가 작성한 validate 함수가 token을 받아 validate에 우리가 커스텀해준 인증 로직을 타게 되는 것이었어요!

정리하자면,

1) 다른 passport 전략을 사용할 때에는 validate는 어떤 인자를 받는가? 의 정답은 => request의 헤더의 bearer token을 받는다. 였구요. 그렇기 때문에 저희는 validate(token: string)와 같은 시그니처로 개발을 하면되겠죠. 사실 함수의 원형 자체는 validate(payload: any)로 해도 문제는 없어요. 다만, 저희가 코드를 뜯어보면서 얻은 소중한 성과는 인자의 타입을 명확하게 추측할 수 있게되었다는 것이죠(인자로 객체가 오게 되면, 객체의 속성값까지도 알아야하니까요!). 개발을 하는데 더 확신을 가질 수 있다는 것도요!

또한, 2) 다른 전략을 사용할 때에는 나는 어떤 옵션을 주어야하는가? 는 각 strategy의 생성자를 보면 파악할 수 있다 라고 정리할 수 있을것 같습니다. passport-http-bearer같은 경우에는 realm, scope, passReqToCallBack라는 값을 옵션으로 줄 수가 있었습니다. 코드를 좀 더 파보면 어렵지 않게 이 옵션들이 어떻게 사용되는지를 파악할 수 있을것 같습니다. 저는 찾아보고나니 크게 필요가 없어서 패스~ 했습니다ㅎ

그래서 저는 결과적으로 어떻게 개발했냐 하면은

import { Injectable } from '@nestjs/common';
import { PassportStrategy } from '@nestjs/passport';
import { MemberService } from '../member/member.service';
import { Strategy } from 'passport-http-bearer';

@Injectable()
export class AdminAuthStrategy extends PassportStrategy(Strategy) {
  constructor(private readonly memberService: MemberService) {
    super();
  }

  async validate(token: string) {
    return await this.memberService.findAdminByToken(token);    // 커스텀 인증 로직 함수
  }
}

이런식으로 개발을 했습니다.

어... 크게 뭐 수정한건 없네요... 작업한 내용만 보면 결국 고작 글자 몇개 수정하려고 이 짓을 했나 싶기도 하지만😂, 내부 구조를 알았으니, 확신을 가지고 작업을 할 수 있었다는게 엄청 큰 성과이지 않을까요! 그리고 이제 passport의 다른 strategy를 사용하더라도 더 수월하게 작업할 수 있겠죠ㅎㅎ (실제로 얼마 전에는 passport-cookie를 가지고 작업할 일이 있었는데, 하루만에 작업을 끝냈답니다 헿)

언박싱 후기

막연하게 오픈소스 코드를 읽는것에 대한 거부감이 있었습니다. 오픈소스를 사용할 때에는 "여러 사람이 사용하니까"라는 이유로 막연한 신뢰감을 가지고 썼었던것 같아요. 사용 방법도 구글에 검색해보면 곧 잘 나왔구요. 감히 내가 전세계의 사람들이 기여한 오픈소스의 코드를 이해할 수 있을까?라는 두려움도 있었던것 같습니다.

근데 이렇게 한번 뜯어보고 나니까. 오픈소스를 가지고 개발하는 것에 대한 막연한 두려움이 해소가 된것 같아요. 앞으로 다른 오픈소스를 사용하면서 문제가 생겼을 때, 스택 오버플로우에서 수동적으로 다른 사람들의 해답을 적용시키기 보다. 빠르게 코드를 확인해봄으로써, 더 명확하게 문제를 해결할 수 있을 것 같아요.

그리고 앞으로 꽤 많은 시간을 개발자로 보낼텐데, 마냥 남들의 답변만 보고 개발을 할 순 없잖아요? 세상에 회사는 많고, 상황도 많고, 요구사항은 더 다양할거에요. 앞으로 가면 갈 수록 그 요구사항에 맞는 레퍼런스를 찾는 것은 더 어려워지겠죠. 그럼에도 문제를 해결해야겠죠. 개발자는 문제를 푸는 사람들이니까요. 그러한 면에서 이번 경험은 그런 보편적이지 않은 문제들도 잘 해결 수 있는 능동적인 개발자로 한걸음 더 성장할 수 있었던 좋은 계기였던것 같습니다😁

+) 꿀팁

NestJS는 node 기반의 프레임워크이고 사실은 express 혹은 fastify위에서 작동합니다. 그렇기 때문에 express나 fastify에서 개발하는 것과 Nest에서 개발하는 것 사이에는 일맥상통한 부분들이 있습니다. 아래 코드는 passport-http-bearer를 express의 미들웨어에 등록하는 예제입니다.

무언가 익숙하지 않으신가요?

function의 매개변수가 validate의 인자와 같습니다. done을 콜백이니까 제외하구요. 그리고 함수의 구현 내용도 유효한 사용자인지를 검증하는 로직이기 때문에 validate의 함수 내용과 같다고 할 수 있겠죠. 즉, 굳이 코드를 뜯어보지 않아도 node에서 passport를 등록하는 방법만 안다면 nest에서도 어렵지 않게 strategy를 사용할 수 있을것 같습니다ㅎㅎ 👍

회사에서 작업하던 도중 코드리뷰를 통해 await을 빼먹은 비동기 함수를 발견해버렸습니다...🤦

대부분의 비동기 함수가 값을 리턴받아서 사용하기 때문에 await 혹은 then 처리를 안해준것을 쉽게 찾을 수 있지만,

리턴값이 없거나 굳이 필요하지 않은 비동기 로직들은 await이나 then을 빼먹은 사실을 깨닫기 어렵더군요.

저의 경우 외부 API를 호출하여 WEB 발신 메세지를 전송하는 로직이었는데, 메세지가 잘 전송되었구나라는 사실만 확인하고 await을 빼먹은 것을 잘 확인하지 못하였습니다.

그래서! 이것을 방지하기 위해 eslint와 github action을 사용하여 처리되지 않은 비동기 함수를 확인하는 방법을 찾아보았고, 실제 프로젝트에 적용해본 경험을 공유해보려고 합니다!

적용해봅시다

1. 일단 eslint로 unhandle된 promise를 찾을 수 있도록설정합니다. .eslintrc.json 파일에 아래와 같은 설정을 추가해줍니다.

```json
  //.eslintrc.json

  {

  ...

  rules: {
      ...
      "@typescript-eslint/no-floating-promises": "error",
      ...
  }
```

이는 eslint 규칙중 no-floating-promises를 어긴 경우를 오류로 표시해주도록 설정해주는 것입니다.

no-floating-promises 규칙은 핸들링 되지 않는 promise를 허용하지 않는 규칙입니다.

위 규칙을 적용하면 await, .then()를 붙여주지 않은 비동기 로직에 대해 아래와 같이 오류를 띄우게 됩니다. 경험적으로 말씀드리자면, await이 누락되었고, 비동기 함수의 결과값을 다른 변수에 할당하지 않은 경우 오류를 보여주었습니다.

        ex)

        aysnc foo() {
            ...
        }

        await foo(); // 통과
        foo(); // 오류 출력
        const bar = foo() // 통과

2. 이제 소스코드가 eslint에 부합하는지 체크하도록 해봅시다. eslint가 설치되어 있다면 아래의 커맨드를 통해 소스코드의 lint를 체크할 수 있습니다.

    //shell
   
    eslint src --ext .ts,.tsx
   

   저는 위 명령어를 npm 커맨드로 등록하여 사용하였습니다.

```json
//pacakge.json

{
    ...
    scripts: {
        ...
        "lint:check": "eslint src --ext .ts,.tsx",
        ...
    }
}
```

3. github action 스크립트에서 lint:check 명령어를 수행할 수 있도록 추가합니다.

   저의 경우 push마다 실행하는 github action 스크립트에서 단위 테스트를 돌리기 전에 lint 검사를 하도록 추가하였습니다.

```yml
name: CI

on: [push]

env:
  ...

jobs:
  build:

    runs-on: ubuntu-latest
    steps:
      - name: Checkout branch
        uses: actions/checkout@v2

      - name: Use Node.js
        uses: actions/setup-node@v1
        with:
          node-version: '16.13.0'

      - uses: actions/cache@v2

      - name: Install dependencies
        run: -

      - name: Check eslint
        run: npm run lint:check

      - name: Run test
        run: -

      - name: Build node js project
        run: -
```

결과는?

이제 push를 해보면 eslint가 어긋나는 코드가 있을 경우 테스트에 실패한 것 처럼 FAIL이 발생하게 됩니다.

뿐만 아니라, 어느 부분에서 eslint에 어긋났는지 github PR내에 코맨트로 확인할 수 있게 됩니다.

아래는 제가 비동기 로직에서 await을 빠뜨린 상황을 가정하여 커밋을 했었는데, 이런 실수를 잘 잡아주는 모습입니다.

lint 오류 뿐만아니라 warning까지도 코맨트를 통해 확인할 수 있습니다.

효과는?

개인적으로 생각하는 가장 큰 효과는 찾기 힘든 오류를 사전에 방지 할 수 있다는 점입니다. await이 누락된 코드로 발생하는 오류는 언뜻 잘 돌아가는 것 처럼 보일때가 있어서 코드를 전부 뜯어보고 난 후에야 발견했던 경험이 몇번 있었는데, 이러한 리소스 낭비를 줄일 수 있다는 장점이 있는것 같습니다.

또한 리뷰의 부담을 줄일 수 있을것 같습니다. 자동으로 남겨주는 코맨트를 통해 리뷰 중에 이러한 오류를 찾아야한다는 부담을 덜 수 있으므로 리뷰 속도가 좀 더 빨라질 수 있을것 같습니다.

최근에 신생 스타트업에서 백엔드 개발자로 합류하여 일하고 있다. 기존 부실하게 만들어진 서버를 재설계하는 작업을 맡았다. 새로 개편하는 서버를 정식 배포할 때까지 기존 서버로 서비스를 운영하는 중인데 아무래도 프로토 타입이다 보니 빈틈이 많아 예상치 못한 오류가 많이 발생하더라. 이번에는 예상치 못한 부분에서 오류가 발생하여 이를 공유해보려고 한다.

어우 진짜 왜그래 아 진짜😥

서비스에서 운영하는 정보 공유방에 오류 제보가 들어왔다. 회원가입을 시도하면 예외 메세지가 그대로 출력이 되는 것이다(...!) (..!) 출력된 오류는 이와 같았다.

"message" : conversion from collation utf8mb4_unicode_ci into utf8_general_ci impossible for parameter

과연 무엇이 문제였을까... . . . . . . 정답은 소셜 인증 서버에서 가져온 정보에서 예외 케이스가 있었던 것이었다. 어떤 예외냐 하면 소셜 인증 서버에서 가져오는 닉네임에 이모지가 포함된 경우가 있던 것이었다. 닉네임을 저장하는 칼럼의 charset이 이모지를 지원하지 않아 충돌이 났었다.

MySql에서 utf8은 3Byte까지만 지원한다. 하지만 이모지는 최대 4Byte를 갖기 때문에 기존 utf8로는 이모지를 처리할 수 없다고...

그래서 이모지를 사용하기 위해선 VARCHAR(255) 타입에서 charset을 utf8에서 utfmb8로 바꾸어야 이모지를 처리할 수 있다고 한다.

이게 간과하기 쉬웠던 이유가 닉네임==단순 문자열 이라는 명제를 공식처럼 받아들였고 코드 상에서는 문자열로 받을 수 있었기 때문에 이게 문제가 될것이라고 상상을 못했다.

오늘의 교훈

최근들어서 이모지와 같은 문자들을 점점 더 많이 사용하는 추세이다. MySql 환경에서는 이제 VARCHAR 타입 칼럼의 charset은 웬만하면 utf8mb4로 변경해야하지 않을까 한다. 트랜드에 의해 DDL을 만져야하는 상황이 어찌보면 흥미롭다😁.

오랜만에 벨로그에 글을 올리는 것 같다. 그동안 놀면서 산건 아니고... 인턴도하고 창업팀에도 들어가고, 공부도 하면서 나름 부지런하게 살았다.

블로그에 글을 안쓰려고 안쓴건 아니고, 남들이 보는 곳에 글을 쓰려니까 완벽한 글만 써야된다는 부담감이 생겨 잠정적으로 중단했었다.

벨로그를 쉬면서 블로그의 방향성에 대해 다시 생각을 해보는 시간을 가졌다. 그리고 내린 결론은 아래와 같다.

😃 정보를 전달하기 보다는 내 생각을 전달할래

물론 내 블로그에서 정제된 지식을 얻어갈 수 있었으면 좋겠지만...

이전 포스트들을 보면 정보를 전달하는 글이 대부분이다. 블로그를 시작했을 때만 하더라도 거창한 것을 해야한다고 생각했기 때문이다.

블로그는 앞으로 내 오픈된 포트폴리오의 역할을 할 것이기 때문에 정말 완벽한 글을 올려야 된다는 압박감이 있었다. 그래서 내가 공부한 것을 올리더라도, 틀린 것이 없는지 잘못된 워딩은 없는지 등 글을 하나 작성하는데도 너무 많은 리소스가 필요했다. 그리고 너무 어려운 내용들을 deep하게 업로드하기도 한 문제도 있었다. 미쳤다고 내가 OS 내용을 업로드 했을까.

이젠 제대로 된 정보를 전달하기 위해 나도 몰랐던 내용을 뒤져가면서 글을 업로드하기 보다는 나의 경험을 공유하고 싶다.

나중 가니까 공부한 것을 블로그에 올리기 보다는, 블로그에 올리기 위해 공부를 하게 되더라. 그러다 보니, 블로그에 글을 쓰는게 부담이 됐었다. 그래서 이제는 내가 공부하면서 새로 알게 된점 위주로 가볍게 진행해보려고 한다.

또 여러개의 제약을 달아두면 또 부담스러워 질까봐 형식도 따로 정해두지 않으려고 한다. 뼛 속까지 N인 사람이라 미리 정해둔 대로 잘 못하는 병이 있다... 유동적으로 진행하는게 좋을 것 같다. 그래야 글 퀄리티도 유지가 될 것 같다. 그때 그때 생각 나는대로 업로드하려고 한다.

📰 어떤 것을 업로드 할 것이냐면

요즘에 창업팀에 들어가서 실제 서비스를 재설계하는 작업을 하고 있다. 그러다 보니 다양한 이슈를 접하게 되는데 이 것을 해결하면서 얻은 인사이트들을 공유해보려고 한다.

또한 문제를 해결하면서 자료를 찾아보다가 새로운 궁금증이 생겨서 새로운 인사이트를 얻게 되는게 있는데 이 것 또한 공유를 해보려고 한다.

개발 이야기가 아닌 더 나은 사람이 되기 위한 고민도 적어보려고 한다. 좋은 개발자가 되려면 코드만 잘 짜면 되는게 아니더라고...

. . . .

쨌든 이전 보다는 조금 더 가벼운 마음으로 다시 시작해보려고 한다. 부디 앞으로 꾸준히 계속할 수 있기를...!

가보자고

[적록색약]

문제

입력

출력

예제 입출력

풀이 및 접근

 입력으로 주어진 배열에서 상하좌우로 같은 색상끼리 그래프로 연결하여 생성되는 그래프의 개수를 세는 문제이다. 내가 작성한 코드는 아래와 같다.

코드

import sys
from collections import deque

shift_pattern = [(1, 0), (-1, 0), (0, -1), (0, 1)]

def bfs(picture, visited):
    area_cnt = 0
    i = 0
    while i < N:
        j = 0
        while j < N:
            if visited[i][j] == False:
                cur_color = picture[i][j]

                visited[i][j] = True
                que.append((i, j, area_cnt))
                while que:
                    y, x, _ = que.popleft()
                    for shift in shift_pattern:
                        dy = y + shift[0]
                        dx = x + shift[1]
                        if 0 <= dy < N  and 0 <= dx < N and visited[dy][dx] == False and picture[dy][dx] == cur_color:
                            que.append((dy, dx, area_cnt))
                            visited[dy][dx] = True
                area_cnt += 1
            j += 1
        i += 1
    return area_cnt

N = int(sys.stdin.readline().rstrip())
que = deque()
visited = [[False for _ in range(N)] for _ in range(N)]

picture = []
for _ in range(N):
    picture.append(list(sys.stdin.readline().rstrip()))

print(bfs(picture, visited))

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

for i in range(N):
    for j in range(N):
        if picture[i][j] == 'G':
            picture[i][j] = 'R'
print(bfs(picture, visited))

접근

처음 내 접근 방식은 아래와 같다.

1. 이미 방문한 곳인지 확인하기 위해 visited 배열을 사용하자
2. visited가 False인 곳을 방문한 경우, 상하좌우 중 현재와 같은 색깔이 곳을 Queue에 넣고 탐색하자. 탐색한 곳은 visited를 True로 변경한다.
3. visited가 False인 곳을 순차적으로 방문하자.
4. Queue에 넣을 때 좌표뿐만 아니라 현재 탐색된 연결그래프(구역)의 개수도 넣어주어 현재까지 몇개의 구역이 탐색되었는지 확인하자

위의 방법을 사용하면, 정상인이 보는 구역의 개수를 찾을 수 있었다.

이 다음에는 적록색약이 보는 구역을 개수를 찾아야하는데 이 과정에서 어렵게 생각하여 시간이 소요되었다. 그 이유는 실행시간을 의식하여 탐색 한번에 정상인과 적록색약이 보는 구역의 개수를 모두 구해야된다고 생각했기때문이다.😂 단순하게 picture의 R을 G로 바꾸고 다시 한번 탐색을 하는 방식으로 코드를 작성하니 통과되었다.

회고

• BFS가 아니라 DFS로 풀어도 되었을것 같다. 그래프 문제는 경험상 DFS로 풀면 시간초과가 걸리는 경향이 있어 습관적으로 BFS로 풀게 되는 것 같다. 처음 직관적으로 생각한대로 BFS로 풀었지만 문제 구조상 DFS로 풀었으면 더 쉽게 풀렸을 것 같다. 또한, 문제조건이 1 <= N <= 100 이라 DFS 풀이에서도 비교적 시간제한에서 여유로운 문제였던것 같다.

• 입력 조건을 체크하는 습관이 필요할 것 같다. 위에서 이어지는 말이지만 이번 문제의 경우 1 <= N <= 100으로 비교적 입력 스케일이 작은편이었다. 입력 스케일이 큰 경우 2차원 배열을 모두 탐색하는 것 조차 불가능한 문제들이 대부분인데, 이 문제의 경우 최대 입력 스케일이 100*100 배열이기 때문에 배열을 탐색하는게 자유롭다는 것을 입력 조건을 보고 더 빨리 알아차렸으면 문제 풀기가 더 수월햇을 것 같다.

 프로세스 전체가 메모리에 올라와있다고 가정하고 프로세스를 실행하는 것. 가상메모리를 사용하기 전에는 실행하는 프로세스의 전체 모두 메모리에 로드되어야 실행시킬 수 있었다. 따라서 총 메모리의 크기보다 큰 프로세스는 실행이 불가능하였다. 하지만 가상 메모리를 사용하면 프로세스에서 현재 필요한 부분만 로드하여 실행하기 때문에 프로세스의 크기와 상관없이 실행이 가능하다. 또한 필요없는 부분은 로드하지 않기 때문에 메모리 사용의 효율이 높아진다.

• 가상 메모리는 프로세스들의 중복된 부분을 프로세스들끼리 공유할 수 있도록 한다.

• 가상 메모리는 대게 page로 관리된다.

요구 페이징(Demand Paging)

 현재 필요한 페이지만 메모리에 로드하는 것이다. 사용하지 않을 페이지를 가져오지 않는 시간낭비와 메모리 낭비를 줄일 수 있다.

페이지 교체

1. 디스크에서 필요한 페이지의 위치를 찾는다.
2. 필요한 페이지를 디스크에 찾는다.
3. 페이지 테이블에서 victim(교체 당할 페이지)를 찾는다.
4. Victim을 디스크에 저장하고, 페이지 테이블을 수정한다.
5. Victim의 자리에 새로운 page를 불러오고 페이지 테이블을 수정한다.

페이지 교체 알고리즘

FIFO

• 선입선출 구조

• 프레임 수를 늘려도 page fault가 줄지 않는 상황이 생길 수 있다.
• 단순히 FIFO 구조이기 때문에 바로 다음에 사용할 페이지를 victim으로 지정할 수도 있기 때문이다.

Optimal

• Page fault를 최소화 하는 교체 알고리즘

• 결과론적인 방법이기 때문에 구현할 수 없으며, 페이지 교체 알고리즘의 성능을 비교할 때 사용된다.

LRU

• Least Recently Used

• 가장 오랫동안 사용되지 않은 페이지를 교체한다.

LFU

• Least Frequently Used

• 사용된 횟수가 가장 적은 페이지를 교체한다.
• Victim 후보가 여러 개인 경우 LRU 기법을 적용하여 victim을 선정한다.
• 최근에 적재된 페이지는 victim될 가능성이 높다.

캐시의 지역성

 캐시의 hit ratio를 높이기 위해 사용되는 개념이다. 캐시의 지역성은 저장장치의 데이터를 균일하게 접근하는 것이 아닌 상황에 따라 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성을 말한다.  캐시의 지역성은 크게 시간적 지역성, 공간적 지역성으로 나뉜다.

• 시간적 지역성 : 최근에 참조된 주소의 내용은 곧 다음에 다시 참조되는 특성

• 공간적 지역성 : 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

 각각의 프로세스는 독립적인 메모리 공간을 갖고, 운영체제 혹은 다른 프로세스의 메모리 공간에 접근할 수 없다. 유일하게, 운영체제만이 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 제약을 받지 않는다.

 메모리는 한정된 자원이기 때문에 사용하다 보면 당연히 공간이 부족하게 된다. 따라서 메모리 공간을 효율적으로 사용하기 위한 여러 방법이 존재 하는데 아래에서 설명할 paging과 segmentation이 그 예시이다. 또한 메모리 관리 기법에 따라 사용하지 못할 만한 작은 자유 공간이 생기는 단편화(Fragmentation)이 발생하기도 한다.

단편화(Fragmentation)

 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할 만큼의 자유 공간들이 생기는 현상, 외부 단편화(External Fragmentaion)와, 내부 단편화(Internal Fragmentation)로 나뉜다.

외부 단편화(External Fragmentation)

 메모리 공간 중 할당된 공간 사이에 작아서 사용하지 못하게 되는 일부분이 생기는 현상. 남는 공간들을 모두 합치면 충분한 공간이 되는 부분들이 분산되어 있을 때 발생한다. 메모리 압축(compaction)을 통해 해결한다.

메모리 압축(compaction)

 외부 단편화를 해소하기 위해 프로세스가 사용하는 공간들을 한쪽으로 몰아, 자유 공간을 확보하는 방법이지만 작업 효율이 좋지 않다.

내부 단편화(Internal Fragmentaion)

 프로세스가 사용하는 메모리 공간에 포함된 남는 부분이 생기는 현상. 예를 들어 프로세스에 할당된 공간이 100이라고 할 때, 실제 사용하는 공간이 80이면 20만큼의 공간이 남게 되는데 이러한 현상을 내부 단편화라고 한다.

페이징(paging)

 하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 없애는 메모리 관리이다. 외부 단편화와와 메모리 압축 작업을 해소하기 위해 생긴 방법론으로, 물리 메모리는 Frame이라는 고정 크기로 분리되어 있고, 논리 메모리는 page라고 불리는 고정 크기의 블록으로 분리된다.

 페이징 기법을 사용함으로써 논리 메모리는 물리 메모리에 저장될 때, 연속되어 저장될 필요가 없고 물리 메모리의 남는 프레임에 적절히 배치됨으로 외부 단편화를 해결할 수 있는 큰 장점이 있다.

 하나의 프로세스가 사용하는 공간은 여러개의 페이지로 나뉘어서 관리되고, 개별 페이지는 순서에 상관없이 물리 메모리에 있는 Frame에 mapping되어 저장된다.

단점

  내부 단편화가 자주 발생한다. 예를 들어, page의 크기가 1,024B이고 프로세스 A가 3,172B의 메모리를 요구한다면 3개의 page(1,024 * 3 = 3,072)를 사용하고도 100B가 모자르기 때문에 총 4개의 page가 필요한 것이다. 따라서 4번째 page에는 1,024B - 100B = 924B의 공간이 남게되는 내부 단편화 문제가 발생한다.

세그멘테이션(segmentation)

 논리 메모리와 물리 메모리를 같은 크기의 블록이 아닌, 서로 다른 크기의 논리적 단위인 세그먼트(segment)로 메모리를 할당한다.

단점

  외부 단편화가 발생한다.

 동일한 자원을 동시에 접근하는 작업을 실행하는 코드 영역을 Ciritical Section이라고 한다.

Critical Section Problem(임계영역 문제)

 프로세스들이 Critical Section을 동시에 접근하였을 때 발생하는 동기화 문제

임계영역 문제를 해결하기 위한 기본 조건

• Mutual Exclution(상호배제) 어떤 프로세스가 Critical Section에서 실행중이라면, 다른 프로세스는 그들이 가진 Critical Section에서 실행될 수 없다.
• Progress(진행) Critical Section에서 실행중인 프로세스가 없다면, 다른 프로세스가 접근할 수 있도록 한다.
• Bounded Waiting(한정된 대기) 같은 프로세스가 임계구역을 독점하지 못하게 한다. 다른 프로세스의 starvaion을 막기 위해 한번 하나의 프로세스가 critical section에 들어가려고 요청한 이후부터는 한정된 대기 횟수 안에 해당 프로세스가 critical section에 들어가야한다.

critical section 문제의 해결책

Lock

 하드웨어 기반 해결책으로써, 동시에 공유 자원에 접근하는 것을 막기 위해 critical section에 진입하는 프로세스는 lock을 획득하고 critical section에 진입하는 프로세스는 lock을 획득하고 critical section을 빠져나올 때, lock을 방출함으로써 동시에 접근이 되지 않도록 한다.  critical section으로의 진입 가능성 확인과 동시에 진입 거부를 원자적으로 한번에 처리한다.

단점

• 락이 걸려있는 경우 인터럽트가 되지 않기 때문에 다중 처리기 환경에서는 효율성 측면에서 적용할 수 없다.

Semaphore(세마포)

 소프트웨어상에서 Critical Section 문제를 해경하기 위한 동기화 도구

종류

• 카운팅 세마포 가용한 개수를 가진 자원에 대한 접근 제어용으로 사용되며, 세마포는 그 가용한 자원의 개수로 초기화 된다. 자원을 사용하는 프로세스가 생기면 세마포가 감소, 방출하면 세마포가 증가한다.
• 이진 세마포 MUTEX라고도 부르며, 상호배제(Mutual Exclution)의 머릿글자를 따서 만들어졌다. 이름 그대로 0과 1의 값만 사용 가능하며, 다중 프로세스들 사이의 Critical Section 문제를 해결하기 위해 사용된다.

단점

• Busy Waiting Spin Lock이라고 불리는 Semaphore 초기 버전에서 Critical Section에 진입해야하는 프로세스는 진입을 계속 시도하기 때문에, CPU 시간을 낭비했었다. 이를 Busy Waiting이라고 부르며 특수한 상황이 아니면 비효율적이다. 일반적으로는 Semaphore에서 Critical Section에 진입을 시도했지만 실패한 프로세스에 대해 Block시킨 뒤, Critical Section에 자리가 날 때 다시 깨우는 방식을 사용한다. 이 경우 Busy Waiting으로 인한 시간 낭비 문제가 해결된다.

모니터

• 고급 언어의 설계 구조물로서, 개발자의 코드를 상호배제하게끔 만든 추상화된 데이터 형태이다.
• 공유자원에 접근하기 위한 키 획득과 자원 사용 후 해제를 모두 처리한다(세마포는 직접 키 해제와 공유자원 접근 처리가 필요하다).

Deadlock(교착상태)

 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태이다. 둘 이상의 프로세스가 각자 공유 자원을 할당받은 후 다음 처리를 위해 다른 공유자원을 할당받아야할 때, 각자 필요한 자원이 상대방에게 할당되어있는 경우 프로세스들이 다음 처리를 위한 공유 자원을 획득하기 위해 서로 무한정 대기하는 상태이다.

프로세스의 흐름

장기 스케줄러(Long-term scheduler)

 메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로 디스크)에 임시로 저장한다. 이 pool에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue로 보낼지 결정하는 역할을 한다.

• new(디스크)->ready(메모리)로 갈 프로세스를 스케줄링

• 프로세스에 memory 및 각종 리소스를 할당
• degree of Multiprogramming 제어

단기 스케줄러(Short-term scheduler or CPU scheduler)

• CPU와 메모리 사이(ready->running->waiting->ready)의 스케줄링을 담당

• Ready Queue에 있는 프로세스 중 어떤 프로세스를 running 시킬지 결정

Ready Queue에 있는 프로세스 중 "어떤 프로세스를 running 시킬지까지만" 단기 스케줄러가 결정하고 실제 프로세스에 CPU를 할당하는 것은 "Dispatcher"가 수행함!

중기 스케줄러(Mid-term scheduler or Swapper)

• 여유공간(메모리)를 마련하기 위해서 프로세스를 통째로 메모리에서 디스크로 쫓아냄(Swapping)

• 프로세스에게서 memeory를 할당 해제(ready->suspended)
• 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절

suspended(stopped) : 외부적인 이유로 프로세스가 메모리에서 디스크로 내려간 상태(swap out), 스스로 event를 기다리는 waiting 상태와 달리 외부적인 요인으로 인해 정지 되었기 때문에 스스로 다시 동작할 수 없다.

CPU 스케줄러

  Ready Queue에 있는 프로세스들을 스케줄링하는 스케줄러(ready -> new)

선점형(preemptive) vs 비선점형(non-preemptive)

프로세스의 흐름

 CPU 스케줄링에 사용되는 두가지 방식으로,  비선점형 방식은 임의의 프로세스가 CPU를 할당 받으면 해당 프로세스가 종료(terminated)될 때까지 CPU를 점유하는데 반해,  선점형 방식은 어떤 프로세스가 CPU를 할당 받더라도 우선순위가 더 높은 프로세스가 ready queue에 들어오거나 입출력이나 이벤트 대기, time out이 발생하는 경우 프로세스가 종료되지 않아도 다른 프로세스에 의해 CPU를 선점당할 수 있다(다른 프로세스에게 CPU를 넘겨주고 대기 상태가 된다).

Priority Schduling(우선 순위 스케줄링)

 우선순위가 가장 높은 프로세스에게 CPU 를 할당하는 스케줄링이다. 우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.

Starvation(기아 현상)

 우선 순위 스케줄링 방식에서 우선 순위가 낮은 프로세스가 우선 순위가 높은 프로세스에게 계속 밀려 CPU의 할당을 받지 못하는 현상 -> aging을 통해 해결 가능

aging

 ready queue에서 오래 대기한 만큼 해당 프로세스의 우선순위를 높여주는 것

스케줄링 알고리즘

FCFS(First Come Fisrt Served)

특징

• 선입선출 방식 #FIFO
• 비선점형 스케줄링

문제점

• 소요시간이 긴 프로세스가 CPU를 차지하고 있는 경우 다른 프로세스들이 수행되지 못한다.

SJF(Shortest Job First)

특징

• ready queue에 존재하는 프로세스 중 가장 CPU Burst Time이 짧은 프로세스에게 CPU 할당
• 비선점형 스케줄링

CPU Burst Time : CPU를 할당 I/O가 일어나기 전까지 CPU를 사용하는 시간

문제점

• starvation 발생 가능

SRTF(Shortest Remaining Time First)

특징

• 새로운 프로세스가 도착할 때마다 각 프로세스의 남은 CPU Burst Time이 짧은 순으로 우선순위를 부여한다.
• 선점형 스케줄링

  문제점

• starvation 발생 가능
• 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU Burst Time을 측정할 수 없다.

SRTF는 SJF의 preemptive 방식이다

RR(Round Robin)

특징

• 각 프로세스는 동일한 크기의 time quantum(할당시간)을 갖게 된다.
• time-out 당하는 경우 ready queue의 맨 뒤로 가서 대기한다.
• CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우 효율적이다.

문제점

• time quantum이 너무 커지면 FCFS와 같아진다.

 실행중인 프로그램이다.  디스크로부터 메모리에 적재되어 CPU를 할당을 받을 수 있는 것을 말한다.

프로세스의 구조

 프로세스는 Text, Data, Stack & Heap 영역으로 나뉜다.

• Text : 프로세스의 컴파일된 코드 텍스트가 들어가는 영역

• Data : 전역변수, 초기화된 변수들이 저장되는 영역
• Stack & Heap : 동적할당 변수, Aativation Record(foraml + parameter, return address, 지역변수)가 저장되는 영역

프로세스의 구조

PCB(Process Control Block, 프로세스 제어 블록)

  PCB는 특정 프로세스에 대한 정보를 저장하는 자료구조이다. 운영체제는 프로세스를 관리하기 위해 프로세스 생성과 동시에 프로세스 당 고유한 PCB를 생성한다. 프로세스는 CPU의 할당을 받아 작업을 처리하다가 Context Switching이 발생하면 진행하던 작업의 상태를 PCB에 저장하고 CPU를 반환한다. 그 후 다시 CPU를 할당받으면 PCB에서부터 정보를 받아와 Context Switching이 발생한 시점부터 다시 작업을 시작한다.

PCB에 저장되는 정보

• PID : 프로세스 식별 번호

• PC : Program Counter
• Registers : CPU Register 정보
• CPU-Scheduling Information : 스케줄링큐에 대한 포인터, 프로세스 우선순위 등
• Memory-Management Information : 페이지 테이블 혹은 세그먼트 테이블과 같은 정보 포함
• I/O status Information : 프로세스에 할당된 입출력 장치들 정보
• File Descriptor Table : 프로세스에 할당된 열린 파일 목록
• Accounting Information : 사용된 CPU 시간, 시간 제한, 계정정보 등
• Signal Handling Information

스레드(Thread)

 프로세스의 실행 단위라고 할수 있다. 한 프로세스 내에서 동작되는 여러 실행 흐름으로 프로세스 내에 Code(Text), Data, Heap 영역,열린 파일 등은 공유하지만 고유의 PC, register, Stack 영역을 갖는다.

멀티스레딩

 하나의 프로세스 내에서 여러개의 스레드를 다루는 것을 멀티스레딩이라고 한다. 프로세스의 자원을 공유함으로써 자원의 생성과 관리의 중복성을 최소화하여 수행 능력을 향상 시킬 수 있다.

멀티 스레딩의 장점

 여러 프로세스를 사용해 동시에 처리하던 일을 스레드로 구현할 경우 메모리 공간과 컴퓨터 자원의 소모가 줄어들게 된다.  스레드간 통신이 필요한 경우에도 별도의 자원을 이용하는 것이 아니라 전역변수의 공간 또는 Heap영역의 동적할당 자료구조를 이용하여 데이터를 주고받을 수 있다. 그렇기 때문에 프로세스간 통신(IPC, Inter Processs Communication)에 비해 스레드간의 통신이 훨씬 간단하다.  또한 스레드의 Context Switching은 프로세스의 Context Switching과 달리 캐시 메모리를 비울 필요가 없기 때문에 더 빠르다. 따라서 시스템의 throughput이 향상되고 자원 소모가 줄어들며 자연스럽게 프로그램의 응답 시간이 단축된다.

멀티 스레딩의 단점

 멀티 프로세스 프로그래밍에서는 프로세스간 공유하는 자원이 없기 때문에 자원의 동기화 문제가 발생하지 않지만, 멀티 스레딩을 사용하는 경우 스레드간 공유하는 영역이 있기 때문에 동기화 문제가 발생할 수 있다.  따라서 멀티 스레딩에서는 동기화 작업이 필요하다. 이 경우 과도한 locking이 걸리는 경우 병목현상이 일어날 수 있으니 주의해야한다.

멀티 스레드 vs 멀티 프로세스

 멀티 스레드는 멀티 프로세스보다 적은 메모리 공간을 가지고 Context Swtiching이 빠르다는 장점이 있지만, 오류로 인해 하나의 스레드가 종료되면 전체 스레드가 종료될 수 있다는 점과 동기화 문제를 안고 있다.  반면 멀티 프로세스 방식은 하나의 프로세스가 죽더라도 다른 프로세스에는 영향을 끼치지않고 정상적으로 수행된다는 장점이 있지만, 멀티 스레드보다 많은 메모리 공간과 CPU 시간(Context Switching이 오래 걸리기 때문)을 차지한다는 단점이 존재한다.

 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.  항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

입출력 예 설명

예제 #1

[ICN, JFK, HND, IAD] 순으로 방문할 수 있습니다.

예제 #2

[ICN, SFO, ATL, ICN, ATL, SFO] 순으로 방문할 수도 있지만 [ICN, ATL, ICN, SFO, ATL, SFO] 가 알파벳 순으로 앞섭니다.

풀이

import copy

def _search(left_tickets, ticket_history, result):
    for ticket in left_tickets:
        if ticket_history[-1][1] == ticket[0]:
            if len(left_tickets) > 1:
                added_history = copy.deepcopy(ticket_history)
                added_history.append(ticket)
                _search(copy.deepcopy([x for x in left_tickets if x is not ticket])
                                , added_history
                                , result)
            elif len(left_tickets) == 1:
                ticket_history.append(ticket)
                result.append(ticket_history)


def solution(tickets):
    answer = []
    result = []
    for ticket in tickets:
        if ticket[0] == 'ICN':
            left_tickets = copy.deepcopy([x for x in tickets if x is not ticket])
            _search(left_tickets, [ticket], result)

    for seq in result:
        path = []
        for index, ticket in enumerate(seq):
            if index == 0:
                path.extend(ticket)
            else:
                path.append(ticket[1])
        answer.append(path)

    answer = sorted(answer, key = lambda x: x)

    return answer[0]

 _search(left_tickets, ticket_history, result)는 solution(tickets)에서 내부적으로 호출되는 함수이다. 깊이 우선 탐색 방식을 통해 가능한 모든 경로를 찾는다. 인자는 아래와 같다.

left_tickets : 아직 사용하지 않은 티켓의 리스트 ticket_history : 현재까지 거쳐온 경로 result : 모든 티켓을 사용하였을 경우 가능한 모든 경로를 저장하는 list

solution에서 'ICN'에서 출발하는 티켓들만 시작점으로 주어 _search를 호출한다.

 _search에서는 가장 마지막 경로의 도착점과 남은 티켓들의 출발지를 확인하여 두 위치가 동일한 경우 ticket_history와 left_tickets에 각각 추가, 삭제한 후에 다시 _search를 재귀호출한다. 이 때, 만약 남은 티켓이 해당 티켓밖에 없는 경우 해당 티켓을 ticket_history에 추가한 후, 해당 ticket_history를 result에 추가한다. 위 과정을 통해 가능한 모든 경로를 result에 추가한다.

 _search의 재귀호출이 모두 끝난 후에 solution에서 result를 확인하여 일련의 경로로 바꾼다. 이후 알파벳 순으로 정렬하여 가장 첫번째 원소를 리턴한다.

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

&nbsp예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

&nbsp두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

풀이

from queue import Queue
import copy

def _word_compare(src_word, dest_word):
    diff_count = 0
    for i in range(len(src_word)):
        if src_word[i] != dest_word[i]:
            diff_count += 1

        if diff_count > 1:
            return False

    return True

def _search(begin, target, words):
    queue = Queue()
    depth = 0
    used = set()

    if target not in words:
        return 0

    queue.put((begin, 0))
    while(queue.qsize() > 0):
        cur_node = queue.get()
        src_word = cur_node[0]
        depth = cur_node[1]
        if _word_compare(src_word, target):
            return depth + 1


        for word in words:
            if _word_compare(src_word, word) and (word not in used):
                queue.put((word, depth + 1))
                used.add(word)
    return 0

def solution(begin, target, words):
    answer = _search(begin, target, words)
    return answer

 _word_compare(src_word, dest_word)두 단어를 입력받아 알파벳 하나만 차이가 나면 True, 아니면 False를 리턴하는 함수이다. 내부적으로 _search에 사용된다.  _search(begin, target, words)는 너비 우선 탐색을 하며 현재 노드의 단어에 대해 _word_compare이 True인 단어를 너비 우선 탐색하는 함수이다. target이 words에 포함되어 있지 않으면 0를 리턴하며, used라는 set에 이미 탐색한 단어를 추가하며 다시 탐색되지 않게 하였다. (이렇게 하지 않으면 인접한 두 단어에 대해 사이클이 생기게 된다. 또한 후에 탐색된 단어와 인접한 단어라고 하더라도 전에 측정된 최단 거리보다 짧을 수 없다) 현재 노드에 인접한 단어들을 depth + 1와 함께 queue에 넣어주어 다시 꺼냈을 때 해당 노드이 깊이를 파악할 수 있게 하였다.

&nbsp처음에는 최단 경로에 집중하여 다익스트라 알고리즘을 통해 해결하는 것을 시도했었다. 이론상으로는 가능하다고 생각하는데, 구현 상 코드가 복잡해지고 그래프를 완성한 후 경로를 찾아야하기 때문에 비효율적이라는 생각이 들었다. 또한 어차피 경로의 길이가 1이기 때문에 다익스트라 알고리즘보다 BFS로 해결하는 방법을 고안하여 문제를 해결하였다.

github 주소

https://github.com/bjih1999/algorithm/blob/master/programmers/DFS_BFS/%EB%8B%A8%EC%96%B4%20%EB%B3%80%ED%99%98/solution.py

 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

입출력 예 설명

예제 #1

아래와 같이 2개의 네트워크가 있습니다.

예제 #2

아래와 같이 1개의 네트워크가 있습니다.

풀이

from queue import Queue

def solution(n, computers):
    answer = 0

    visited = set()
    queue = Queue()

    queue.put(0)

    for node_index in range(n):
        if node_index not in visited:
            visited.add(node_index)
            queue.put(node_index)
            while(queue.qsize() > 0):
                cur = queue.get()
                visited.add(cur)

                for i in range(n):
                    if (computers[cur][i] == 1) and (i not in visited):
                        visited.add(i)
                        queue.put(i) 

            answer += 1

    return answer 

 Queue를 사용하여 BFS를 통해 그래프를 탐색하며 탐색한 노드의 index를 visited에 추가하였다. 시작 노드부터 탐색할 수 있는 모든 노드를 방문한 경우(Queue에 추가된 자식 노드가 없는 경우 즉, Queue.qsize() == 0) 한개의 네트워크를 찾은 것으로 보아 answer을 1증가시킨다. 만약 아직 방문하지 않는 노드가 있는 경우 해당 노드부터 시작하여 위 시행을 반복한다. 모든 노드를 방문한 경우 answer를 리턴한다.

github

https://github.com/bjih1999/algorithm/blob/master/programmers/DFS_BFS/%ED%83%80%EA%B2%9F%20%EB%84%98%EB%B2%84/solution.py

 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

풀이

import copy

def search(numbers, index, target, answer):
    number_arr = copy.deepcopy(numbers)
    if index > len(number_arr)-2 :
        if sum(number_arr[:-1]) + number_arr[-1] == target:
            answer[0] += 1

        if sum(number_arr[:-1]) - number_arr[-1] == target:
            answer[0] += 1

        return

    else:
        search(number_arr, index + 1, target, answer)

        number_arr[index] *= -1
        search(number_arr, index + 1, target, answer)


def solution(numbers, target):
    answer = [0]
    search(numbers, 0, target, answer)

    return answer[0]

 search(numbers, index, target, answer)는 numbers와 index를 입력받아 함수 내에서 search(numbers, index + 1, target, answer)을 재귀적으로 호출하여 해당 인덱스의 numbers 원소에 -1을 곱하였을 때 numbers의 합이 target과 일치하는 지 확인하는 함수이다.  재귀 호출 시 numbers[i]에 -1을 곱한 것과 곱하지 않은 것을 인자로 주어 두번 호출함으로써, 이진 트리를 DFS로 탐색하는 구조를 갖고 있다. 최종적인 확인(sum(numbers) == target)은 index == len(numbers)-2일 때 재귀가 종료되며 수행되도록 하여, 굳이 depth 한 번 더 내려가지 않고 그 전에 마지막 level의 값을 미리 계산하여 결과를 확인함으로써 실행시간을 단축시켰다.  결과값을 answer[0]에 저장을 하였는데 python은 int타입의 경우 call by value로 인해 각 재귀 호출로 인한 정답 개수가 독립적으로 누적되는 이슈가 발생한다. 따라서 list에 저장하도록 하여 모든 재귀 호출의 결과값이 한 변수에 동기화 되도록 하였다.

github 주소

https://github.com/bjih1999/algorithm/blob/master/programmers/DFS_BFS/%ED%83%80%EA%B2%9F%20%EB%84%98%EB%B2%84/solution.py

 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

• 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
• 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
• 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

입출력 예 설명

 classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

풀이

def solution(genres, plays):
    answer = []
    genre_dic = {}
    genre_play = []

    for index, genre in enumerate(genres) :
        if genre not in genre_dic:
            genre_dic[genre] = plays[index]
        else:
            genre_dic[genre] += plays[index]

        genre_play.append((index, genre, plays[index]))

    sorted_genre = list(reversed(sorted(genre_dic.items(), key = lambda x : x[1])))
    sorted_song = list(reversed(sorted(genre_play, key = lambda x : (x[2], -x[0]))))

    for genre in sorted_genre:
        count = 0
        for song in sorted_song:
            if genre[0] == song[1]:
                count += 1
                answer.append(song[0])
            if count > 1:
                break
    return answer

 {장르 : 장르별 재생 수의 합}의 해시 테이블(딕셔너리) genre_dic을 만들어 재생수의 내림차순으로 장르를 정렬하고, (장르, 노래의 고유번호, 재생 수)의 속성을 가진 리스트 genre_play를 만들어 1차로 재생 수의 내림차순, 재생수가 같은 경우 2차로 고유번호가 낮은 순으로 정렬하였다.  그 후, 총 재생 수가 많은 순으로 sorted_song(genre_play를 정렬한 것)의 장르와 비교하여 가장 먼저 찾은 노래를 2개씩 answer에 추가하는 방법으로 해결하였다.

github 주소

https://github.com/bjih1999/algorithm/blob/master/programmers/hash/%EB%B2%A0%EC%8A%A4%ED%8A%B8%EC%95%A8%EB%B2%94/solution.py

 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

입출력 예 설명

예제 #1

headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

예제 #2

face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask
2. blue_sunglasses
3. smoky_makeup

import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> hashMap = new HashMap<>();

        for(int i = 0 ; i < clothes.length ; i++){
            if(!hashMap.containsKey(clothes[i][1])){
                hashMap.put(clothes[i][1], 1);
            }
            else{
                hashMap.put(clothes[i][1], (hashMap.get(clothes[i][1]).intValue()) + 1);
            }
        }
        for(String key : hashMap.keySet()){
            answer *= (hashMap.get(key)+1);
        }
        return answer-1;
    }
}

풀이

 HashMap을 사용하여 풀었다. <의상의 종류, 해당 종류 의상의 개수>를 각각 Key, Value로 받아 각 의상 종류의 개수를 파악하였다.  스파이가 입는 의상의 경우의 수는 각 의상 종류의 개수+1을 모두 곱하는 것이다(해당 종류의 의상을 안 입는 경우 포함). 이 때 스파이가 적어도 하나의 의상은 입고 있어야하기 때문에 모든 의상을 입지 않은 한가지 경우의 수를 위해 모두 곱한 값에 -1을 해준다.

github 링크

https://github.com/bjih1999/algorithm/blob/master/programmers/hash/%EC%9C%84%EC%9E%A5/Solution.java

 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.  전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

입출력 예

입출력 예 설명

입출력 예 #1

앞에서 설명한 예와 같습니다.

입출력 예 #2

한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3

첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

풀이

public class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

        L1 : for(int i = 0 ; i < phone_book.length - 1 ; i++){
            for(int j = i+1 ; j < phone_book.length ; j++){
                if(phone_book[i].charAt(0) == phone_book[j].charAt(0)){
                    if(phone_book[i].startsWith(phone_book[j]) || phone_book[j].startsWith(phone_book[i])){
                        answer = false;
                        break L1;
                    }
                }
            }
        }
        return answer;
    }
}

 완전 탐색으로 해결하였다. 대신 연산을 줄이기 위해 서로의 첫 문자만 비교하여 서로의 접두사인지 판단하도록 하였다.

github 링크

https://github.com/bjih1999/algorithm/blob/master/programmers/hash/%EC%A0%84%ED%99%94%EB%B2%88%ED%98%B8%20%EB%AA%A9%EB%A1%9D/Solution.java