한상훈 기술 블로그

GraphQL 개념잡기

Thu, 01 Aug 2019 12:00:00 +0900

GraphQL은 페이스북에서 만든 쿼리 언어입니다. GrpahQL은 요즘 개발자들 사이에서 자주 입에 오르내리고 있으나, 2019년 7월 기준으로 얼리스테이지(early-stage)임은 분명합니다. 국내에서 GraphQL API를 Open API로 공개한 곳은 드뭅니다. 또한, 해외의 경우, Github 사례(Github v4 GraphQL)를 찾을 수는 있지만, 전반적으로 GraphQL API를 Open API로 공개한 곳은 많지 않습니다. 하지만 등장한지 얼마되지 않았음에도 불구하고, GraphQL의 인기는 매우 가파르게 올라가고 있다는 사실을 확인 할 수 있습니다.

GraphQL 이란?

Graph QL(이하 gql)은 Structed Query Language(이하 sql)와 마찬가지로 쿼리 언어입니다. 하지만 gql과 sql의 언어적 구조 차이는 매우 큽니다. 또한 gql과 sql이 실전에서 쓰이는 방식의 차이도 매우 큽니다. gql과 sql의 언어적 구조 차이가 활용 측면에서의 차이를 가져왔습니다. 이 둘은 애초에 탄생 시기도 다르고 배경도 다릅니다. sql은 데이터베이스 시스템에 저장된 데이터를 효율적으로 가져오는 것이 목적이고, gql은 웹 클라이언트가 데이터를 서버로 부터 효율적으로 가져오는 것이 목적입니다. sql의 문장(statement)은 주로 백앤드 시스템에서 작성하고 호출 하는 반면, gql의 문장은 주로 클라이언트 시스템에서 작성하고 호출 합니다.

SELECT plot_id, species_id, sex, weight, ROUND(weight / 1000.0, 2) FROM surveys;

sql 쿼리 예시

{
  hero {
    name
    friends {
      name
    }
  }
}

gql 쿼리 예시

서버사이드 gql 어플리케이션은 gql로 작성된 쿼리를 입력으로 받아 쿼리를 처리한 결과를 다시 클라이언트로 돌려줍니다. HTTP API 자체가 특정 데이터베이스나 플렛폼에 종속적이지 않은것 처럼 마찬가지로 gql 역시 어떠한 특정 데이터베이스나 플렛폼에 종속적이지 않습니다. 심지어 네트워크 방식에도 종속적이지 않습니다. 일반적으로 gql의 인터페이스간 송수신은 네트워크 레이어 L7의 HTTP POST 메서드와 웹소켓 프로토콜을 활용합니다. 필요에 따라서는 얼마든지 L4의 TCP/UDP를 활용하거나 심지어 L2 형식의 이더넷 프레임을 활용 할 수도 있습니다.

REST API와 비교

REST API는 URL, METHOD등을 조합하기 때문에 다양한 Endpoint가 존재 합니다. 반면, gql은 단 하나의 Endpoint가 존재 합니다. 또한, gql API에서는 불러오는 데이터의 종류를 쿼리 조합을 통해서 결정 합니다. 예를 들면, REST API에서는 각 Endpoint마다 데이터베이스 SQL 쿼리가 달라지는 반면, gql API는 gql 스키마의 타입마다 데이터베이스 SQL 쿼리가 달라집니다.

위 그림처럼, gql API를 사용하면 여러번 네트워크 호출을 할 필요 없이, 한번의 네트워크 호출로 처리 할 수 있습니다.

GraphQL의 구조

쿼리/뮤테이션(query/mutation)

쿼리와 뮤테이션 그리고 응답 내용의 구조는 상당히 직관적 입니다. 요청하는 쿼리문의 구조와 응답 내용의 구조는 거의 일치 합니다.

gql에서는 굳이 쿼리와 뮤테이션을 나누는데 내부적으로 들어가면 사실상 이 둘은 별 차이가 없습니다. 쿼리는 데이터를 읽는데(R) 사용하고, 뮤테이션은 데이터를 변조(CUD) 하는데 사용한다는 개념 적인 규약을 정해 놓은 것 뿐입니다.

{
  human(id: "1000") {
    name
    height
  }
}

query HeroNameAndFriends($episode: Episode) {
  hero(episode: $episode) {
    name
    friends {
      name
    }
  }
}

제가 처음 gql을 접했을때 일반 쿼리와 오퍼레이션 네임 쿼리의 구분이 어려웠습니다. 하나 는 앞에 query가 붙어있고, 다른 하나는 처음 시작이 중괄호(‘{‘) 문자가 붙어있습니다. 이것을 이해하는데에는 오퍼레이션 네임과 변수의 쓰임새를 살펴보는 것이 도움이 됩니다. 일반적인 경우 클라이언트에서 static한 쿼리문을 작성하지는 않을 것입니다. 주로 정보를 불러올때 id 값이나, 다른 인자 값을 가지고 데이터를 불러 올 것입니다. gql에는 쿼리에 변수라는 개념이 있는데, 이 개념은 이러한 용처를 위해 존재 하는것 입니다. gql을 구현한 클라이언트에서는 이 변수에 프로그래밍으로 값을 할당 할 수 있는 함수 인터페이스가 존재합니다. react apollo client의 경우에는 variables 라는 파라메터에 원하는 값을 넣어주면 됩니다.

query getStudentInfomation($studentId: ID){
  personalInfo(studentId: $studentId) {
    name
    address1
    address2
    major
  }
  classInfo(year: 2018, studentId: $studentId) {
    classCode
    className
    teacher {
      name
      major
    }
    classRoom {
      id
      maintainer {
        name
      }
    }
  }
  SATInfo(schoolCode: 0412, studentId: $studentId) {
    totalScore
    dueDate
  }
}

오퍼레이션 네임 쿼리는 매우 편리 합니다. 굳이 비유하자면 쿼리용 함수 입니다. 데이터베이스 에서의 프로시져(procedure) 개념과 유사하다고 생각하면 됩니다. 이 개념 덕분에 여러분은 REST API를 호출할때와 다르게, 한번의 인터넷 네트워크 왕복으로 여러분이 원하는 모든 데이터를 가져 올 수 있습니다. 데이터베이스의 프로시져는 DBA 혹은 백앤드프로그래머가 작성하고 관리 하였지만, gql 오퍼레이션 네임 쿼리는 클라이언트 프로그래머가 작성하고 관리 합니다.

gql이 제공하는 추가 기능 덕분에 백엔드 프로그래머와 프론트엔드 프로그래머의 협업 방식 에도 영향을 줍니다. 이전 협업 방식(REST API)에서는 프론트앤드 프로그래머는 백앤드 프로그래머가 작성하여 전달하는 API의 request / response의 형식에 의존하게 됩니다. 그러나, gql을 사용한 방식에 서는 이러한 의존도가 많이 사라집니다. 다만 여전히 데이터 schema에 대한 협업 의존성은 존재합니다.

스키마/타입(schema/type)

데이터베이스 스키마(schema)를 작성할 때의 경험을 SQL 쿼리 작성으로 비유한다면, gql 스키마를 작성할 때의 경험은 C, C++의 헤더파일 작성에 비유가 됩니다. 그러므로, 프로그래밍언어(C, C++, JAVA등)에 익숙한 프로그래머라면 스키마 정의 또한 쉽게 배우실 것입니다.

오브젝트 타입과 필드

type Character {
  name: String!
  appearsIn: [Episode!]!
}

오브젝트 타입 : Character
필드 : name, appearsIn
스칼라 타입 : String, ID, Int 등
느낌표(!) : 필수 값을 의미(non-nullable)
대괄호([, ]) : 배열을 의미(array)

리졸버(resolver)

데이터베이스 사용시, 데이터를 가져오기 위해서 sql을 작성 했습니다. 또한, 데이터베이스에는 데이터베이스 어플리케이션을 사용하여 데이터를 가져오는 구체적인 과정이 구현 되어 있습니다. 그러나 gql 에서는 데이터를 가져오는 구체적인 과정을 직접 구현 해야 합니다. gql 쿼리문 파싱은 대부분의 gql 라이브러리에서 처리를 하지만, gql에서 데이터를 가져오는 구체적인 과정은 resolver(이하 리졸버)가 담당하고, 이를 직접 구현 해야 합니다. 프로그래머는 리졸버를 직접 구현해야하는 부담은 있지만, 이를 통해서 데이터 source의 종류에 상관 없이 구현이 가능 합니다. 예를 들어서, 리졸버를 통해 데이터를 데이터베이스에서 가져 올 수 있고, 일반 파일에서 가져 올 수 있고, 심지어 http, SOAP와 같은 네트워크 프로토콜을 활용해서 원격 데이터를 가져올 수 있 습니다. 덧붙이면, 이러한 특성을 이용하면 legacy 시스템을 gql 기반으로 바꾸는데 활용 할 수 있습니다.

gql 쿼리에서는 각각의 필드마다 함수가 하나씩 존재 한다고 생각하면 됩니다. 이 함수는 다음 타입을 반환합니다. 이러한 각각의 함수를 리졸버(resolver)라고 합니다. 만약 필드가 스칼라 값(문자열이나 숫자와 같은 primitive 타입)인 경우에는 실행이 종료됩니다. 즉 더 이상의 연쇄적인 리졸버 호출이 일어나지 않습니다. 하지만 필드의 타입이 스칼라 타입이 아닌 우리가 정의한 타입이라면 해당 타입의 리졸버를 호출되게 됩니다.

이러한 연쇄적 리졸버 호출은 DFS(Depth First Search)로 구현 되어있을것으로 추측합니다. 이점이 바로 gql이 Graph라는 단어를 쓴 이유가 아닐까 생각합니다. 연쇄 리졸버 호출은 여러모로 장점이 있습니다. 연쇄 리졸버 특성을 잘 활용하면 DBMS의 관계에 대한 쿼리를 매우 쉽고, 효율적으로 처리 할 수 있습니다. 예를들어 gql의 query에서 어떤 타입의 필드 중 하나가 해당 타입과 1:n의 관계를 맺고 있다고 가정해보겠습니다.

type Query {
  users: [User]
  user(id: ID): User
  limits: [Limit]
  limit(UserId: ID): Limit
  paymentsByUser(userId: ID): [Payment]
}

type User {
	id: ID!
	name: String!
	sex: SEX!
	birthDay: String!
	phoneNumber: String!
}

type Limit {
	id: ID!
	UserId: ID
	max: Int!
	amount: Int
	user: User
}

type Payment {
	id: ID!
	limit: Limit!
	user: User!
	pg: PaymentGateway!
	productName: String!
	amount: Int!
	ref: String
	createdAt: String!
	updatedAt: String!
}

여기에서는 User와 Limit는 1:1의 관계이고 User와 Payment는 1:n의 관계입니다.

{
  paymentsByUser(userId: 10) {
    id
    amount
  }
}

{
  paymentsByUser(userId: 10) {
    id
    amount
    user {
      name
      phoneNumber
    }
  }
}

위 두 쿼리는 동일한 쿼리명을 가지고 있지만, 호출 되는 리졸버 함수의 갯수는 아래가 더 많습니다. 각각의 리졸버 함수에는 내부적으로 데이터베이스 쿼리가 존재합니다. 이 말인즉, 쿼리에 맞게 필요한 만큼만 최적화하여 호출 할 수 있다는 의미입니다. 내부적으로 로직 설계를 어떻게 하느냐에 따라서 달라 질 수 있겠지만, 이러한 재귀형의 리졸버 체인을 잘 활용 한다면, 효율적인 설계가 가능 합니다. (기존에 REST API 시대에는 정해진 쿼리는 무조건 전부 호출이 되었습니다.)

리졸버 함수는 다음과 같이 총 4개의 인자를 받습니다.

  Query: {
    paymentsByUser: async (parent, { userId }, context, info) => {
        const limit = await Limit.findOne({ where: { UserId: userId } })
        const payments = await Payment.findAll({ where: { LimitId: limit.id } })
        return payments        
    },  
  },
  Payment: {
    limit: async (payment, args, context, info) => {
      return await Limit.findOne({ where: { id: payment.LimitId } })
    }
  }

첫번째 인자는 parent로 연쇄적 리졸버 호출에서 부모 리졸버가 리턴한 객체입니다. 이 객체를 활용해서 현재 리졸버가 내보낼 값을 조절 할 수 있습니다.
두번째 인자는 args로 쿼리에서 입력으로 넣은 인자입니다.
세번째 인자는 context로 모든 리졸버에게 전달이 됩니다. 주로 미들웨어를 통해 입력된 값들이 들어 있습니다. 로그인 정보 혹은 권한과 같이 주요 컨텍스트 관련 정보를 가지고 있습니다.
네번째 인자는 info로 스키마 정보와 더불어 현재 쿼리의 특정 필드 정보를 가지고 있습니다. 잘 사용하지 않는 필드입니다.

인트로스펙션(introspection)

기존 서버-클라이언트 협업 방식에서는 연동규격서라고 하는 API 명세서를 주고 받는 절차가 반드시 필요 했습니다. 프로젝트 관리 측면에서 관리해야 할 대상의 증가는 작업의 복잡성 및 효율성 저해를 의미합니다. 이 API 명세서는 때때로 관리가 제대로 되지 않아, 인터페이스 변경 사항을 제때 문서에 반영하지 못하기도 하고, 제 타이밍에 전달 못하곤 합니다.

이러한 REST의 API 명세서 공유와 같은 문제를 해결하는 것이 gql의 인트로스펙션 기능 입니다. gql의 인트로스펙션은 서버 자체에서 현재 서버에 정의된 스키마의 실시간 정보를 공유를 할 수 있게 합니다. 이 스키마 정보만 알고 있으면 클라이언트 사이드에서는 따로 연동규격서를 요청 할 필요가 없게 됩니다. 클라이언트 사이드에서는 실시간으로 현재 서버에서 정의하고 있는 스키마를 의심 할 필요 없이 받아들이고, 그에 맞게 쿼리문을 작성하면 됩니다.

이러한 인트로스펙션용 쿼리가 따로 존재합니다. 일반 gql 쿼리문을 작성하듯이 작성하면 됩니다. 다만 실제로는 굳이 스키마 인트로스펙션을 위해 gql 쿼리문을 작성할 필요가 없습니다. 대부분의 서버용 gql 라이브러리에는 쿼리용 IDE를 제공합니다. 다음 화면은 apollo server라는 서버용 gql 라이브러리에 포함 되어있는 웹 IDE 화면입니다.

위의 화면을 참고하면, 프로그래머는 인트로스펙션을 활용하여, 직접 쿼리 및 뮤테이션, 필드 스키마를 확인 할 수 있습니다. 물론 보안상의 이슈로 상용환경에서는 이러한 스키마의 공개는 신중해야 합니다. 대부분의 라이브러리는 해당기능을 켜고 끄게 하는 옵션이 존재합니다.

GraphQL을 활용 할 수 있게 도와주는 다양한 라이브러리들

gql 자체는 쿼리 언어입니다. 이것 만으로는 할 수 있는 것이 없습니다. gql을 실제 구체적으로 활용 할 수 있도록 도와주는 라이브러리들이 몇가지 존재 합니다. gql 자체는 개발 언어와 사용 네트워크에 완전히 독립적입니다. 이를 어떻게 활용 할지는 여러분에게 달려 있습니다.

대표적인 gql 라이브러리 셋에 대한 링크는 2개를 소개합니다. 릴레이는 GraphQL의 어머니인 Facebook이 만들었습니다. 하지만 개인적인 의견으로는 현재(2019년 7월)버전의 릴레이는 사용하기 매우 번거롭게 디자인 되어 있다고 생각합니다. 개인적으로는 아폴로가 사용하기 편했습니다.

실제 GraphQL로 비지니스 로직 작성하기

앞서서 gql에 대한 개념을 익혔고, 비지니스 로직 작성을 간단히 보여드리겠습니다. 구현시, 비지니스 로직은 실제 리졸버 함수에 담지 않습니다. 로직은 비지니스 로직 레이어 (다른 파일의 다른 함수)에 작성을 하는 것을 권장합니다. 위 그림에도 나왔지만 이는 REST API를 제작할때 사용하는 패턴과 동일한 패턴입니다.

    requestPaymentSession: async (parent, { 
      pgId, name, sex, birthDay, phoneNumber, amount, productName, ref 
    }, context, info) => {
      const ret = await requestPaymentSession({ pgId, name, birthDay, phoneNumber, sex, amount, productName, ref })

      return removeSymbol(ret)
    },
    requestPaymentApprove: async (parent, {
      sessionKey, authNumber
    }, context, info) => {
      const ret = await requestApprovePayment({ sessionKey, authNumber })

      return removeSymbol(ret)
    }

실제 구현한 비지니스 로직 관련 리졸버

정리

gql은 퍼포먼스적인 장점이 분명 존재합니다. 하지만 개인적으로 더 관심이 가는 장점은 바로 생산성 향상입니다. gql은 기존 백앤드-프론트앤드 협업 문화를 많이 바꿀것으로 예상합니다. gql의 협업 구조상 프론트앤드쪽에 조금 더 할일이 많아지고 힘이 실리는 느낌입니다. 에자일하게 웹사이트 프로젝트를 진행하는데 gql이 많은 도움이 될 것이라고 생각합니다.

개발자 여러분에게 안타까운 소식을 전하자면, 이 글을 읽었다고 해서 gql을 바로 실전에서 사용하기는 쉽지 않을 것입니다. 이 글에서는 gql의 클라이언트 모듈에 대해서는 구체적으로 언급하지도 않았습니다. 특히 react를 혼합해서 사용하려면, 또 다시 가파른 고개를 넘어서야 제대로 사용 할 수 있을 것입니다. 요즘 react는 flux 아키텍쳐가 점령 했습니다. flux 아키텍쳐는 아름답지만, flux와 함께 gql을 구현하는 일은 또 다른 숙제가 될 것입니다. 개인적인 생각으로는 apollo client의 local statment management 기능은 flux 아키텍쳐를 구체화하여 구현한 redux를 완전히 대처 가능하다고 생각합니다. 추후에 기회가 된다면 react와 apollo 조합에 대해서 이야기 해볼까 합니다. 항상 공부하는 개발자의 모습은 아름답습니다. 이 세상의 모든 개발자 화이팅입니다.

참고 사이트

https://graphql.org

이 글은 핀플레이 결제 프로젝트를 진행시 Graphql을 도입하며 얻은 경험을 바탕으로 작성하였습니다.

참여 후기: Open Infrastructure & Cloud Native Days Korea 2019

Tue, 23 Jul 2019 10:00:00 +0900

지난 주 18일부터 19일까지 양일간 진행된 Open Infrastructure & Cloud Native Days Korea 2019 행사에 카카오가 후원했습니다. 일정상 행사장에 참여하지 못한 분들에게 카카오가 참여한 내용을 소개합니다.

이번 행사는 OpenStack, Kubernetes, Ceph, OCP 한국 커뮤니티가 힘을 합쳐서 개최하였고, Open Infrastructure 와 관련된 많은 분야를 어우르는 커뮤니티 연합 성격의 컨퍼런스로 진행됐습니다.

오픈 소스 커뮤니티에 참여하고 있는 저희들 입장에서도 하나의 분야가 아닌 서로 연관된 여러 분야의 기술들을 한 자리에서 보고, 서로 논의하고 공유할 수 있는 기회에 카카오가 키노트와 다양한 발표 세션을 포함해 기술 시연 부스에 참가할 수 있어 기뻤습니다.

행사 정보

웹사이트: https://openinfradays.kr/
일시: 2019년 7월 18~19일,. 9:00AM ~ 6:00PM
장소: 페럼타워, 삼화타워, T타워 (을지로입구)
주최: 국내 오픈소스 커뮤니티 (OpenStack, Kubernetes, Ceph, OCP)

부스

카카오의 스폰서 부스에는 카카오의 클라우드 플랫폼인 9rum, Krane 시연과 채용관련 Q&A 질의응답을 진행했습니다. QR 코드를 스캔하면 채용관련 설문으로 연결되고, 응답하신분들께는 라이언/어피치/튜브가 이쁘게 프린트된 유리컵 세트를 드렸습니다. 준비해간 기념품과 경품이 빠르게 소진되어 뒤늦게 방문해주신 분들께 전해드리지 못한 점 양해부탁드립니다.

부스에서 받은 질문중에 가장 재밌었던 질문은 ‘아니 외부 사람은 써보지도 못 할걸 왜 전시하는거에요? 혹시 카카오가 클라우드 잘 하는거 자랑하시려구요?’ 였습니다. 네, 아직은 외부 분들은 사용하지 못하지만 혹시 또 언젠가는 외부에서도 쓸 수 있지 않을까요? 그리고 주요 제품들을 오픈소스화 할 계획을 가지고 있으니까, 꼭 허무 맹랑한 이야긴 아닌것 같습니다. 잘 준비해서 공개할 수 있도록 해보겠습니다.

키노트 세션

Cloud, Current Currents and Directions with open powers

클라우드의 현재 쟁점 이슈(AI 클라우드 서비스화, 이종(heterogeneous)클라우드, 오픈소스진영과 클라우드 벤더간의 라이센싱 이슈)들에 대해서 소개하고, 향후 클라우드가 진화해가는데 있어서 오픈소스와 오픈 인프라가 어떻게 도움을 주는지에 정리해봤습니다. 마지막으로, 카카오가 이런 오픈소스 흐름을 이용해서 앞으로의 클라우드에 적용할지에 대해서도 소개했습니다.

(키노트를 소개한 기사: https://news.v.daum.net/v/20190721094650099)

공용준 / KAKAO

공용준(Andrew)은 카카오에서 클라우드 컴퓨팅 파트에서 클라우드 기술 리딩을 맡고 있으며, 프라이빗/퍼블릭 클라우드 서비스와 그에 필요한 기술들을 연구, 개발해서 실제 서비스에 적용하고 있다. 중소기업 발전을 위해 한국정보화진흥원에서 중소기업 기술 자문위원, 한국 데이터베이스 진흥원 자문위원으로도 활동하고 있다. 2011년에 정통부 산하의 클라우드 정책 연구단 기술고문을 역임했으며, 주요 저서로는 『카프카: 데이터 플랫폼의 최강자』(책만,2018),『클라우드 API를 활용한 빅데이터분석』(에이콘,2015), 『실전 클라우드 인프라 구축기술(한빛, 2014)』이 있다.

발표 세션

DAY-1, 15:00 ~ 15:40 @ Track 3

kubernetes scheduler deep dive

Kubernetes scheduler component의 동작방식 및 알고리즘에 대해 알아보고 scheduler 확장에 대해서 알아 봅니다.

김동진 / 카카오뱅크

카카오뱅크에서 cloud native 사업의 일환으로 퍼블릭 클라우드 도입을 준비중입니다.특히 컨테이너 서비스를 위한 Kubernetes 플랫폼 구축 및 설계를 담당하고 있습니다.

DAY-1, 17:00 ~ 17:40 @ Track 3

Source to URL without Dockerfile

Knative와 buildpack을 이용해서 dockerfile이 없는 소스의 코드를 분석해서 컨테이너화 한 다음에 Kubernetes 클러스터에 실행하는 방법을 알아봅니다. 서버리스 플랫폼인 knative의 전반적인 내용과 buildpack.io의 내용을 살펴봅니다. 간단한 시연을 포함해서 발표를 보신 분들이 knative와 buildpack을 사용해 보실 수 있는 방법을 안내합니다.

정원천 / KAKAO

카카오의 내부 컨테이너 클라우드 플랫폼을 개발하고 있습니다. 최근에는 어떻게하면 유용한 컨테이너 플랫폼을 만들고 효율적으로 안정적인 운영을 할 수 있을지를 많이 생각하고 있습니다.

카카오 클라우드디플로이셀 셀장
Certified Kubernetes Administrator

DAY-2, 12:00 ~ 12:40 @ Track 2

카카오 T 택시 사례를 통해 살펴보는 카카오 클라우드의 Kubernetes as a Service

카카오의 프라이빗 클라우드 환경에서 KaaS(Kubernetes as a service) 를 개발/운영하며 겪어온 시행착오와 아키텍처 개선 작업들, 수 백 개의 쿠버네티스 클러스터 들을 서비스로서 제공하기 위해 개발한 유용한 기능들을 소개합니다. 그리고 ‘카카오 T 택시’ 에 적용된 쿠버네티스 기반 서비스 사례를 통해 실제 서비스에서의 적용 과정과 운영은 어떻게 되고 있는지 공유합니다.

홍석용 / KAKAO

Works- OpenStack 기반 LG전자 및 LG 그룹사 Private Cloud 구축/운영
OpenStack Ironic(bare Metal) 구축 및 Inhouse Driver 개발
카카오 클라우드 Mesos as a service, DKOSv2 운영
카카오 클라우드 Kubernetes as a service, DKOSv3 개발/운영Community Activity
2017 OpenStack Day: 하이브리드 클라우드를 위한 Horizon AWS Plugin
2018 OpenInfra Day: Mesos to Kubernetes, Cloud Native 서비스를 위한 여정
쿠버네티스 코믹스 한글화: https://goo.gl/5mTvtm

박광열 / KAKAO

티몬 물류 시스템 개발/운영
카카오 T for business 플랫폼 개발/운영
카카오 T 택시 서버 개발/운영

DAY-2, 14:00 ~ 14:40 @ Track 2

KOCOON – KAKAO Automatic K8S Monitoring

기존 모니터링 시스템(KEMI)에서 KOCOON을 진행한 이유
대용량 K8S Cluster 모니터링 자동화를 진행하면서 겪었던 내용들에 대해 공유
(#kocoon #k8s #prometheus #helm #chart #OOM)

임성국 / KAKAO

웹공학 석사 @ KAIST
공통플랫폼 개발 @ ETRI
Open API GW 개발 @ KT
KAKAO Monitoring Cloud 개발 @ KAKAO

앞으로도 카카오는 개발자 커뮤니티에 대한 지속적인 후원과 기술 발표 및 강연에 적극 참여하도록 하겠습니다. 많은 관심과 응원 부탁드립니다.

kubernetes를 이용한 서비스 무중단 배포

Mon, 24 Dec 2018 10:00:00 +0900

Kubernetes는 컨테이너 오케스트레이션 영역에서 거의 표준으로 자리 잡은 오픈소스 시스템입니다. kubernetes를 사용하게 되면 여러대의 노드를 하나의 클러스터로 묶어서 사용가능하게 됩니다. 클러스터를 구성하는 노드들중에 일부에 장애가 발생하더라도 장애가 난 곳에 있던 컨테이너가 kubernetes에 의해 다른 정상상태의 노드로 옮겨가게 되어서 컨테이너로 제공하던 서비스에 지장이 없이 서비스가 지속될 수 있게 해줍니다. 그래서 실제로 서비스를 운영할 때는 컨테이너만을 단독으로 사용하기 보다는 이런 오케스트레이터와 함께 사용하는 경우가 많습니다.

kubernetes를 사용하면 배포를 보다 편리하게 할 수 있다는 장점도 있습니다. 앱을 실행할 컨테이너만 준비해서 kubernetes에 제출하면 kubernetes가 알아서 배포절차를 진행합니다. 카카오에서 컨테이너 플랫폼을 운영하면서 가장 많이 받는 질문중 하나가 “배포중에 트래픽 유실은 없나요?” 입니다. 트래픽이 큰 서비스를 운영하면서 서비스의 품질을 유지하려면 배포중에도 트래픽 유실이 없어야 합니다. 이 글에서는 kubernetes를 사용해서 배포했을때 트래픽 유실이 없게하기 위해서 어떤 점들을 유의해야 하는지 알아보도록 하겠습니다.

kubernetes pod, service, ingress 관계

먼저 kubernetes로 트래픽이 들어오는 구조를 살펴보도록 하겠습니다. kubernetes클러스터 내부에 있는 pod까지 트래픽이 도달하는 경로는 대략 다음과 같습니다.

kubernetes는 별도의 클러스터 네트워크를 구성해서 이뤄지는 경우가 많기 때문에 외부에서 클러스터 내부에서 실행중인 pod에 접근하기 위해서는 인입되는 트래픽을 클러스터 내부까지 전달해줄 LB역할을 해줄 매개체가 필요한데요. AWS, GCP, Azure같은 Public cloud를 사용할때는 거기서 제공해주는 LB를 사용하면 되지만, 내부에 구축할때는 일반적으로 앞의 그림에 있는 ingress-controller를 사용합니다. ingress-controller에도 여러가지 종류가 있지만 이 글에서는 일반적인 nginx ingress controller를 기준으로 이야기하겠습니다. Kubernetes 내부에서 pod간 통신을 위해서는 중간에 service를 두고 통신하게 되는데요. ingress를 설정할때 역시 개별 pod들을 이용하는게 아니라 pod와 연결된 service를 설정하도록 되어 있습니다. 다음 ingress 설정을 보시면 serviceName으로 ingress를 통해서 연결하려는 서비스를 지정한 걸 확인할 수 있습니다.

apiVersion: extensions/v1beta1
kind: Ingress
metadata:
  name: test-ingress
  annotations:
    nginx.ingress.kubernetes.io/rewrite-target: /
spec:
  rules:
  - http:
      paths:
      - path: /testpath
        backend:
          serviceName: test
          servicePort: 80

이렇게 설정되면 실제 nginx-ingress-controller는 이 service를 통해서 pod에 연결하는게 아니라 이 service에 연결된 pod의 정보를 가져와서 직접 nginx config로 설정하게 됩니다. 그래서 위의 그림에서는 service를 이용하긴하지만 직접 service를 거쳐서 통신하는건 아니라는 의미에서 service영역을 점선으로 표시했습니다.

kubernetes pod 배포시 기본 구조

앞에서 서비스 트래픽이 실제 어떻게 pod까지 전달되는지 알아봤습니다. 이제 실서비스에서 트래픽이 흘러가고 있는 와중에 pod를 어떻게 무중단으로 배포할 수 있는지 알아보도록 하겠습니다. 우선 pod가 배포되면 pod 교체가 어떻게 일어나는지 살펴보도록 하겠습니다. 정상적인 경우라면 아래 그림처럼 새로운 pod(v2)가 생성되고 헬스체크가 성공한 후에 트래픽이 pod(v2)쪽으로 흘러가게 됩니다. 그 후에 pod(v1) 쪽으로 가던 트래픽이 제거된 후 pod(v1)이 제거 됩니다.

이 과정에서 고려해야 할 부분들이 몇 군데 있습니다.

kubernetes 배포시 고려해야할 컨테이너 구성

Kubernetes 가 대부분의 배포 절차를 잘 수행해 주지만 컨테이너 내부에서도 종료될때 graceful shutdown구현이 필요합니다. 새로운 pod가 실행되고 이전 pod를 종료할때 kubernetes에서 노드의 컨테이너를 관리하는 프로세스인 kubelet은 먼저 pod에 SIGTERM 신호를 보내게 됩니다. 컨테이너에서 SIGTERM을 받았을때 기존에 처리중이던 요청에 대한 처리를 완료하고 새로운 요청을 받지 않도록 개발되어 있어야 합니다. 그렇지 않으면 아래 그림처럼 트래픽은 아직 Pod(v1)쪽으로 가고 있는데 Pod(v1)이 종료되어 버려서 아직 ingress-controller의 설정이 갱신되기 전에 pod(v1)으로 가는 요청들은 에러를 내게 됩니다. kubelet에서 pod에 SIGTERM을 보낸후에 일정시간동안 graceful shutdown이 되지 않는다면 강제로 SIGKILL을 보내서 pod를 종료하게 됩니다. 이 대기 기간은 terminationGracePeriodSeconds 으로 설정해 줄 수 있고 기본 대기 시간은 30초 입니다.

SIGTERM 수신 뒤 즉시 종료 : 17.44% Request 502 error

SIGTERM 시그널 처리시 : 무중단 배포 가능

kubernetes 배포시 고려해야할 kubernetes 옵션

컨테이너가 SIGTERM을 고려해서 잘 만들어져 있다면 kubernetes에서 배포 과정에 어떤 옵션들을 활용할 수 있는지 살펴보겠습니다.

먼저 pod의 롤링업데이트를 위한 maxSurge와 maxUnavailable 설정 옵션입니다. deployment를 이용해서 배포할 때 maxSurge는 deployment에 설정되어 있는 기본 pod개수보다 여분의 pod가 몇개가 더 추가될 수 있는지를 설정할 수 있습니다. maxUnavailable는 업데이트하는 동안 몇 개의 pod가 이용 불가능하게 되어도 되는지를 설정하는데 사용됩니다. 이 두개의 옵션을 운영중인 서비스의 특성에 맞게 적절히 조절해 주어야지 항상 일정 개수 이상의 pod가 이용가능하게 되기 때문에 배포중 트래픽 유실이 없게 됩니다. 둘 다 한꺼번에 0으로 설정되면 pod가 존재하지 않는 경우가 발생하기 때문에 한꺼번에 0으로 설정할 수는 없습니다.

그 다음으로는 pod의 readinessProbe 설정입니다. kubernetes에서는 pod의 헬스체크를 확인하기 위해서 2가지 상태체크 옵션을 주고 있습니다. livenessProbe와 readinessProbe입니다. livenessProbe는 컨테이너가 살아 있는지 확인하는 역할을 하고 이 헬스체크가 실패하면 kubelet이 컨테이너를 죽이게 됩니다. 그리고 컨테이너의 restart policy에 따라 컨테이너가 재시작됩니다. 무중단 배포에서 신경써서 봐야할 설정은 readinessProbe입니다. readinessProbe는 실제로 컨테이너가 서비스 요청을 처리할 준비가 되었는지를 확인하는데 사용됩니다. readinessProbe가 ok상태여야지 이 pod와 연결된 service에 pod의 ip가 추가되고 트래픽을 받을 수 있게 됩니다. 자바 프로세스 같은 경우는 프로세스가 올라와서 livenessProbe가 ok상태가 되더라도 초기화 과정이 오래 걸리기 때문에 readinessProbe를 따로 설정하지 않을때에 아직 준비되지 않은 컨테이너로 요청이 가서 응답을 제대로 하지 못하고 실패할 수 있습니다. 그런 경우를 방지하기 위해서 실제 서비스가 준비된 상태인지를 확인할 수 있는 readinessProbe를 잘 설정해 주어야 합니다.

경우에 따라서는 앱 자체가 readinessProbe를 설정해주기 어려운 상황일 수도 있습니다. 그럴때는 .spec.minReadySeconds 옵션을 이용하면 어느정도 readinessProbe와 비슷한 효과를 낼 수 있습니다. .spec.minReadySeconds은 pod의 status가 ready가 될때까지의 최소대기시간입니다. 그래서 pod가 실행되고나서 .spec.minReadySeconds에 설정된 시간동안은 트래픽을 받지 않습니다. 그렇기 때문에 readinessProbe를 설정하기 어렵고 초기화 시간이 오래 걸리는 컨테이너에 대해서 사용하면 컨테이너가 준비될때까지 일정시간동안 트래픽을 받지않고 대기할 수 있기 때문에 유용하게 사용할 수 있습니다. 하지만, readinessProbe가 완료되면 .spec.minReadySeconds에 설정된 시간이 아직 남아 있더라고도 무시되고 트래픽을 보내게 됩니다. .spec.minReadySeconds의 기본값은 0입니다.

MinReadySeconds 옵션 : pod status 가 ready 로 업데이트 될 때 까지 최소 대기 시간, 그 전까지 서비스에서 트래픽 받지 않음

Readiness Check 가 완료 되면 MinReadySeconds 설정은 무시된다.

pod가 종료될때 graceful shutdown을 구현하지 못하는 경우도 있을 수 있습니다. 앱이 사용하는 언어나 프레임워크가 지원하지 않는 경우도 있고, 오래된 레거시라서 앱을 수정하지 못한채 컨테이너로 올려야되는 경우도 있을 수 있습니다. 이런 경우에는 prestop hook을 이용할 수 있습니다. kubernetes에서는 pod 라이프사이클중에 hook을 설정할 수 있습니다. pod가 실행되고난 직후 실행하는 poststart hook과 pod가 종료되기 직전 실행되는 prestop hook입니다. prestop 훅은 pod에 SIGTERM을 보내기 전에 실행되기 때문에 prestop을 이용하면 앱과 별개로 graceful shutdown의 효과를 내게 할 수도 있습니다. Prestop 훅의 실행이 완료되기 전까지는 컨테이너에 SIGTERM을 보내지 않기 때문에 앱의 구현과는 별개로 종료되기 전에 대기시간을 주는 것도 가능해 지게 됩니다. 하지만 이렇게 prestop 훅으로 대기시간을 주더라도 terminationGracePeriodSeconds 시간을 초과한다면 프로세스 종료가 일어날 수 있으니 염두에 두고 사용해야 합니다.

위 내용은 카카오 사내 컨테이너 오케스트레이션 서비스인 DKOS를 운영하던 중 많이 나오는 문의사항을 토대로 배포시 고려해야 할 kubernetes 구조와 옵션 등을 살펴봤습니다. DKOS는 클라우드디플로이셀의 hardy.jung, dennig.hong, scott.vim, heimer.j등이 함께 운영해오고 있습니다.

kakao의 오픈소스 Ep9 - Khaiii : 카카오의 딥러닝 기반 형태소 분석기

Thu, 13 Dec 2018 10:00:00 +0900

“카카오의 오픈소스를 소개합니다” 아홉 번째는 jamie.lim과 자연어 처리 파트 동료들이 함께 개발한 khaiii(Kakao Hangul Analyzer III)입니다.

khaiii는 세종 코퍼스를 이용하여 CNN(Convolutional Neural Network, 합성곱 신경망) 기술을 적용해 학습한 형태소 분석기입니다. 디코더를 C++로 구현하여 GPU 없이도 비교적 빠르게 동작하며, Python 바인딩을 제공하고 있어서 편리하게 사용하실 수 있습니다.

앞으로 오픈소스 생태계를 통해 자연어 처리를 연구하는 분들께 도움이 되고, 또한 부족한 부분에 대해 도움을 받을 수 있으면 좋겠습니다.

아래는 카카오 AI 리포트에 포스팅한 카카오의 딥러닝 기반 형태소 분석기를 옮긴 것입니다.

khaiii는 “Kakao Hangul Analyzer III”의 첫 글자들만 모아 만든 이름으로 카카오에서 개발한 세 번째 형태소 분석기입니다. 두 번째 버전의 형태소 분석기 이름인 dha2(Daumkakao Hangul Analyzer 2)를 계승한 이름이기도 합니다. 기존의 분석기(dha1, dha2)는 규칙 기반으로 동작하기 때문에 사람이 직접 지속적으로 규칙을 입력해야 하지만, khaiii는 데이터 기반으로 동작하기 때문에 기계학습 알고리즘(딥러닝)을 사용합니다.

‘형태소’는 언어학에서 특정한 의미를 가지는 가장 작은 말의 단위로 발화체 내에서 따로 떼어낼 수 있는 것을 말합니다. 즉, 더 분석하면 뜻이 없어지는 말의 단위입니다. 형태소 분석기는 단어를 보고 형태소 단위로 분리해내는 소프트웨어를 말합니다. 이러한 형태소 분석은 자연어 처리의 가장 기초적인 절차로 이후 구문 분석이나 의미 분석으로 나아가기 위해 가장 먼저 이루어져야 하는 과정이라고 볼 수 있습니다¹.

데이터 기반

기존 버전이 사전과 규칙에 기반해 분석을 하는 데 반해 khaiii는 데이터(혹은 기계학습) 기반의 알고리즘을 이용하여 분석을 합니다. 학습에 사용한 코퍼스(corpus)는 국립국어원에서 배포한 21세기 세종계획 최종 성과물을 카카오에서 일부 내용을 추가하거나 오류를 수정한 것입니다. 전처리 과정에서 오류가 발생하는 문장을 제외하고 약 85만 개의 문장, 그리고 1천만 개 어절의 코퍼스를 사용하여 학습을 했습니다. 코퍼스와 품사 체계에 대한 구체적인 내용은 뒤에 자세히 설명드리도록 하겠습니다.

알고리즘

기계학습을 위해서는 신경망 알고리즘들 중 CNN(Convolutional Neural Network, 콘볼루션 신경망)을 사용하였습니다. 한국어에서 형태소 분석은 자연어 처리를 위한 가장 기본적인 전처리 과정이므로 속도가 매우 중요한 요소라고 생각합니다. 따라서 자연어 처리에 많이 사용하는 LSTM(Long-Short Term Memory, 장단기 메모리)와 같은 RNN(Recurrent Neural Network, 순환 신경망) 알고리즘은 속도 면에서 활용도가 떨어질 것으로 예상하여 고려 대상에서 제외하였습니다.

음절 기반 모델

한국어 형태소 분석 결과는 원형 복원, 불규칙 활용 등의 이유로 입력 문자와는 형태와 길이가 달라지게 됩니다. 예를 들어, ‘져줄래’와 같은 입력 어절의 분석 결과는 ’지/VV + 어/EC + 주/VX + ㄹ래/EF’와 같이 출력의 길이와 형태 모두 쉽게 예측이 가능하지 않습니다. 이러한 길이의 불일치 문제가 있기에 기계학습 분류기에 기반한 모델의 출력을 설계하는 부분이 중요합니다.

기존에 고전적인 HMM(Hidden Markov Model, 은닉 마르코프 모델), CRF(Conditional Random Fields, 조건부 랜덤 필드) 등의 방법에서는 트라이(TRIE) 사전을 이용하여 들쑥날쑥한 형태의 격자(lattice)를 비터비(Viterbi) 알고리즘을 통해 최적의 경로를 탐색하는 형식으로 많이 접근해 왔습니다.

최근의 딥러닝 방법으로는 번역에서 많이 사용하는 seq2seq(sequence to sequence) 방식을 가장 먼저 생각해 볼 수 있습니다. ‘져, 줄, 래’라는 입력 원문에 대해 인코더를 통해 latent 벡터를 생성하고 디코더를 통해 차례대로 ’지/VV, 어/EC, 주/VX, ㄹ래/EF’라는 출력을 생성하는 것입니다. 여기에 당연히 어텐션(attention) 메커니즘을 적용할 수 있겠습니다. 그러나 seq2seq 방식에서 주로 사용하는 RNN은 속도가 느리고, 입력 음절과 출력 형태소 간의 연결 정보가 끊어져 형태소 분석 결과가 입력의 어느 부분으로부터 나왔는지에 대한 정보가 소실되는 단점이 있습니다. 이에 khaiii는 입력된 각 음절에 대해 하나의 출력 태그를 결정하는 분류 문제로 접근합니다.

음절과 형태소의 정렬

입력의 경우 각각의 음절이 분류 대상입니다. 형태소 분석 결과를 다시 형태소 각각의 음절 별로 나누어 IOB1 방식으로 표현하면 다음과 같습니다.

이렇게 나뉜 각각의 음절들은 아래와 같이 정렬됩니다.

‘했’은 ‘I-VX:I-EP:0’라는 복합 태그를 갖는 반면, 나머지 음절들은 단순 태그를 갖습니다. 복합 태그와 단순 태그의 차이는 원형 복원 사전의 사용 여부와 관련이 있습니다. 음절과 복합 태그를 합친 ‘했/I-VX:I-EP:0’를 key로 하여 원형 복원 사전을 검색하면 ‘하/I-VX, 였/I-EP’이라는 복원 정보를 얻게 됩니다. 이렇게 음절과 형태소를 정렬하고 태그로부터 원형을 복원하는 방식은 심광섭 교수님의 논문²에서 기본적인 아이디어를 차용했습니다.

코퍼스에서 모든 음절에 대해 형태소 분석 결과와 정렬을 수행하고, 필요한 경우 복합 태그를 ‘I-VX:I-EP:1’, ‘I-VX:I-EP:2’와 같이 순차적으로 생성하면 자동으로 원형 복원 사전도 생성하게 됩니다. 아래는 이렇게 생성된 학습 데이터의 예시입니다.

그리고 아래는 동시에 자동으로 생성된 원형 복원 사전입니다.

이렇게 모든 코퍼스 내 어절의 정렬을 마치고 나면 92개의 고정된 단순 태그와 400여 개의 복합 태그가 생성됩니다. 이때 정렬은 수작업으로 작성한 규칙과 매핑(mapping) 사전을 사용해 자동으로 정렬이 이뤄지고, 정렬에 실패한 문장은 학습에서 제외했습니다. 그러면 비로소 각각의 입력 음절에 대해 500여 개의 출력 태그를 판단하는 분류 문제로 접근할 수 있게 됩니다.

윈도우와 문맥

하나의 음절에 대한 태그를 판단하기 위해 윈도우 크기만큼 좌/우로 확장한 문맥을 사용합니다. 예를 들어 ‘프랑스의 세계적인 의상 디자이너 엠마누엘 …’이라는 입력에 대해 ‘세’라는 음절의 태그를 판단하기 위해 윈도우 크기가 7인 문맥은 아래와 같습니다.

실질적인 음절 이외에 가상의 음절들도 문맥으로 사용하는데, 이는 아래와 같습니다.

네트워크 구조

위 네트워크는 윈도우가 7이고 음절의 임베딩 크기는 5, 커널(kernel)의 크기가 3인 4개의 필터를 사용한 콘볼루션(convolution)입니다. 크기가 [15, 5]인 문맥을 하나의 필터를 거치면 길이가 13인 하나의 벡터가 생성되고 전체에 대해 최댓값 선택(max pooling)을 적용하면 하나의 스칼라 값(scalar value)이 됩니다. 4개의 필터를 사용했으므로 최종적으로 길이가 4인 벡터가 나오게 됩니다.

이런 방식으로 커널의 크기가 {2, 3, 4, 5}에 대해 각각 길이가 4인 벡터를 연결하여 길이가 16인 벡터를 생성합니다. 이것을 히든(hidden) 레이어와 출력 레이어를 거쳐 최종적으로 태그를 결정하게 됩니다.

실제로 베이스(base) 모델의 경우 윈도우 크기가 3, 임베딩 크기는 30입니다. 필터의 출력 차원은 임베딩과 같이 30을 사용했고, {2, 3, 4, 5} 네 종류의 커널을 거치고 나면 길이가 120인 벡터가 생성됩니다. 최종 출력 태그 개수는 500이며 hidden 레이어의 차원은 120과 500의 중간인 310입니다.

이러한 콘볼루션 방식은 김윤님의 문장 분류에 관한 논문³을 참고하였습니다. 문장을 문맥에 대입하고 단어는 음절에 대입하여 적용하면 됩니다.

성능

1. 정확도

CNN 모델의 주요 하이퍼파라미터(hyperparameter)는 분류하려는 음절의 좌/우 문맥의 크기를 나타내는 win 값과, 음절 임베딩의 차원을 나타내는 emb 값입니다. win 값은 {2, 3, 4, 5, 7, 10}의 값을 가지며, emb 값은 {20, 30, 40, 50, 70, 100, 150, 200, 300, 500}의 값을 가집니다. 따라서 이 두 가지 값의 조합은 6 x 10으로 총 60가지를 실험하였고 아래와 같은 성능을 보였습니다. 성능 지표는 정확률과 재현율의 조화 평균값인 F-Score입니다.

파라미터 win의 경우 3 혹은 4에서 가장 좋은 성능을 보이며 그 이상에서는 오히려 성능이 떨어집니다. 파라미터 emb의 경우 150까지는 성능도 같이 높아지다가 그 이상에서는 별 차이가 없습니다. 최상위 5위 중 비교적 작은 모델은 win=3, emb=150으로 F-Score 값은 97.11입니다. 이 모델을 라지(large) 모델이라 명명합니다.

2. 속도

모델의 크기가 커지면 정확도가 높아지기는 하지만 그만큼 계산량 또한 많아져 속도가 떨어집니다. 그래서 적당한 정확도를 갖는 모델 중에서 크기가 작아 속도가 빠른 모델을 기본(base) 모델로 선정하였습니다. F-Score 값이 95 이상이면서 모델의 크기가 작은 모델은 win=3, emb=30, F-Score의 값은 95.30입니다. 속도를 비교하기 위해 1만 문장(총 903KB, 문장 평균 91)의 텍스트를 분석하여 비교했습니다. 기본 모델의 경우 약 10.5초, large 모델의 경우 약 78.8초가 걸립니다.

코퍼스

1. 세종 코퍼스

세종 코퍼스는 국립국어원에서 1998년부터 2007년까지 10년간 진행한 ‘21세기 세종계획’ 사업의 결과물 중 코퍼스 부분을 말합니다. 여기에 있는 다양한 코퍼스 중 형태 분석 말뭉치가 바로 khaiii의 학습 데이터입니다. 세종 코퍼스에 관한 자세한 내용은 황용주 님이 새국어생활에 2016년에 게재한 글⁴을 참고하시기 바랍니다. 세종 결과물 배포 이후 이를 활용한 여러 논문이 발표되고, 여러 차례 시스템 경진대회의 개최와 오픈소스 바람으로 인해 세종 코퍼스와 품사 집합은 사실상 표준으로 자리 잡고 있습니다. 그러나 1천만 개 어절이라는 방대한 양에 걸맞게 오류 또한 많이 포함하고 있습니다.

2. 문종 프로젝트

카카오에서는 이러한 오류 중 약 30만 개 이상의 어절을 수정하였고 여전히 발견되는 오류를 수정하고 있습니다. 내부적으로는 이것을 ‘문종 프로젝트’라는 이름으로 진행하고 있습니다.⁵ 문종 프로젝트의 결과물을 공개하여 협력을 통해 발전해 가고자 제안⁶을 드렸지만, 아쉽게도 저작권 문제로 공개할 수 없게 되었습니다.

3. 학습 코퍼스

세종 코퍼스를 수정한 1천만 개의 어절에 더해 저희가 자체적으로 구축한 6만 개 어절의 코퍼스를 합하여 학습에 사용했습니다. 음절과 형태소의 정렬을 거치고 나면 최종적으로 약 85만 개의 문장과 1,003만 개의 어절이 전체 학습 코퍼스가 됩니다. 이 중 1만 개의 문장을 제외한 뒤 학습을 하고, 1만 개의 문장은 다시 5천 개씩 나눠 각각 dev, test 코퍼스로 활용했습니다.

4. 품사 집합

세종 코퍼스의 품사 집합을 대부분 그대로 따르고 있지만, SWK・ZN・ZV・ZZ 4가지만 원본 품사 집합과 다릅니다. ZN・ZV・ZZ는 세종 품사 집합에서 각각 NF・NV・NA와 동일합니다. SWK의 경우 한글 자모만으로 이뤄진 형태소에 한해 사용했고 SW에 완전히 포함되는 하위 품사입니다. NF・NV의 경우 품사는 정의되어 있지만 세종 코퍼스에 한 번도 나타나지 않습니다. 추정 범주에 해당하는 품사는 NA만 나타나고 있는데, 카카오는 한글 자모가 나타나는 경우, 또는 띄어쓰기에 오타가 있는 경우에 한해 제한적으로 사용하였습니다. 아래는 그러한 예시들입니다.

Appendix - 품사 집합

참고문헌

참고 https://ko.wikipedia.org/wiki/%ED%98%95%ED%83%9C_%EB%B6%84%EC%84%9D ↩
논문 : 심광섭, “음절 단위의 한국어 품사 태깅에서 원형 복원”, 소프트웨어 및 응용 제40권 제3호, 2013. ↩
논문 Yoon Kim, “Convolutional Neural Networks for Sentence Classification”, EMNLP, 2014. ↩
참고 황용주 외 1인, “21세기 언어 말뭉치 제대로 살펴보기”, 새국어생활, 2016. ↩
논문 한경은 외 2인, “공개와 협업을 통한 세종 형태 분석 말뭉치 오류 개선 방법”, 한글 및 한국어정보처리학술대회, 2017. ↩
참고 https://ithub.korean.go.kr/user/member/memberQnaView.do?boardSeq=7&articleSeq=94 ↩

2019 카카오 블라인드 공채 2차 오프라인 코딩 테스트 문제 해설

Tue, 23 Oct 2018 10:00:00 +0900

지난 10월 6일(토) 2019 블라인드 공채 오프라인 2차 코딩테스트가 진행되었습니다. 작년에는 8시간 동안 온라인으로 진행한 것과는 달리 오프라인으로 5시간 동안 치러졌는데요, 어떤 의도로 출제하였는지 살펴보겠습니다.

작년 2차 코딩테스트 회고

작년 문제 출제 의도를 기억하시는지요?

온라인 2차 코딩 테스트 문제 출제 위원회에서는,
- 탄탄한 기본기를 바탕으로 새로운 것을 빠르게 습득하는 역량
- 요구사항을 꼼꼼하게 분석하고, 트레이드오프를 고려하여 디자인하여 구현하는 역량
- 결과를 모니터링하며 점진적으로 개선해나가는 역량
을 테스트할 수 있도록 2차 문제에 녹여내고자 하였습니다.

작년 문제에는 매우 많은 장치가 숨겨져 있었으나 정작 요구사항을 그대로 구현하기만 해도 합격선인 8만 점을 얻기에는 충분했었습니다.

그리하여 올해는 시스템 디자인 역량을 좀 더 중점적으로 평가하고자 하였습니다.

엘리베이터 시뮬레이션

올해 오프라인 2차 테스트 문제는 다수의 엘리베이터(1대~4대)를 제어하는 시스템을 구현하는 것입니다. 핵심 구현에 집중할 수 있도록 엘리베이터 동작 및 상태는 서버에서 관리하고, 서버와 통신은 작년과 같이 REST API 및 JSON 포맷으로 주고받도록 하였습니다.

지원자는 주어진 빌딩별 승객 트래픽을 분석하여 가정 적합한 엘리베이터 제어 알고리즘을 구현해야 합니다.

지원자가 제어할 엘리베이터 시스템은 다음과 같습니다.

Timestamp (시간)

엘리베이터 시스템은 가상의 시간을 사용하며 timestamp라 부른다.
Timestamp는 0부터 시작하고 엘리베이터에 명령을 내릴 때마다 1씩 증가한다.

Call (승객)

승객이 엘리베이터 탑승을 위해 보내는 요청, 방향 버튼을 누르는 행위를 call이라 표현한다. Call에는 탑승하려는 층과 목적지 층이 포함된다.
어떤 승객을 태우거나 내려줄지도 엘리베이터 제어 시스템이 결정해야 한다. 승객은 스스로 타거나 내리지 않는다.
내리려는 층과 다른 층에 승객을 내려주면 다시 엘리베이터를 타기 위해 대기한다.

엘리베이터

엘리베이터는 여러 대가 존재하며 모두 사용할 수도 있고 일부만 사용해도 된다.
엘리베이터에 명령을 내려 각각의 엘리베이터를 층을 이동하거나 멈추고, 문을 열 거나 닫고, 승객을 태우거나 내려 줄 수 있다.
엘리베이터는 정원이 있어 정해진 수 이상의 승객을 태울 수 없다.
엘리베이터에는 현재 상태를 표현하는 status가 있으며, 값으로는 STOPPED, OPENED, UPWARD, DOWNWARD가 있다.
사용할 수 있는 명령은 다음과 같다.

명령	설명
`STOP`	엘리베이터를 멈춘다. 현재 층에 머무르기 원하는 경우 `STOP` 명령을 통해 머무를 수 있다.
`UP`	엘리베이터를 한 층 올린다. 최상층인 경우 현재 층을 유지한다.
`DOWN`	엘리베이터를 한 층 내린다. 1층인 경우 1층을 유지한다.
`OPEN`	엘리베이터의 문을 연다. 엘리베이터의 문이 열린 상태를 유지하기 위해서는 `OPEN` 명령을 사용한다.
`CLOSE`	엘리베이터의 문을 닫는다.
`ENTER`	엘리베이터에 승객을 태운다.
`EXIT`	엘리베이터의 승객을 내린다. 목적지가 아닌 곳에서 내린 경우, OnCall API의 `calls`에 내린 층과 내린 시점의 timestamp로 변경되어 다시 들어가게 된다.

명령에 따른 status 전환을 그림과 표로 표현하면 아래와 같다.

문제의 특징 및 의도

엘리베이터 1대의 동작은 대부분 지원자에게 친숙할 것입니다. 우리가 실생활에서 자주 접하는 엘리베이터 알고리즘은 “collective control”, “elevator algorithm” 등으로 불리는데 아래와 같이 2가지 규칙으로 구성됩니다.

엘리베이터 내에 탑승객이 있거나 현재 진행 방향의 앞쪽에 같은 진행 방향으로 이동하고자 하는 승객이 있으면, 현재의 방향을 유지한다.
현재 진행 방향의 요청들을 전부 처리하고 나면, 반대 방향의 요청을 처리하기 위해 방향을 전환한다. 만약 반대 방향의 요청이 없다면 멈추어 요청을 기다린다.

간단하고 직관적인 알고리즘입니다. 운영체제 수업을 열심히 들은 학생이라면 디스크 스케줄링 알고리즘 중 하나인 look 알고리즘을 떠올릴 수도 있겠습니다.

반면, 복수의 엘리베이터를 제어하기 위해서는 추가로 승객의 요청을 어느 엘리베이터에 할당할 것인지를 결정해야 합니다. 얼핏 보면 간단해 보이는 이 요구사항의 추가로 시스템은 제법 복잡해지게 됩니다. 어느 엘리베이터에 승객을 할당하는 것이 효율적인지 비용 계산을 해야 하고, 승객이 어디에 탑승하고 있는지를 관리해야 합니다. 층별로 구역을 나누어 운행한다면(홀/짝, 고층/저층 분리 운영 등) 환승 기능도 구현해야 합니다.

1대의 엘리베이터 제어는 쉽고 간단해 보이지만, 3문제를 모두 풀기 위해서는 반드시 복수 엘리베이터를 제어해야 합니다. 또한 각 문제의 승객 패턴도 다르고, 승객 패턴에 따라 효율적으로 엘리베이터를 구성해야 합니다. 따라서 시스템 디자인 시 다양한 엘리베이터 알고리즘을 실험할 수 있도록 추상화 & 모듈화를 통해 변경에 유연하도록 디자인해야 합니다. 실제 내부 모의 검증 시에도 문제 요구사항 분석 없이 1대만 먼저 운행하는 식으로 시작한 피실험자의 경우, 여러 대를 제어하는 시스템으로 리팩토링하는 단계에서 시간을 너무 소모하여 시간 내에 문제를 다 풀지 못하는 경우가 속출하였습니다.

승객 트래픽 모델링

엘리베이터 요청은 크게 3가지로 분류할 수 있습니다. (빌딩의 입구는 1층이라고 가정) (참고: https://beta.vu.nl/nl/Images/werkstuk-boer_tcm235-91327.pdf)

incoming: 1층에서 특정 층으로 이동하는 요청
outgoing: 특정 층에서 1층으로 이동하는 요청
inter-floor: 1층을 제외한 층간 이동

이번 테스트에서는 총 3개의 빌딩을 제시했습니다.

첫 번째 어피치 맨션의 경우 5층 높이의 작은 맨션이고 총 요청은 6개입니다. 쉬운 문제를 통해 엘리베이터 시스템에 익숙해지고 API 연동을 해보는 몸풀기 문제라 할 수 있습니다.

두 번째 제이지 빌딩은 25층 건물에 요청은 200개입니다. 위의 3가지 타입의 요청이 적절히 섞여 있는 가장 일반적인 형태의 모델이라고 할 수 있습니다.

세 번째 라이언 타워는 25층 건물에 요청은 500개입니다. 라이언 타워는 승객의 패턴을 제공하고, 이에 맞는 효율적인 엘리베이터 분배 알고리즘을 구현하도록 유도한 문제입니다. 입구는 1층이고, 2층-12층은 개별 회사에 임대를 하고, 13층-25층은 카카오가 사용합니다. 따라서 2층-12층 내에서는 층간 이동이 거의 없는 반면, 13층-25층 사이에서는 층간 이동이 빈번합니다. 또한 13층에 카카오프렌즈샵이 위치하여 1층과 13층을 오가는 고객들이 많다는 상황을 설정하였습니다.

다양한 접근방법

FIFO

가장 쉬운 접근법입니다. 요청이 들어온 순서대로 태우고 목적지에 내려준 후 다음 요청을 처리하는 형태입니다. 어피치 맨션의 경우 이 접근으로도 쉽게 풀립니다만, 제이지 빌딩, 라이언 타워의 경우 각각 약 4000, 13000 timestamp로 좋은 점수를 받을 수 없습니다.

Collective control

위에서 설명한 collective control 알고리즘입니다. 가장 친숙한 동작 방식입니다. 1대만 사용했음에도 불구하고 제이지 빌딩에서 972의 timestamp를 기록할 정도로 효율적입니다. 라이언 타워의 경우 약 2000 timestamp를 기록할 수 있습니다.

다양한 전략들

이번 문제의 엘리베이터는 보통의 엘리베이터와 다른 점이 있습니다. 이 부분을 활용하면 고득점을 할 수 있는데요. 출제진도 예상하지 못한 다양한 접근 방법들이 나와 놀랐습니다. 어떤 것들이 있는지 살펴보겠습니다.

0번 엘리베이터를 주목해주세요. 3명의 승객을 태우고 올라가던 엘리베이터는 17층에서 승객 1명을 내려주고 내려가는 방향의 승객 2명을 태워 올라갑니다. 일반적인 알고리즘과는 다른 방식인데요. 힌트는 평가 방법에 있습니다. 평가 조건은 모든 승객을 목적 층으로 수송해야 하며 가장 마지막 승객이 목적 층에 하차하였을 때의 시간 기준으로 평가를 합니다. 따라서 엘리베이터 내에 공간이 충분하다면 문이 열린 김에 태워가는 것이, 방향 전환 후 다시 멈추고, 문을 열고, 탑승시키는 것보다 효율적입니다.

마찬가지로 승객의 요청이 들어왔을 때 바로 요청을 처리하지 않고 대기하는 지원자도 있었습니다. 승객을 태우기 위해 멈추고, 문을 열고, 닫고, 태우는 것이 모두 timestamp를 잡아먹기 때문에 충분히 기다렸다가 한꺼번에 태우는 것입니다. 또한 대기 중인 승객의 수에 따라 엘리베이터 이동 전략을 달리한 지원자도 있었습니다.

그리고 결정적으로 현실의 엘리베이터와 차이가 나는 부분이 있습니다. 바로 요청을 받을 때 목적 층을 사전에 알 수 있다는 것입니다. 이 정보를 토대로 엘리베이터에 승객을 가고자 하는 층별로 그룹화하여 탑승시킬 수 있습니다. 심지어 엘리베이터를 움직이기 전에 모든 승객의 요청을 다 수집한 후에 움직이기 시작한 지원자도 있었습니다.

통계

언어별 통계

Python이 압도적으로 높은 비율을 보였고 그 뒤를 Java와 Node가 뒤이었습니다.

시간대별 누적 성공 응시자 통계

빌딩별 가장 먼저 성공한 시각은 14시 12분 / 14시 40분 / 14시 53분입니다. 어피치 맨션을 2시간 30분 이내에 풀어야 남은 두 빌딩을 최적화하여 고득점 할 수 있을 것이라 예상하였는데, 예상외로 후반부의 집중력이 놀라웠습니다.

빌딩별 시도/성공 비율

기타

2차 오프라인 코딩테스트에서 사용한 엘리베이터 시뮬레이션 서버는 직접 돌려볼 수 있도록 수정하여 공개하였습니다. 이 곳에서 내려받아 실행할 수 있습니다.

마치며

긴 시간 동안 문제 푸시느라 고생하셨습니다! 당락을 떠나 즐겁고 유익한 문제였기를 바랍니다

만든 사람들

김동주 jude.traveller@kakaocorp(dot)com
송신형 lucid.s@kakaocorp(dot)com
안건 kyen.a@kakaocorp(dot)com
유승원 cree.yoo@kakaocorp(dot)com
이진환 root.lee@kakaocorp(dot)com
하광성 jesse.ha@kakaocorp(dot)com

문의

하광성 jesse.ha@kakaocorp(dot)com

if kakao 2018 동영상을 공개합니다.

Wed, 17 Oct 2018 17:00:00 +0900

지난 9월 4일, 코엑스 그랜드볼룸에서 카카오의 개발자 콘퍼런스인 if kakao 2018이 성황리에 마쳤습니다.

카카오 이름을 건 첫 번째 개발자 콘퍼런스인 if kakao 2018은 인공지능, 메신저, 택시, 결제/송금, 검색 등 수많은 영역에서 쌓은 카카오의 기술과 노하우를 외부에 공유하고 소통하는 자리였구요.

신정환 CTO와 김병학 AI Lab 총괄 부사장의 기조연설과 인공지능, 머신러닝, 멀티미디어 처리, 챗봇, 클라우드, 오픈소스, 추천 등 다양한 주제의 27개 강연 세션을 진행했으며, 카카오의 서비스를 만드는 현직 개발자들이 실제 개발 사례를 중심으로 기술과 노하우를 생생하게 전달하려고 노력했습니다.

이번 행사의 스케치 영상을 포함해 기조연설과 모든 강연 세션 동영상을 공개합니다.

행사 스케치 영상

카카오TV ▶︎

if kakao 2018 콘퍼런스의 모든 영상은 카카오TV의 if kakao dev 2018 채널에서 확인할 수 있습니다. 아쉽게도 행사에 참석하지 못한 분들 뿐만 아니라, 행사에 참석했던 분들에게도 세션 내용을 다시 확인하는데 도움이 되었으면 합니다.

내년에는 더욱 멋진 콘퍼런스를 준비해서 찾아뵙겠습니다. 감사합니다.

2019 카카오 신입 공채 1차 코딩 테스트 문제 해설

Fri, 21 Sep 2018 11:00:00 +0900

작년에 이어 올해도 블라인드 전형으로 카카오 개발 신입 공채가 시작되었습니다!

그 첫 번째 관문으로 1차 온라인 코딩 테스트가 지난 9월 15일(토) 오후 2시부터 7시까지 5시간 동안 치러졌는데요.

지원자분들 만큼이나 준비위원들도 테스트가 문제없이, 공정하게 치러질 수 있도록 많은 준비를 했고 두근 거리는 마음으로 끝까지 온라인 테스트를 모니터링했답니다.

문제는 작년과 비슷하게 구현 문제 위주로 쉬운 난이도에서 어려운 난이도 순으로 풀 수 있도록 차례대로 배치했고, 모든 테스트 케이스가 통과해야 문제를 풀이한 것으로 인정되도록 했습니다. 단, 작년과는 다르게 효율성 테스트를 도입하여 같은 문제라도 입력의 크기에 따라 효율적인 풀이를 구현하도록 유도했고, 효율성 테스트가 있는 문제에서는 부분점수가 부여되도록 설계했습니다.

그럼, 지금부터 문제 설명과 풀이를 살펴보도록 하겠습니다.

문제 설명

1. 오픈채팅방

정답률: 59.91%
문제 풀러 가기

카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.

신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다.

“[닉네임]님이 들어왔습니다.”

채팅방에서 누군가 나가면 다음 메시지가 출력된다.

“[닉네임]님이 나갔습니다.”

채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.

채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.
채팅방에서 닉네임을 변경한다.

닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.

예를 들어, 채팅방에 “Muzi”와 “Prodo”라는 닉네임을 사용하는 사람이 순서대로 들어오면 채팅방에는 다음과 같이 메시지가 출력된다.

“Muzi님이 들어왔습니다.” “Prodo님이 들어왔습니다.”

채팅방에 있던 사람이 나가면 채팅방에는 다음과 같이 메시지가 남는다.

“Muzi님이 들어왔습니다.” “Prodo님이 들어왔습니다.” “Muzi님이 나갔습니다.”

Muzi가 나간후 다시 들어올 때, Prodo 라는 닉네임으로 들어올 경우 기존에 채팅방에 남아있던 Muzi도 Prodo로 다음과 같이 변경된다.

“Prodo님이 들어왔습니다.” “Prodo님이 들어왔습니다.” “Prodo님이 나갔습니다.” “Prodo님이 들어왔습니다.”

채팅방은 중복 닉네임을 허용하기 때문에, 현재 채팅방에는 Prodo라는 닉네임을 사용하는 사람이 두 명이 있다. 이제, 채팅방에 두 번째로 들어왔던 Prodo가 Ryan으로 닉네임을 변경하면 채팅방 메시지는 다음과 같이 변경된다.

“Prodo님이 들어왔습니다.” “Ryan님이 들어왔습니다.” “Prodo님이 나갔습니다.” “Prodo님이 들어왔습니다.”

채팅방에 들어오고 나가거나, 닉네임을 변경한 기록이 담긴 문자열 배열 record가 매개변수로 주어질 때, 모든 기록이 처리된 후, 최종적으로 방을 개설한 사람이 보게 되는 메시지를 문자열 배열 형태로 return 하도록 solution 함수를 완성하라.

제한사항

record는 다음과 같은 문자열이 담긴 배열이며, 길이는 1 이상 100,000 이하이다.
다음은 record에 담긴 문자열에 대한 설명이다.
- 모든 유저는 [유저 아이디]로 구분한다.
- [유저 아이디] 사용자가 [닉네임]으로 채팅방에 입장 - “Enter [유저 아이디] [닉네임]” (ex. “Enter uid1234 Muzi”)
- [유저 아이디] 사용자가 채팅방에서 퇴장 - “Leave [유저 아이디]” (ex. “Leave uid1234”)
- [유저 아이디] 사용자가 닉네임을 [닉네임]으로 변경 - “Change [유저 아이디] [닉네임]” (ex. “Change uid1234 Muzi”)
- 첫 단어는 Enter, Leave, Change 중 하나이다.
- 각 단어는 공백으로 구분되어 있으며, 알파벳 대문자, 소문자, 숫자로만 이루어져있다.
- 유저 아이디와 닉네임은 알파벳 대문자, 소문자를 구별한다.
- 유저 아이디와 닉네임의 길이는 1 이상 10 이하이다.
- 채팅방에서 나간 유저가 닉네임을 변경하는 등 잘못 된 입력은 주어지지 않는다.

입출력 예

record	result
[“Enter uid1234 Muzi”, “Enter uid4567 Prodo”,”Leave uid1234”,”Enter uid1234 Prodo”,”Change uid4567 Ryan”]	[“Prodo님이 들어왔습니다.”, “Ryan님이 들어왔습니다.”, “Prodo님이 나갔습니다.”, “Prodo님이 들어왔습니다.”]

입출력 예 설명

입출력 예 #1 문제의 설명과 같다.

문제 풀이

첫 번째 문제답게 큰 고민 없이 연관 배열(맵)을 이용해서 쉽게 풀 수 있습니다.

record 를 순회 하면서

Enter, Leave 인 경우 유저 아이디와 함께 정답에 출력될 메시지의 종류를 기록을 해둡니다. 이렇게 기록해둔 것을 events 라고 합시다.

Enter, Change 인 경우 연관 배열을 이용하여 각 유저 아이디를 키로, 닉네임을 값으로 저장해 둡니다. 이렇게 해서 최종 닉네임을 유저 아이디별로 유지합니다.

이제 events 를 순회하면서 채팅방에 출력할 메시지를 생성할 때, 연관 배열에 저장된 아이디별 최종 닉네임을 이용하면 됩니다.

2. 실패율

정답률: 55.57%
문제 풀러 가기

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

실패율은 다음과 같이 정의한다.
- 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

제한사항

스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
stages의 길이는 1 이상 200,000 이하이다.
stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
- 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
- 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

입출력 예

N	stages	result
5	[2, 1, 2, 6, 2, 4, 3, 3]	[3,4,2,1,5]
4	[4,4,4,4,4]	[4,1,2,3]

입출력 예 설명

입출력 예 #1

1번 스테이지에는 총 8명의 사용자가 도전했으며, 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 1번 스테이지의 실패율은 다음과 같다.

1번 스테이지 실패율 : 1/8

2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 2번 스테이지의 실패율은 다음과 같다.

2번 스테이지 실패율 : 3/7

마찬가지로 나머지 스테이지의 실패율은 다음과 같다.

3번 스테이지 실패율 : 2/4
4번 스테이지 실패율 : 1/2
5번 스테이지 실패율 : 0/1

각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.

[3,4,2,1,5]

입출력 예 #2

모든 사용자가 마지막 스테이지에 있으므로 4번 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0이다.

[4,1,2,3]

문제 풀이

문제를 읽어보면 알 수 있듯이 이 문제는 정렬을 이용해서 풀 수 있습니다.

먼저 주어진 배열의 길이를 이용하여 전체 사용자 수를 구하고, stages 를 순회하며 각 스테이지에 몇 명의 사용자가 도달했는지 세줍니다. 이렇게 만들어둔 배열(각 스테이지별 사용자 수가 들어있는)을 순회하면서 stages 를 참고하여 스테이지별 실패율을 계산합니다. 이때, 스테이지에 도달한 사용자가 0명인 경우 예외 처리를 해야 합니다. 스테이지별 실패율을 구했다면, 각 스테이지 번호와 묶어서 실패율 내림차순으로 정렬합니다. 실패율이 같은 경우는 스테이지 번호가 작은 것을 먼저 오도록 정렬하면 됩니다.

3. 후보키

정답률: 16.09%
문제 풀러 가기

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
- 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
- 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 “학번”을 가지고 있다. 따라서 “학번”은 릴레이션의 후보 키가 될 수 있다. 그다음 “이름”에 대해서는 같은 이름(“apeach”)을 사용하는 학생이 있기 때문에, “이름”은 후보 키가 될 수 없다. 그러나, 만약 [“이름”, “전공”]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다. 물론 [“이름”, “전공”, “학년”]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다. 따라서, 위의 학생 인적사항의 후보키는 “학번”, [“이름”, “전공”] 두 개가 된다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

제한사항

relation은 2차원 문자열 배열이다.
relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

입출력 예

relation	result
[[“100”,”ryan”,”music”,”2”],[“200”,”apeach”,”math”,”2”],[“300”,”tube”,”computer”,”3”],[“400”,”con”,”computer”,”4”],[“500”,”muzi”,”music”,”3”],[“600”,”apeach”,”music”,”2”]]	2

입출력 예 설명

입출력 예 #1 문제에 주어진 릴레이션과 같으며, 후보 키는 2개이다.

문제 풀이

가능한 모든 어트리뷰트의 조합을 만들고, 이 조합에서 조건을 만족시키는 조합만 추려야 하는 문제입니다.

dfs 또는 bit 를 이용한 집합 표현을 이용하여 어트리뷰트의 모든 부분 집합을 만들어냅니다.
만들어지는 각 부분 집합을 이용해서 중복 튜플이 있는지 검사합니다. 만약 중복 튜플이 없다면, 이 부분 집합을 슈퍼 키 집합(유일성을 만족하는 키들의 집합)에 포함시킵니다.

슈퍼 키 집합을 구한 후, 여기서 최소성을 만족하는 키들을 선택하여 후보 키 집합을 만들 수 있습니다.
만약 어떤 슈퍼 키 X에 대해 X의 부분집합인 슈퍼 키 Y가 없다면 (X ⊃ Y인 슈퍼 키 Y가 없다면) X는 후보 키로 선택될 수 있습니다.

예를 들어 어떤 릴레이션의 어트리뷰트가 ABCDE 이고, 슈퍼 키 집합이 {A, AB, BC, BCE, BDE, …} 라고 해봅시다.

A 는 후보 키로 선택될 수 있습니다.

AB 는 AB ⊃ A 이므로 후보 키가 될 수 없습니다.

BC 는 부분집합이 되는 다른 슈퍼 키가 없으므로 후보 키로 선택됩니다.

BCE 는 BCE ⊃ BC 이므로 후보 키가 될 수 없습니다.

BDE 는 부분집합이 되는 다른 슈퍼 키가 없으므로 후보 키로 선택됩니다.

…

따라서 이 경우 후보 키 집합은 {A, BC, BDE, …} 가 됩니다.

가능한 모든 조합을 만드는 부분 때문인지 앞쪽에 배치된 문제임에도 많은 지원자들이 어려움을 겪은 것으로 보입니다.

4. 무지의 먹방 라이브

정답률: 정확성 42.08% / 효율성 5.52%
문제 풀러 가기

* 효율성 테스트에 부분 점수가 있는 문제입니다.

평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.

그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.

회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다.

무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
- 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다. 무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다. 각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.

제한사항

food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
k 는 방송이 중단된 시간을 나타낸다.
만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

정확성 테스트 제한 사항

food_times 의 길이는 1 이상 2,000 이하이다.
food_times 의 원소는 1 이상 1,000 이하의 자연수이다.
k는 1 이상 2,000,000 이하의 자연수이다.

효율성 테스트 제한 사항

food_times 의 길이는 1 이상 200,000 이하이다.
food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
k는 1 이상 2 x 10^13 이하의 자연수이다.

입출력 예

food_times	k	result
[3, 1, 2]	5	1

입출력 예 설명

입출력 예 #1

0~1초 동안에 1번 음식을 섭취한다. 남은 시간은 [2,1,2] 이다.
1~2초 동안 2번 음식을 섭취한다. 남은 시간은 [2,0,2] 이다.
2~3초 동안 3번 음식을 섭취한다. 남은 시간은 [2,0,1] 이다.
3~4초 동안 1번 음식을 섭취한다. 남은 시간은 [1,0,1] 이다.
4~5초 동안 (2번 음식은 다 먹었으므로) 3번 음식을 섭취한다. 남은 시간은 [1,0,0] 이다.
5초에서 네트워크 장애가 발생했다. 1번 음식을 섭취해야 할 때 중단되었으므로, 장애 복구 후에 1번 음식부터 다시 먹기 시작하면 된다.

문제 풀이

이 문제를 완전히 해결하려면 효율성 테스트를 통과해야 합니다.
효율성 테스트의 제한 사항은 정확성 테스트보다 까다롭기 때문에 정확성 테스트를 통과한 풀이를 그대로 적용하면 시간 초과가 발생합니다. 따라서, 실행 시간을 줄일 수 있는 아이디어가 필요합니다.

정확성 풀이

시간이 1초 지날 때마다 다음 먹을 음식을 반복문을 이용해 하나하나 찾아가며 시뮬레이션하면 됩니다.

효율성 풀이

먼저 음식별 필요 시간을 오름차순으로 정렬합니다. 시간의 오름차순으로 정렬해두면 음식을 먹는 데 소요되는 시간을 한꺼번에 지울 수 있습니다. 예를 들어 정렬한 시간이 T = [1, 3, 3, 4, 5]라면 처음에 T[0] * 5 = 5만큼의 시간을 한꺼번에 지울 수 있습니다. 다음으로 T[1]부터 남은 시간을 한꺼번에 제거합니다. 즉, (T[1] - T[0]) * 4 = 8 만큼의 시간을 한꺼번에 지웁니다. 마찬가지로 (T[2] - T[1]) * 3 = 0 만큼의 시간을 한꺼번에 지울 수 있습니다.

위와 같은 방법으로 시간을 지워가다가, 지운 시간의 합이 K 보다 커지게 되면 남은 시간의 개수로 나눈 나머지를 이용해 K 초 후 다시 먹기 시작해야 될 음식의 번호를 바로 구할 수 있습니다. 이때, 남은 시간을 다시 원래 음식의 번호 순서대로 재정렬해야 합니다.

꼭 이 방법이 아니라도 K에 도달하는 시점을 빠르게 구할 수만 있으면 실행 시간을 줄일 수 있습니다.

5. 길 찾기 게임

정답률: 7.40%
문제 풀러 가기

전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다.

라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다.

그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다.

라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.

트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
모든 노드는 서로 다른 x값을 가진다.
같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
자식 노드의 y 값은 항상 부모 노드보다 작다.
임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

아래 예시를 확인해보자.

라이언의 규칙에 맞게 이진트리의 노드만 좌표 평면에 그리면 다음과 같다. (이진트리의 각 노드에는 1부터 N까지 순서대로 번호가 붙어있다.)

이제, 노드를 잇는 간선(edge)을 모두 그리면 아래와 같은 모양이 된다.

위 이진트리에서 전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.

전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7

다행히 두 팀 모두 머리를 모아 분석한 끝에 라이언의 의도를 간신히 알아차렸다.
그러나 여전히 문제는 남아있다. 노드의 수가 예시처럼 적다면 쉽게 해결할 수 있겠지만, 예상대로 라이언은 그렇게 할 생각이 전혀 없었다.

이제 당신이 나설 때가 되었다.

곤경에 빠진 카카오 프렌즈를 위해 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때, 노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.

제한사항

nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.
- nodeinfo의 길이는 1 이상 10,000 이하이다.
- nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
- 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
- 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
- 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.

입출력 예

nodeinfo	result
[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]]	[[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]

입출력 예 설명

입출력 예 #1

문제에 주어진 예시와 같다.

문제 풀이

트리를 순회하는 방법은 검색을 통해 쉽게 알 수 있으므로 문제가 되지 않습니다. 이 문제의 핵심은 좌표 값으로 주어지는 노드들을 트리로 구성하는 부분입니다.

트리를 만들기 위해 y 값을 이용해서 각 노드의 level 을 분리하고, 현재 노드의 자식 노드가 가질 수 있는 x값을 이용하여 현재 노드의 왼쪽, 오른쪽 자식을 정확히 찾는 것이 중요합니다.

각 노드의 왼쪽, 오른쪽 자식 노드는 다음과 같이 찾을 수 있습니다.

먼저 현재 노드 P의 x값을 Px, 현재 노드의 자식 노드가 가질 수 있는 x 범위를 Lx, Rx (Lx < Px < Rx)라고 하겠습니다. 또 어떤 노드 K의 x값을 Kx 라고 하겠습니다. 만약 현재 노드의 바로 다음 레벨에 Lx ≤ Kx < Px를 만족하는 노드 K가 있다면 K는 노드 P의 왼쪽 자식이 됩니다. 이때, 노드 K의 자식 노드가 가질 수 있는 x값의 범위는 Lx ≤ x ≤ Px - 1 (x ≠ Kx)가 됩니다.

마찬가지로 현재 노드의 바로 다음 레벨에 Px < Kx ≤ Rx를 만족하는 노드 K가 있다면 K는 노드 P의 오른쪽 자식이 되며, 노드 K의 자식 노드가 가질 수 있는 x의 범위는 Px + 1 ≤ x ≤ Rx (x ≠ Kx)가 됩니다.

위 과정을 재귀적으로 반복하면서 각 노드의 왼쪽, 오른쪽 자식을 찾아주면 트리를 구성할 수 있습니다.

노드별 왼쪽, 오른쪽 자식을 찾는 방법은 여러 가지가 있을 수 있습니다. 그중 하나로, 재귀적으로 순회하며 트리를 만들면 같은 level의 노드는 x값이 작은 노드부터 방문하게 되므로, 큐를 트리의 레벨만큼 만들어 두고, x축 기준으로 오름차순 정렬된 노드들을 y축 값이 같은 노드끼리 각 큐에 넣어두면 큐의 front를 확인하는 방법으로 O(1)에 찾을 수 있습니다.

이렇게 하면 노드의 수가 N일 때, 트리를 구성하는 데는 O(N) 시간이 소요되며, 시간 복잡도는 전체 노드를 정렬하는데 걸리는 시간인 O(NlogN)이 됩니다.

6. 매칭 점수

정답률: 6.12%
문제 풀러 가기

프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다. 그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.

한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.

예를 들어, 다음과 같이 A, B, C 세 개의 웹페이지가 있고, 검색어가 hi라고 하자.

이때 A 웹페이지의 매칭점수는 다음과 같이 계산할 수 있다.

기본 점수는 각 웹페이지에서 hi가 등장한 횟수이다.
- A,B,C 웹페이지의 기본점수는 각각 1점, 4점, 9점이다.
외부 링크수는 다른 웹페이지로 링크가 걸린 개수이다.
- A,B,C 웹페이지의 외부 링크 수는 각각 1점, 2점, 3점이다.
A 웹페이지로 링크가 걸린 페이지는 B와 C가 있다.
- A 웹페이지의 링크점수는 B의 링크점수 2점(4 ÷ 2)과 C의 링크점수 3점(9 ÷ 3)을 더한 5점이 된다.
그러므로, A 웹페이지의 매칭점수는 기본점수 1점 + 링크점수 5점 = 6점이 된다.

검색어 word와 웹페이지의 HTML 목록인 pages가 주어졌을 때, 매칭점수가 가장 높은 웹페이지의 index를 구하라. 만약 그런 웹페이지가 여러 개라면 그중 번호가 가장 작은 것을 구하라.

제한사항

pages는 HTML 형식의 웹페이지가 문자열 형태로 들어있는 배열이고, 길이는 1 이상 20 이하이다.
한 웹페이지 문자열의 길이는 1 이상 1,500 이하이다.
웹페이지의 index는 pages 배열의 index와 같으며 0부터 시작한다.
한 웹페이지의 url은 HTML의 <head> 태그 내에 <meta> 태그의 값으로 주어진다.
- 예를들어, 아래와 같은 meta tag가 있으면 이 웹페이지의 url은 https://careers.kakao.com/index 이다.
- <meta property=”og:url” content=”https://careers.kakao.com/index” />
한 웹페이지에서 모든 외부 링크는 <a href=”https://careers.kakao.com/index”>의 형태를 가진다.
- <a> 내에 다른 attribute가 주어지는 경우는 없으며 항상 href로 연결할 사이트의 url만 포함된다.
- 위의 경우에서 해당 웹페이지는 https://careers.kakao.com/index 로 외부링크를 가지고 있다고 볼 수 있다.
모든 url은 https:// 로만 시작한다.
검색어 word는 하나의 영어 단어로만 주어지며 알파벳 소문자와 대문자로만 이루어져 있다.
word의 길이는 1 이상 12 이하이다.
검색어를 찾을 때, 대소문자 구분은 무시하고 찾는다.
- 예를들어 검색어가 blind일 때, HTML 내에 Blind라는 단어가 있거나, BLIND라는 단어가 있으면 두 경우 모두 해당된다.
검색어는 단어 단위로 비교하며, 단어와 완전히 일치하는 경우에만 기본 점수에 반영한다.
- 단어는 알파벳을 제외한 다른 모든 문자로 구분한다.
- 예를들어 검색어가 “aba” 일 때, “abab abababa”는 단어 단위로 일치하는게 없으니, 기본 점수는 0점이 된다.
- 만약 검색어가 “aba” 라면, “aba@aba aba”는 단어 단위로 세개가 일치하므로, 기본 점수는 3점이다.
결과를 돌려줄때, 동일한 매칭점수를 가진 웹페이지가 여러 개라면 그중 index 번호가 가장 작은 것를 리턴한다
- 즉, 웹페이지가 세개이고, 각각 매칭점수가 3,1,3 이라면 제일 적은 index 번호인 0을 리턴하면 된다.

입출력 예 #1

word : blind

pages :

["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://a.com\"/>\n</head>  \n<body>\nBlind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. \n<a href=\"https://b.com\"> Link to b </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://b.com\"/>\n</head>  \n<body>\nSuspendisse potenti. Vivamus venenatis tellus non turpis bibendum, \n<a href=\"https://a.com\"> Link to a </a>\nblind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.\n<a href=\"https://c.com\"> Link to c </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://c.com\"/>\n</head>  \n<body>\nUt condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind\n<a href=\"https://a.com\"> Link to a </a>\n</body>\n</html>"]

pages는 다음과 같이 3개의 웹페이지에 해당하는 HTML 문자열이 순서대로 들어있다.

<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://a.com"/>
</head>  
<body>
Blind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. 
<a href="https://b.com"> Link to b </a>
</body>
</html>

<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://b.com"/>
</head>  
<body>
Suspendisse potenti. Vivamus venenatis tellus non turpis bibendum, 
<a href="https://a.com"> Link to a </a>
blind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.
<a href="https://c.com"> Link to c </a>
</body>
</html>

<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://c.com"/>
</head>  
<body>
Ut condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind
<a href="https://a.com"> Link to a </a>
</body>
</html>

위의 예를 가지고 각각의 점수를 계산해보자.

기본점수 및 외부 링크수는 아래와 같다.
- a.com의 기본점수는 3, 외부 링크 수는 1개
- b.com의 기본점수는 1, 외부 링크 수는 2개
- c.com의 기본점수는 1, 외부 링크 수는 1개
링크점수는 아래와 같다.
- a.com의 링크점수는 b.com으로부터 0.5점, c.com으로부터 1점
- b.com의 링크점수는 a.com으로부터 3점
- c.com의 링크점수는 b.com으로부터 0.5점
각 웹 페이지의 매칭 점수는 다음과 같다.
- a.com : 4.5 점
- b.com : 4 점
- c.com : 1.5 점

따라서 매칭점수가 제일 높은 첫번째 웹 페이지의 index인 0을 리턴 하면 된다.

입출력 예 #2

word : Muzi

pages :

["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://careers.kakao.com/interview/list\"/>\n</head>  \n<body>\n<a href=\"https://programmers.co.kr/learn/courses/4673\"></a>#!MuziMuzi!)jayg07con&&\n\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://www.kakaocorp.com\"/>\n</head>  \n<body>\ncon%\tmuzI92apeach&2<a href=\"https://hashcode.co.kr/tos\"></a>\n\n\t^\n</body>\n</html>"]

pages는 다음과 같이 2개의 웹페이지에 해당하는 HTML 문자열이 순서대로 들어있다.

<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://careers.kakao.com/interview/list"/>
</head>  
<body>
<a href="https://programmers.co.kr/learn/courses/4673"></a>#!MuziMuzi!)jayg07con&&

</body>
</html>

<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://www.kakaocorp.com"/>
</head>  
<body>
con%	muzI92apeach&2<a href="https://hashcode.co.kr/tos"></a>

	^
</body>
</html>

기본점수 및 외부 링크수는 아래와 같다.
- careers.kakao.com/interview/list 의 기본점수는 0, 외부 링크 수는 1개
- www.kakaocorp.com 의 기본점수는 1, 외부 링크 수는 1개
링크점수는 아래와 같다.
- careers.kakao.com/interview/list 의 링크점수는 0점
- www.kakaocorp.com 의 링크점수는 0점
각 웹 페이지의 매칭 점수는 다음과 같다.
- careers.kakao.com/interview/list : 0점
- www.kakaocorp.com : 1 점

따라서 매칭점수가 제일 높은 두번째 웹 페이지의 index인 1을 리턴 하면 된다.

문제 풀이

점수를 계산하는 로직 자체는 복잡하지 않지만, 점수 계산에 필요한 요소들을 잘 추출해야 하는 문제입니다.

정규표현식을 이용하거나 문자열 처리 로직을 구현해서 a 태그와 meta 태그를 찾아 현재 페이지의 URL 과 외부 링크의 URL 을 찾습니다. 또한, 전체 HTML 문서를 대상으로 검색어가 몇 번 등장하는지 찾습니다. 이때, 제시된 조건에 맞게 단어를 찾을 수 있도록 적절히 split 하여 비교합니다. 각 HTML 문서별 기본 점수, 외부 링크 수를 구하고, 해당 웹페이지로 링크가 걸린 다른 웹페이지들을 찾아 링크 점수를 계산합니다.

마지막으로 각 페이지의 매칭 점수를 구하고, 최댓값을 갖는 문서의 인덱스를 구하면 됩니다.

7. 블록 게임

정답률: 5.85%
문제 풀러 가기

프렌즈 블록이라는 신규 게임이 출시되었고, 어마어마한 상금이 걸린 이벤트 대회가 개최 되었다.

이 대회는 사람을 대신해서 플레이할 프로그램으로 참가해도 된다는 규정이 있어서, 게임 실력이 형편없는 프로도는 프로그램을 만들어서 참가하기로 결심하고 개발을 시작하였다.

프로도가 우승할 수 있도록 도와서 빠르고 정확한 프로그램을 작성해 보자.

게임규칙

아래 그림과 같이 1×1 크기의 블록을 이어 붙여 만든 3 종류의 블록을 회전해서 총 12가지 모양의 블록을 만들 수 있다.

1 x 1 크기의 정사각형으로 이루어진 N x N 크기의 보드 위에 이 블록들이 배치된 채로 게임이 시작된다. (보드 위에 놓인 블록은 회전할 수 없다). 모든 블록은 블록을 구성하는 사각형들이 정확히 보드 위의 사각형에 맞도록 놓여있으며, 선 위에 걸치거나 보드를 벗어나게 놓여있는 경우는 없다.

플레이어는 위쪽에서 1 x 1 크기의 검은 블록을 떨어뜨려 쌓을 수 있다. 검은 블록은 항상 맵의 한 칸에 꽉 차게 떨어뜨려야 하며, 줄에 걸치면 안된다. 이때, 검은 블록과 기존에 놓인 블록을 합해 속이 꽉 채워진 직사각형을 만들 수 있다면 그 블록을 없앨 수 있다.

예를 들어 검은 블록을 떨어뜨려 아래와 같이 만들 경우 주황색 블록을 없앨 수 있다.

빨간 블록을 가로막던 주황색 블록이 없어졌으므로 다음과 같이 빨간 블록도 없앨 수 있다.

그러나 다른 블록들은 검은 블록을 떨어뜨려 직사각형으로 만들 수 없기 때문에 없앨 수 없다.

따라서 위 예시에서 없앨 수 있는 블록은 최대 2개이다.

보드 위에 놓인 블록의 상태가 담긴 2차원 배열 board가 주어질 때, 검은 블록을 떨어뜨려 없앨 수 있는 블록 개수의 최댓값을 구하라.

제한사항

board는 블록의 상태가 들어있는 N x N 크기 2차원 배열이다.
- N은 4 이상 50 이하다.
board의 각 행의 원소는 0 이상 200 이하의 자연수이다.
- 0 은 빈 칸을 나타낸다.
- board에 놓여있는 각 블록은 숫자를 이용해 표현한다.
- 잘못된 블록 모양이 주어지는 경우는 없다.
- 모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현됩니다.
- 예를 들어 문제에 주어진 예시의 경우 다음과 같이 주어진다.

입출력 예

board	result
[[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]]	2

입출력 예 설명

입출력 예 #1 문제에 주어진 예시와 같음

문제 풀이

문제를 이해하는 것은 어렵지 않지만 제거해야 할 블록을 찾기 위한 아이디어가 필요합니다.

문제에서는 검은 블록을 떨어뜨린다고 되어있으나, 실제로 검은 블록을 떨어뜨리지 않고 순서대로 검은 블록으로 채워 나가기만 해도 삭제될 블록을 찾을 수 있습니다. 먼저 게임 보드의 왼쪽 위(혹은 오른쪽 위)부터 가로 방향으로 한 줄씩 순서대로 진행하면서 빈칸에 검은 블록을 채울 수 있는지 확인합니다. 현재 칸이 빈칸이라면 위쪽으로 삭제되지 않은 블록이 있는지 확인합니다. 만약 다른 블록이 없다면 검은 블록으로 채우고, 그렇지 않으면 그대로 빈칸으로 둡니다.

칸 하나를 확인한 후에는 해당 칸을 포함하는 칸 중에서 삭제할 수 있는 블록이 있는지 확인합니다. 블록이 사라질 수 있는지 판단은 검은 블록 두 개와 같은 색 블록 4개가 2x3, 3x2의 직사각형 안에 들어있는지 확인하면 됩니다.

블록을 지운 경우에 지워진 칸을 그대로 둘지, 혹은 검은 블록으로 채울지 확인하는 과정이 필요합니다. 블록이 삭제된 칸이어도 검은 블록으로 채울 수 없는 경우가 있기 때문입니다. 지워진 칸을 기준으로 위쪽에 삭제되지 않은 블록이 있는지 확인하여 검은 블록을 적절히 채웁니다(삭제되는 블록을 찾는 방향에 따라 조금 다를 수도 있습니다).

블록이 삭제되면 카운트를 1 증가시키고, 게임 보드의 모든 칸에 대해 삭제될 블록을 찾은 후 카운트된 값을 반환하면 됩니다.

또 다른 방법으로, 문제의 설명대로 위에서 블록을 떨어뜨려서 없앨 수 있는 블록을 차례대로 찾아서 제거하는 것을 생각해 볼 수 있습니다.

도형의 모양을 자세히 보면, 제거할 수 있는 도형은 채워야 할 공간이 위쪽으로 열려있는 5가지뿐임을 알 수 있습니다. 최상단 좌측부터 검사를 시작해 도형이 있는 칸(0보다 큰 값)을 만나면, 주변 값들을 확인해서 제거 가능한 도형 중 하나인지를 체크합니다. 만약, 제거 가능한 도형 중 하나라면 도형에서 채워야 하는 공간부터 최상단까지 모든 값이 비어있는지를 체크합니다. 모두 비어있다면 이는 없앨 수 있다는 뜻이므로 이 도형을 0으로 채워 제거합니다.

제거 가능한 도형을 모두 찾을 때까지 이 과정을 반복하고, 도형을 제거할 때마다 카운트를 증가시켜주면 됩니다.

마무리하며

지금까지 1차 코딩 테스트 문제와 풀이에 대해 살펴봤습니다.

아마 문제를 풀어본 분이라면 고개가 끄덕여지는 부분도 있을 것이고, 자신의 풀이와 차이점도 확인할 수 있었을 것 같네요. 모쪼록 이 글이 도움이 되었으면 좋겠습니다.

마지막으로, 5시간 동안 테스트에 응해주신 지원자분들께 감사드립니다. 모두 고생 많으셨고 2차 오프라인 테스트에서 만날 수 있길 바라봅니다. : )

코드 페스티벌 2018 본선 이야기

Wed, 12 Sep 2018 17:00:00 +0900

2018 코드 페스티벌, 뜨거운 열기와 함께 본선 시작!

지난 8월 25일 토요일, 카카오 코드 페스티벌 오프라인 본선이 진행됐습니다. 예선에서의 엄청난 경쟁률을 뚫고 당당히 본선에 진출한 64명의 실력자들이 함께 했는데요. 작년과는 다르게 카카오 판교 오피스에서 행사를 개최하여 더 뜻깊은 자리가 되었던 것 같습니다.

▶ 행사 후기가 궁금하시다면?

그럼 본선에 출제되었던 문제와 해법을 알아보도록 하겠습니다.

문제 설명 및 풀이

승부 예측

제출자 62명
정답자 62명
문제 풀러 가기

서로 다른 결과의 경우의 수가 총 3⁶ 가지임을 알 수 있습니다. 그러므로 모든 경우를 고려하는 완전 탐색 풀이를 구현하면 됩니다. 특정 경우에서 동점자가 발생하는 경우가 존재하기 때문에, 동점자가 발생하는 모든 경우를 유의할 필요가 있습니다.

카카오머니

제출자 64명
정답자 59명
문제 풀러 가기

모순이 없다고 가정하고, M 을 구해 봅시다. 편의상 b₀ = 0 으로 둔다면, i (1 ≤ i ≤ n)번째 로그에서 카카오머니 잔고의 변화량은 b_i - b_i-1 입니다.

만약 b_i - b_i-1 = a_i라면, i 번째 로그가 입금인지 출금인지의 여부와 관계없이, 카카오머니 잔고가 a_i 만큼 변하여 제대로 기록된 것입니다.

하지만, 만약 b_i - b_i-1 ≠ a_i 라면, 카카오머니 잔고가 부족하여 통장에서 돈을 가져왔을 것입니다. (이 외의 방법이 없습니다.)

통장에서 가져온 금액은 b_i - (b_i-1 + a_i) 원입니다. 문제의 지문에서, 통장에서 돈을 가져올 때에는 M 원씩을 여러 번 가져오므로, b_i - (b_i-1 + a_i) 이 M 의 배수여야 한다는 조건을 얻을 수 있습니다. 또한, 최종 잔고는 M 원 미만이므로, b_i < M 이라는 조건도 얻을 수 있습니다.

위의 관찰 중 첫 번째 조건을 종합해 보면, M 으로 가능한 수들은 b_i - (b_i-1 + a_i) 들의 공약수임을 알 수 있습니다. 이들 중 두 번째 조건을 만족하려면, M 이 크면 클수록 좋다는 것을 알 수 있습니다.

따라서, b_i - (b_i-1 + a_i) 들의 최대공약수를 구한 뒤, 이것을 M 으로 놓고, 주어진 로그대로 입출금을 해보면서 모순이 없는지 확인하면 됩니다.

뒤집기

제출자 61명
정답자 60명
문제 풀러 가기

문제를 잘 관찰해 보면, 인접한 두 격자의 색이 다른 경우 두 격자의 현재 상태는 초기 상태와 같다는 성질을 발견할 수 있습니다.

증명) 인접한 두 격자의 현재 상태가 BW 일 때, 원래 WW 거나 BB 였다면, 두 격자는 연결되어 있으므로 현재 상태와 같이 달라지는 경우는 발생하지 않습니다. 원래 WB 였다면 상태가 바뀔 때 BW 로 한 번에 바뀔 수 없고, WW 또는 BB 를 거쳐야 하므로 불가능합니다. 따라서 초기 상태가 BW 였음을 알 수 있습니다.

인접한 격자 중 자신과 색이 다른 것이 존재하는 격자들의 경우 위 성질에 의해 색이 정해지고, 그 외의 격자들은 초기 상태에 아무렇게나 칠해져 있어도 현재 상태로 만들 수 있음을 알 수 있습니다. (연결된 컴포넌트들의 경계선에 있는 부분은 색이 정해 지므로, 내부는 아무렇게나 칠해져 있어도 경계선과 동일하게 만들 수 있습니다.)

따라서, 가능한 초기 상태의 수는 2^{(색이 정해지지 않은 격자의 수)} 가 됩니다.

섬

제출자 53명
정답자 22명
문제 풀러 가기

튜브는 연료를 구하러 망망대해로 나가고 싶으나, 사냥꾼이 어떠한 섬을 점거했을 때 길이 막힐 것이 두려워 걱정하고 있습니다. 튜브는 현재 위치에서 안전하게 망망대해로 나갈 수 있을까요?

이 문제는 풀이의 방향이 크게 두 갈래로 나뉩니다. 하나는 출제진이 의도하였던 풀이이고, 하나는 출제진이 예상하지 못했던 방향의 풀이입니다. 첫 번째 풀이를 중심으로 설명하나, 두 번째 풀이에 대해서도 간단히 짚고 넘어가겠습니다.

의도된 풀이 : 그래프의 절점

문제를 다시 요약해 보겠습니다. 우리는 튜브가 도착한 각각의 섬 v 에 대해서, v 와 다른 섬 w 중, w 에 사냥꾼이 있을 때 v 에서 최외곽으로 갈 수 있는 경로가 없어지는 w 가 존재하는가가 궁금한 것입니다. 결국에는 “경로” 와 “섬” 에 대한 이야기니, 그래프에 풀어놓고 생각해보면 편리하게 문제를 해결할 수 있습니다.

그래프에 있는 모든 4방향으로 인접한 육지와 바다를 Flood-Fill 로 하나의 정점으로 묶어줍시다. 이제 각각의 정점은 “섬” 이거나 “바다” 로 분류될 수 있습니다. “섬” 과 “바다” 가 맞닿아 있으면 간선을 이어줍시다. 최외곽의 바다를 1번 정점이라고 하면, 우리가 풀고자 하는 문제는 다음과 같습니다.

그래프 G 와 튜브가 도착한 각각의 섬 정점 v 에 대해, w ≠ v 가 존재하여, G 에서 w 를 제거했을 때 1 번 정점과 v 번 정점을 잇는 경로가 존재하지 않는다.

왠지 익숙한 느낌이 들지 않나요? 그래프에서 정점 하나를 제거했을 때 경로가 사라지는 형태의 문제이니, “절점”의 개념을 활용할 수 있다고 생각할 수 있습니다. 그래프에서 어떠한 정점을 제거하였을 때, 컴포넌트의 개수가 증가하는 정점들을 “절점” 이라고 부릅니다. 절점에 대한 자세한 설명은 지면상 생략하겠으나, 어떠한 정점이 절점인지 아닌지를 판별하는 것은 선형 시간에 가능합니다.

절점 개념을 도입하면, 문제는 다음과 같이 변합니다.

모든 섬 v 에 대해서, “절점인 섬” 을 지나지 않고 1 번 정점에서 v 번 정점을 방문할 수 있는지 아닌지를 판별하여라.

이는 절점을 구하는 알고리즘을 조금만 응용하면 됩니다. 1번 정점에서 DFS 를 시작했을 때, 어떠한 점이 절점이면, 해당 점을 거쳐야만 1번 정점으로 갈 수 있는 점들의 집합이 DFS Tree 상의 서브트리로 표현이 됩니다. 이는 문제가 “서브트리에 있는 정점에 대해서 마킹을 하시오” 의 형태로 환원이 된다는 것을 의미합니다. 서브트리에 있는 정점은 Euler Tour 번호에서 연속된 구간을 이루기 때문에, 구간에 대한 마킹으로 변환할 수 있으며, 이는 변화값 배열을 사용해서 해결할 수 있습니다.

다른 풀이

입력이 결국에는 평면 상의 격자의 모습임을 상기해 보면, 사냥꾼이 점령하고 있는 섬 안에 “둘러싸인” 섬들은 위험한 섬이 된다는 것을 알 수 있습니다. 즉, 각각의 섬에 대해서 그 섬이 “둘러싸고” 있는 섬들이 무엇인지를 알면 문제를 해결하는 데 조금 더 가까워질 수 있습니다. 둘러싸고 있는 영역을 Flood-Fill 해 주면 되기 때문입니다.

다른 풀이는 이 “둘러싸고 있는 영역” 을 효율적으로 구하는 데 초점을 맞춥니다. 각각의 섬에 대해서 Flood-Fill 로 해당 섬의 영역을 구해주고, 영역의 빈자리를 찾아낸 후, 해당 빈자리를 다시 Flood-Fill 로 구해주는 것이죠.

직관적으로는 이 부분이 매우 자명하나, 이를 알고리즘으로 옮기는 것은 또 다른 난이도입니다. 여기부터는 출제진도 말을 아끼겠습니다 :D 위 방법은 절점과 같은 고급 개념이 필요하지 않은 알고리즘이지만, 이러한 부분에서의 난이도가 상당히 있었는지, 초반에 이 문제를 빠르게 푼 대부분의 참가자들은 절점 알고리즘을 사용하였습니다.

보물 상자 열기

제출자 18명
정답자 12명
문제 풀러 가기

먼저, 초기 상태가 회문인 경우에는 답이 모두 0입니다. 그렇지 않은 경우, 주어진 문자열을 S[1~N] 이라 할 때, S[i] 가 S[N+1-i] 와 다른 최소의 i 를 b 라 하고, e = N-b+1 로 두면 주어진 문자열을 회문으로 만들기 위해서는 b 번째 석판이나 e 번째 석판을 교체해야 한다는 것을 알 수 있습니다.

또한 [b, e] 구간 밖에서는 석판을 교체할 이유가 없으므로 시작 위치가 i 일 때 소모해야 하는 체력을 H[i] 라 하면,

i < b 인 경우 H[i] = H[b] + (b-i) * c
i > e 인 경우 H[i] = H[e] + (i-e) * c

가 되고 S[b~e] 에 대해서만 문제를 해결하면 됩니다. b 와 e 중 석판 b 를 교체하는 경우를 생각해 보면 시작 위치가 x 번째 석판일 때 가능한 경로를 다음과 같은 2가지로 분류할 수 있습니다.

x->r->b (x에서 오른쪽으로 갔다가 왼쪽으로 이동하여 b로 가는 경우)
x->b->r (x에서 왼쪽으로 이동하여 b로 갔다가 오른쪽으로 가는 경우)

두 경우 모두 [b, r] 의 석판만 교체하여 문자열을 회문으로 만들 수 있어야 가능하고, 또한 [b, r] 에 회문에서 서로 대응되는 두 석판이 모두 포함되는 경우 교체 시 드는 체력이 작은 쪽을 고르는 것이 항상 이득입니다.

모든 r 에 대해 [b, r] 구간을 방문할 때 회문을 만들기 위해 석판을 교체하는 데 드는 체력을 배열 P[] 에 미리 저장해 놓을 수 있습니다. 그러면 x 가 주어졌을 때 x <= r 인 모든 r 에 대해 P[r] + (r-x) + (r-b) 의 최솟값이 x->r->b 의 경로 중 최적인 값이고, P[r] + (x-b) + (r-b) 의 최솟값이 x->b->r 의 경로 중 최적인 값입니다. 이는 x 를 e 부터 시작하여 왼쪽으로 한 칸씩 밀면서 계산하면 모든 x 에 대해서 O(N) 시간에 계산할 수 있으므로 석판 b 를 교체하는 경우에 소모해야 하는 최소 체력을 O(N) 시간에 계산할 수 있습니다. 석판 e 를 교체하는 경우도 대칭적으로 생각하면 마찬가지 방법으로 가능합니다.

따라서 선형 시간에 문제를 해결할 수 있습니다.

조용한 생활관 만들기

제출자 7명
정답자 0명
문제 풀러 가기

먼저, Union 마법을 사용했을 때 사용하기 전보다 더 시끄러워지는 경우는 없습니다. 처음은 directed rooted tree 형태의 그래프이고, 최종 상태는 Union 마법을 더 이상 쓸 수 없는 상태여야 하므로 모든 도로의 끝점은 트리의 leaf 일 것입니다. 이 점에 착안하여 생각해보면 이 문제는 directed rooted tree 의 edge 들을, leaf 를 끝점으로 하는 여러 경로들로 나누어 각 경로의 시작점과 끝점에 있는 건물의 사람 수의 곱을 최소로 만드는 문제입니다. 즉, 건물 i 에 사는 사람의 수를 C[i] 라 할 때, 최종 상태의 모든 경로 u->v 에 대해 C[u]*C[v] 의 합을 최소화하면 됩니다.

처음에 주어진 directed rooted tree 에서, root 가 아닌 노드 u 를 생각해봅시다. 또한, u 를 root 로 하는 subtree 를 subtree(u) 라고 합시다. u 의 부모에서 u 로 들어오는 간선이 있으므로, 최종 상태에는 u 의 조상 중 하나에서 subtree(u)에 포함되는 leaf 로 가는 경로가 하나 있을 것이고, 그 경로에 포함되지 않는 subtree(u)의 edge 들은 subtree(u) 내부의 경로가 될 것입니다.

결론적으로, subtree(u) 내부의 edge 들이 최종적으로 어떤 경로에 포함될지 결정된다면, 외부에 영향을 끼치는 요소는 u 의 조상 중 하나와 연결될 leaf 의 건물에 있는 사람 수 뿐입니다. 따라서, 다음과 같은 다이나믹 프로그래밍을 생각할 수 있습니다.

D[u][l] : u 의 조상 중 하나와 연결되는 leaf 가 l 일 때, u 내부 경로들에서 만들어지는 시끄러운 정도의 최솟값

점화식은 다음과 같습니다.

u = l : D[u][l] = 0
u ≠ l : u 의 자식 중 x 가 l ∈ subtree(x)을 만족할 때,
D[u][l] = D[x][l] + (u 의 x 가 아닌 모든 자식 v 에 대해, (D[v][l’]+C[u]C[l’]) 의 최솟값들의 합
(단, l' 은 subtree(v)의 leaf))

각 자식 노드 v 에 대해 D[v][l'] + C[u]C[l'] 이 최소가 되는 l' 을 미리 구해놓을 수 있으므로, 시간 복잡도는 각 노드 u 에 대해 subtree(u)의 leaf l 을 선택하는 경우의 수인 O(N²)가 됩니다. 위 다이나믹 프로그래밍은 O(N²)의 시간 복잡도를 가지므로, 시간 초과가 발생하게 됩니다. 이를 줄이기 위해서는 한 가지 관찰이 필요합니다.

subtree(u)의 모든 leaf l 에 대해, 좌표평면 상에서 y = C[l] * x + D[u][l] 라는 직선을 그었다고 생각해봅시다. 0 이상의 모든 x 에 대해 그 x 에서 함숫값이 최소가 되는 직선을 구했다고 합시다. 만약 어떤 x 에서도 함숫값이 최소가 되지 않는 직선이 있다면, 그 직선은 최적해를 구하는 데에 있어 쓸모가 없습니다. 그 leaf 가 u 의 어느 조상과 연결되든 간에 더 좋은 방법이 존재하기 때문입니다. 따라서 정점 u 에 대해 subtree(u)의 모든 leaf 에 대한 값을 저장할 필요가 없고, 위에서 설명한 직선들의 아래쪽 convex hull 만을 들고 있으면 충분합니다.

앞에서 설명한 DP를 이 convex hull 을 이용해서 할 수 있는데, 먼저 u 의 모든 자식 v 에 대해 D[v][l'] + C[u]C[l'] 의 최솟값은 v 의 아래쪽 convex hull 이 x = C[u] 와 만나는 부분임을 쉽게 알 수 있습니다. 따라서 이를 미리 계산해 놓을 수 있습니다. 또한 u 의 자식 v 에 대해 subtree(v)에 포함되는 leaf 가 u 의 조상과 연결되는 경우는 v 의 convex hull 이 일정 크기만큼(정확히는 v 가 아닌 모든 자식 c 에서 D[c][l'] + C[c]C[l'] 의 최솟값의 합만큼) 위로 올라간 것임을 알 수 있습니다. 따라서, 자식들에 저장된 convex hull 들을 y 축 방향으로 평행 이동시킨 후에 모두 합쳐서 convex hull 을 다시 구할 수 있다면 앞서 설명한 DP 와 정확하게 같은 것을 할 수 있는 것입니다.

먼저 set 을 이용해 Dynamic Convex Hull 자료구조를 만들면 O(log N) 시간에 직선을 추가하는 연산을 수행할 수 있고, 어떤 x 좌표가 주어졌을 때 convex hull 에서 해당하는 y 좌표를 이분 탐색을 이용해 O(log²N) 시간에 찾을 수 있습니다.

y축 방향으로 얼마만큼 평행이동되었는지는 따로 저장해 놓으면 쉽게 관리할 수 있습니다. x 좌표가 주어졌을 때 convex hull 에서 y 좌표를 찾는 연산은 D[v][l'] + C[u]C[l'] 의 최솟값을 찾을 때 사용하므로 총 O(N)번 쓰게 되어 여기서 시간 복잡도 O(N log²N)가 발생합니다. 자식들의 convex hull 들을 합쳐야 하는데, 자식들 중 가장 직선이 많은 convex hull 에 다른 자식들의 convex hull 의 직선을 삽입하는 small-to-large 방식으로 이를 해결할 수 있습니다. 여기에서 직선 삽입은 Heavy-Light Decomposition 과 같은 원리로 최대 O(N logN)번만 수행됩니다. 따라서, 여기서 발생하는 시간 복잡도는 O(N log²N)입니다.

따라서, 총 시간 복잡도 O(N log²N)에 문제를 해결할 수 있습니다.

자석 장난감

제출자 8명
정답자 1명
문제 풀러 가기

이 문제는 그래프에서 규칙에 따라 모든 노드를 제거할 수 있는지 확인하는 문제입니다.
제거하는 규칙은, 어떤 노드 X 가 제거될 때 그 노드에 연결된 다른 모든 노드 A, B, …, D 가 서로 모두 연결되어 있어야 한다는 것입니다. 이 조건에서 X, A, B, …, D 는 하나의 Clique(모든 노드 쌍이 연결된 부분 그래프)를 이룬다는 것을 알 수 있습니다. 그래프의 한 상태에서 제거될 조건을 만족하는 노드는 어느 것을 먼저 제거하더라도 상관없다는 것을 짐작할 수 있고 증명할 수 있습니다. 하지만, 이렇게 조건을 하나하나 확인하면서 제거할 수 있는 노드를 찾아 나가며 진행하는 것은 매우 느린 방법이 됩니다.

빠른 방법 중 하나는 노드를 제거하는 “특정한 순서”를 찾고, 그 순서에 따라서 노드를 제거했을 때 조건을 만족하면서 모든 노드를 제거할 수 있음을 확인하는 것입니다. 이 “특정한 순서”는, 만약 모든 노드를 제거할 수 있는 순서가 하나라도 있다면 반드시 모든 노드를 제거할 수 있는 순서가 된다는 성질을 가집니다. 모든 노드를 제거할 수 있는 그래프는 Clique 들이 서로 노드를 공유하는 모양으로만 구성되어 있어야 한다는 것을 어렵지 않게 짐작할 수 있고 증명할 수 있습니다.

비교적 단순하게 두 개의 Clique P 와 Q 가 일부 노드를 공유하고 있는 그래프로 설명해 보겠습니다. 이 그래프는 모든 노드를 제거하는 것이 가능한 그래프임이 당연합니다. 노드들의 집합 P-Q, Q-P, P∩Q 를 생각해 봅시다. P-Q 나 Q-P 에 있는 노드가 가장 먼저 제거되는 것은 가능하지만, P∩Q 에 있는 노드가 가장 먼저 제거되는 것은 불가능합니다. P-Q 나 Q-P 중 한 집합이라도 모두 제거되어야 P∩Q 에 있는 노드가 제거될 수 있음을 알 수 있습니다.

이제, 아무 노드에서나 시작해서 그래프를 탐색하면서 방문하는 순서대로 노드들을 출력합니다. 노드가 출력되면 노드에 연결된 다른 노드들에 모두 카운터를 1 증가시키는 연산을 합니다. 카운터 값이 큰 노드부터 무조건 다음에 출력합니다.

만약 이 탐색이 P-Q(혹은 Q-P) 에 있는 노드에서 시작된다면 P(혹은 Q)가 모두 출력된 다음에야 나머지 노드가 출력될 수 있습니다.
만약 이 탐색이 P∩Q 에 있는 노드에서 시작된다면, 탐색이 최초로 P-Q(혹은 Q-P) 에 들어가는 순간 P-Q(혹은 Q-P) 에 있는 노드가 모두 출력된 다음에야 Q-P(혹은 P-Q) 에 있는 노드가 출력됨을 알 수 있습니다.

모든 경우를 증명하는 것은 복잡하지만 이런 방식으로 출력하면, 출력의 반대 순서가 반드시 제거 가능한 순서가 됨을 알 수 있습니다.

특정한 하나의 순서를 찾았으면 이 순서가 규칙을 지키는 제거 순서인지를 확인해야 합니다. 제거 과정에서 매번 규칙을 전부 확인하면 시간이 아주 오래 걸리게 됩니다. 하지만, 이 과정을 살펴보면 동일한 노드 쌍의 연결 관계를 반복적으로 확인하고 있음을 알 수 있습니다. 동적 프로그래밍과 비슷한 방법으로 반복적으로 확인하는 것을 한 번만 확인하도록 줄여서 빠른 시간에 규칙을 지키는지 확인하는 것이 가능합니다.

이러한 두 가지 과정을 거쳐서 O((N+M)logN) 시간 알고리즘을 구현할 수 있습니다.
대회에서는 O(N sqrt(N)) 정도 알고리즘도 통과할 수 있는 수준으로 채점 데이터가 만들어졌습니다.

헬리콥터

제출자 4명
정답자 0명
문제 풀러 가기

이 문제는 직교 다각형 형태로 주어진 영역을 왼쪽에서 오른쪽으로 비행할 때 단 한 번의 사선 방향을 제외하고는 모두 수직이나 수평으로만 움직일 수 있다고 가정하고 가장 짧은 거리를 찾는 문제입니다. 이 문제의 답을 구현하는 것은 매우 어렵지만 아이디어를 설명하는 것은 비교적 간단합니다.

우선, 사선 방향 없이 수직 수평으로만 움직이는 경로를 생각해 봅시다. 주어진 영역 안에서 그러한 최단 경로는 매우 많습니다. 최단 경로들을 모두 그렸다고 하면 그려진 경로들은 모여서 하나의 영역을 만들게 됩니다. 이 영역을 “새 영역”이라고 부릅시다. 새 영역을 구하는 것은 O(N) 시간에 가능합니다.

단 한 번의 사선 방향으로의 움직임(사선 성분)에 대해 다음 세 가지를 확인할 수 있습니다.

(1) 최적인 사선 성분은 새 영역 안에 있다.
(2) 최적인 사선 성분은 새 영역의 경계를 끝점으로 가진다.
(3) 최적인 사선 성분은 새 영역의 꼭짓점과 교차한다.

이 세 가지 성질에서 다음과 같은 알고리즘을 만들 수 있습니다.
새 영역의 각 꼭짓점에서 그 꼭짓점에 걸치면서 그 꼭짓점에서 보이는 영역의 경계 위의 두 점을 잇는 모든 선분을 확인합니다. 각 꼭짓점에서는 O(N)개의 다른 꼭짓점이 보입니다. 선분들 중 적어도 한쪽이 꼭짓점인 것들은 따라서 O(N)개가 됩니다. 이들 중 최적인 것이 있다면 쉽게 확인할 수 있습니다. 이들 중 최적인 것이 없다면 앞에서 확인한 선분들 사이를 회전시켜 가면서 최적인 선분을 찾아볼 수 있습니다. 선분을 회전할 때 사선이 만들어 내는 이익은 증가나 감소를 최대 한 번 바꿀 수 있다는 것을 알아낼 수 있어 삼분 탐색으로 충분한 오차 이내까지 선분을 찾아 내려갈 수 있습니다.

이러한 방법으로 O(N² logN * log10⁹) 시간이 걸리는 알고리즘을 만들 수 있습니다.
대회에서는 O(N³) 정도 되는 알고리즘도 통과할 수 있는 수준으로 채점 데이터가 만들어졌습니다.

결과 발표

그럼 이제, 코드 페스티벌 본선 결과를 공개합니다! 본선은 예선과 같은 방식으로 채점이 진행되었으며, 1등은 출제된 8문제 중 6문제를 풀어주셨습니다.

▶ 순위표 보러 가기

사전에 공지된 대로 우수한 성적을 거둔 상위 31명의 참가자에게 상장 및 상금이 수여되었습니다. 아쉽게 수상권에 들지 못한 분들을 위해 다양한 특별상도 준비했는데요, 수상하신 모든 분들 축하드립니다!

마지막으로 작년에 비해 본선 문제의 난이도가 높다는 피드백이 많았는데요, 그럼에도 불구하고 끝까지 코드 페스티벌에 적극적으로 참여해주신 분들께 감사드립니다.

앞으로 있을 개발자 행사에도 많은 관심 부탁드립니다 :)

2019 카카오 블라인드 신입 개발자 공채가 시작됩니다!

Tue, 28 Aug 2018 10:00:00 +0900

카카오는 여전히 같은 생각입니다. 개발자가 자신의 가치를 증명할 수 있는 것은 자소서나 스펙이 아니라 코드라고 말이죠!

올해는 카카오를 포함하여 5개 기업이 함께 합니다. 지금 바로 도전하세요! new developer coming!

[2019 카카오 블라인드 신입 개발자 공채]

▶ 접수 기간 : 8월 27일 (월) 15:00 ~ 9월 11일 (화) 23:59
▶ 지원 접수 : www.welcomekakao.com
▶ 문의 사항 : apply@kakaocorp.com
▶ 모집 회사 : (주)카카오 / (주)카카오 게임즈 / (주)카카오 모빌리티 / (주)카카오페이지 / (주)카카오 페이
(총 5개 기업 중 1개 기업에 지원 가능)

2019 카카오 신입 개발자 공채는 스펙보다는 성장 가능성과 잠재력, 창의성 등이 뛰어난 신입 개발자 분들을 선발하기 위해 학력, 경력 등 스펙이 아닌 코딩 능력으로만 검증하는 ‘블라인드’ 전형으로 실시될 예정입니다.

블라인드 전형 취지에 맞게 응시자는 학력, 나이, 성별, 경력 등을 기입하지 않고 이름/메일/ 연락처 등만 입력한 후 본인 계정을 생성하면 코딩 테스트에 응시할 수 있습니다!

올해는 (주)카카오, (주)카카오게임즈, (주)카카오모빌리티, (주)카카오페이지, (주)카카오페이 5개의 기업이 신입 공채를 함께 진행합니다.

지원자는 서류 전형 없이 9월15일부터 코딩테스트를 볼 수 있으며, 이후 오프라인 코딩 테스트, 1차 및 2차 인터뷰가 순차적으로 진행됩니다. 11월 중 최종 합격 발표 예정이며, 합격자들은 오리엔테이션을 거쳐 내년 1월 정식 입사하게 됩니다. (기업 별로 일자는 상이할 수 있습니다)

카카오 블라인드 공개 채용과 관련한 자세한 내용은 www.welcomekakao.com에서 확인, 지원 가능합니다. 개발에 대한 열정과 창의성을 갖춘 많은 분들의 지원을 기다립니다 :)

▶카카오 블라인드 신입 개발자 공채 지원하러가기

코드 페스티벌 2018 예선전 이야기

Thu, 09 Aug 2018 17:00:00 +0900

카카오 코드 페스티벌 예선전, 많은 관심 감사합니다!

작년에 이어 두 번째로 진행된 카카오 코드 페스티벌, 온라인 예선이 지난 8월 4일 토요일에 진행됐습니다. 작년보다 더욱 많은 6,000여 명의 참가자들이 6시간 동안 뜨거운 열정을 발휘했는데요, 특히 실시간으로 바뀌는 스코어보드를 보면서 치열한 접전을 느낄 수 있었습니다. 여기 예선 문제와 해설, 그리고 결과를 공유합니다. 참가해주신 모든 모든 분들께 감사드립니다!

문제 설명 및 풀이

상금 헌터

제출자 3120명
정답자 2686명
문제 풀러 가기

대회에 참가해서 얼마의 상금을 받을 수 있을지를 계산하는 문제로, 주어진 조건대로 구현하면 됩니다. if문을 사용해서, a와 b가 어떤 범위가 있는지에 따라 상금을 구하거나, 크기가 101인 배열 A[0..101]와 65인 배열 B[0..64] 두 개를 만들어서, 각각 1회/2회 대회에서 i등을 하면 얼마의 상금을 받는지를 저장한 뒤 계산하는 방법 등이 있습니다.

인형들

제출자 2138명
정답자 942명
문제 풀러 가기

길이가 N인 수열이 주어졌을 때, 이 중 K개 이상의 연속된 수를 선택하여 표준편차를 최소로 만드는 문제입니다. 범위가 작기 때문에 정의된 대로 직접 계산해도 되고, 이를 좀 더 효율적으로 계산할 수도 있습니다.

Naive: O(N³)

모든 경우를 다 고려하여 구현해보는 방법입니다. j - i + 1 ≥ K, 1 ≤ i, j ≤ N 을 만족하는 모든 i, j에 대해서 다음과 같은 과정을 수행하면 됩니다.

m = (a[i] + a[i+1] + … + a[j]) / N
v = ((a[i] - m) * (a[i] - m) + … + (a[j] - m) * (a[j] - m)) / N

참고로, 여기서 m, v는 각각 (산술) 평균과 분산을 의미하며, 문제에 나와있는 식과 같습니다. 그 후 구한 v 중에서 최솟값을 구하고 이 값의 음이 아닌 제곱근을 출력하면 됩니다.

가능한 (i, j)의 가짓수가 O(N²)이므로, 모든 (i, j)에 대하여 평균과 분산을 구하는 프로그램의 시간복잡도는 O(N³)이 됩니다.

O(N²)

(분산) = (제곱의 평균) - (평균) * (평균) 이라는 성질이 알려져 있습니다. 그러므로 누적 합 배열과 제곱의 누적 합 배열을 만들면, j - i + 1 ≥ K, 1 ≤ i, j ≤ N 을 만족하는 모든 i, j에 대해서 평균과 분산을 O(1)의 시간에 구할 수 있습니다.

가능한 (i, j)의 가짓수가 O(N²)이므로, O(N²)의 시간복잡도로 문제를 풀 수 있습니다.

그 외에 추가로 고려해야 할 사항은 다음과 같습니다.

인형을 K개를 선택하는 것이 아니라 K개 이상을 선택해야 한다는 점이 있는데, 의도하지 않게 많은 분들이 처음에 이러한 것을 간과한 것으로 보입니다.
절대/상대 오차가 10^-6이므로, 실수의 정밀도 관련 문제에 대해 어느 정도 고려할 필요가 있습니다.
- C++ 기준으로, float를 이용하여 O(N³)을 적용하면 정답을 받지 못합니다. double / long double을 사용하면 정답을 받을 수 있습니다.
- 최대한 실수 연산의 수를 줄이는 것이 좋습니다. 예를 들어, 평균을 구할 때에는 수들의 합을 정수형 변수에 저장한 후 N으로 나누는 것이 실수형 변수를 이용하여 연산하는 것에 비해서 좀 더 정확하게 구할 수 있습니다.
Python으로 구현하는 경우, 다른 언어들에 비해 실행 시간이 더 걸리기 때문에, O(N³) 풀이를 구현하면 시간 초과를 받게 될 수 있습니다.

숏코딩

제출자 235명
정답자 50명
문제 풀러 가기

문제의 조건에 맞게 생성된 논리식이 입력되었을 때, 이 식과 동치인 논리식 중 가장 짧은 논리식을 찾는 문제입니다. ==과 !=를 나누어 생각합니다.

==: 각 단항식을 정점으로, <X>==<Y>를 <X>와 <Y>를 잇는 양방향 간선으로 생각한 그래프에서 한 컴포넌트에 속한 정점들은 모두 값이 같아야 합니다. 이는 ==가 동치관계(equivalence relation)이기 때문입니다.
- 한 컴포넌트에 있는 단항식들을 u₁, u₂, …, u_n이라고 하고, 그 중 길이가 가장 짧은 것을 u_i라고 하면, u_i와 다른 모든 정점을 잇는 n-1개의 간선만 있어도 정점들을 똑같이 묶을 수 있고, 이렇게 하는 것이 가장 길이가 짧습니다. 컴포넌트의 크기가 1이라면 (1==1, a==a 등으로 가능) 그 컴포넌트는 출력에 포함되지 않아야 합니다.
- 단, 같은 컴포넌트에 2개 이상의 정수가 있다면, 조건문은 항상 false를 반환합니다.
!=: <X>!=<Y>가 있다고 가정하면,
- <X>와 <Y>를, 같은 == 컴포넌트에 속한 가장 길이가 짧은 단항식으로 교체할 수 있습니다.
- (교체한 이후) 똑같은 != 조건문이 여러 개 있다면 그 중 하나만 남겨둘 수 있습니다.
- <X>와 <Y>가 같은 == 컴포넌트에 속한다면, 조건문은 항상 false를 반환하므로, 이와 동치인 가장 짧은 조건문(ex: x!=x, 4==7)을 출력해야 합니다.
- <X>가 속하는 == 컴포넌트에 정수가 포함되어 있고, <Y>가 속하는 == 컴포넌트에도 정수가 포함되어 있다면, 해당 비교 연산은 결국 서로 다른 두 정수를 비교하고 있으므로 필요가 없고, 따라서 제거할 수 있습니다.

위의 과정에서 비교 연산들이 모두 불필요하다고 판단되어 제거되었다면, 조건문은 항상 true를 반환하는 식이 됩니다. 항상 true나 false를 반환하는 가장 짧은 조건문은 길이가 4이며, 각각 T==T와 0!=0의 예시가 있습니다.

부스터

제출자 603명
정답자 102명
문제 풀러 가기

N개의 체크포인트 사이를 규칙에 맞게 이동하는 방법이 있는지를 찾는 문제입니다. 체크포인트의 수와 질의의 수 모두 최대 25만 개로 매우 많으므로 단순한 방법으로는 시간 안에 답을 구하기가 매우 힘들기 때문에, 다음과 같이 단계별로 알고리즘을 개선시켜볼 수 있습니다.

O(QN²)

문제를 있는 그대로 해석하면, 각각의 체크포인트에서 HP 재충전 / 부스터 재충전 여부를 모두 저장해야 하는 아주 복잡한 문제가 됩니다. 이 정보들을 최대한 간소화할 수 있을까요?

각각의 체크포인트에서 HP / 부스터의 재충전 여부를 기억할 필요가 없습니다. 어떠한 체크포인트에 두 번 이상 방문하는 경로가 있다면, 그 체크포인트를 마지막으로 빠져나간 방법을 처음부터 사용하면 됩니다. 그렇다면 임의의 체크포인트에는 많아야 한 번만 방문해도 답을 찾을 수 있고, 이 때 HP / 부스터를 재충전하지 않아서 손해를 볼 일이 없습니다. 고로, 체크포인트에 방문했다는 것은 HP / 부스터를 재충전했다는 것과 동일합니다.
체크포인트 간을 이동할 때 부스터는 많아야 한 번밖에 쓸 수 없는데, 처음에 부스터를 무조건 켜도 손해를 보지 않습니다. 처음에 걸어간 후 부스터를 사용하는 경로는, 똑같이 평행이동 시켜서 처음에 부스터를 사용한 후 걸어가는 경로로 바꿔줄 수 있기 때문입니다. 고로 처음에 부스터를 잘 켜서 걷는 거리를 최소화하는 문제인데, X좌표와 Y좌표 차 중에서 큰 쪽을 줄여나가는 전략이 유효하므로, 두 체크포인트 (X_u, Y_u)와 (X_v, Y_v)를 오갈 때 걸어가야 하는 최소 거리는 min(|X_u - X_v|, |Y_u - Y_v|)입니다.

이 관찰을 통해서 문제는 그래프 탐색 문제로 환원됩니다. 각각의 쿼리가 주어졌을 때, min(|X_u - X_v|, |Y_u - Y_v|)가 주어진 HP 제한 이하인 쌍에 대해서 양방향 간선이 있다고 생각하고, 깊이 우선 / 너비 우선 탐색을 사용해서 문제를 해결할 수 있습니다. 시간 제한을 맞추기에는 너무 느린 알고리즘이지만, 좋은 시작점으로 삼을 수 있겠죠.

O(N log N + QN)

현재 사용하는 방법의 문제점 중 하나는, 고려해야 할 간선의 개수가 O(N²)개에 육박할 정도로 많다는 것입니다. 이를 줄이기 위해서는 다음과 같은 아이디어가 필요합니다.

위 그래프에서 X좌표 차이로 이루어진 간선들만 생각해 봅시다. 그러한 간선들만 놓고 보았을 때 Y좌표는 중요한 요인이 아니기 때문에, 우리는 X축 수직선에 점들을 찍어놓고, 두 점의 거리차로 간선을 이었다고 생각할 수 있습니다. 그렇다면, 수직선 상에 인접하지 않은 두 점 간에 간선을 이을 필요가 있을까요? 인접한 정점을 타고서도 해당 위치로 도달할 수 있기에, 굳이 큰 가중치를 사용해서 수직선 상에 인접하지 않은 두 점을 오갈 필요가 없습니다.

같은 이야기는 Y좌표 차이로 이루어진 간선들에 대해서도 똑같이 적용됩니다. 이로써 얻을 수 있는 결론은 다음과 같습니다.

“X좌표 순으로 정렬했을 때 인접한 N-1개의 쌍과, Y좌표 순으로 정렬했을 때 인접한 N-1개의 쌍만 고려해도 된다.”

이제, 각각의 좌표로 정렬한 후, 인접한 쌍에 대해서만 간선을 이어주면 된다는 결론에 도달합니다. 그래프의 크기가 작아졌으니, 훨씬 더 문제를 해결하기 수월해졌죠. 물론, 여전히 탐색을 일일이 해 주기에는 쿼리의 수가 너무 많습니다.

O(N log N + Q log Q)

복잡도를 줄이는 전략이 여러 가지가 있으나, 이 중 가장 간단한 전략은 모든 쿼리를 X의 오름차순으로 정렬하는 것입니다. 결국 각각의 쿼리가 의미하는 바는, 가중치 X 이하인 간선들만 사용해서 두 정점을 오갈 수 있나? 라는 형태의 질문과 동일합니다. 이 때 모든 쿼리를 X의 오름차순으로 정렬했다면, 각각의 쿼리에서 보게 되는 간선들의 집합이 갈수록 커지게 됩니다.

간선들이 추가되는 상황에서 두 정점을 오가는 경로가 있는지, 즉 두 정점이 연결되어 있는지를 확인하는 좋은 자료구조로는 유니온 파인드(Union-Find, 서로소 집합Disjoint Set이라고도 합니다)가 있습니다. 가중치 순서대로 모든 간선과 쿼리를 보면서, 간선이 나오면 두 정점을 하나의 집합으로 합쳐주고, 쿼리가 나오면 두 정점이 같은 집합에 있는지를 보면 됩니다. 이 방법을 사용하면 O(Q log Q) 정렬 이후 각각의 쿼리를 O(log N) 정도의 속도로 해결할 수 있습니다.

쿼리를 정렬하지 않고 그때 그때 결과를 알아내는 방법도 있습니다. 이 방법은 그래프의 최소 스패닝 트리(Minimum Spanning Tree)에 속하는 간선만이 중요하다는 사실에 기반합니다. 해당 사실을 사용하면, 주어진 쿼리는 트리 상의 어떠한 경로에 있는 간선들의 가중치가 모두 X 이하인가? 라는 문제로 변환되며, 이는 트리의 경로에 대한 최댓값을 빠르게 구하는 자료구조를 O(N log N)에 만들어 놓으면, 각각의 쿼리 당 O(log N)에 해결할 수 있습니다. 조금 더 어려운 도전이 필요하다면 시도해 보셔도 좋습니다. :)

음악 추천

제출자 211명
정답자 34명
문제 풀러 가기

추천이 여러 번 이루어지고 각각의 추천마다 여러 개의 노드의 값을 갱신하는 과정을 반복할 때, 지정된 값을 넘는 시점이 언제인지를 판단하는 문제입니다. 추천 횟수는 최대 10만 번이고 각각에 대해 값이 갱신되는 노드가 최대 10만 개이므로 단순히 값을 하나씩 갱신하는 방식으로는 시간 안에 답을 구할 수 없습니다.

트리 형태로 데이터가 주어지고, 서브트리 내의 모든 값에 일정한 값을 더하는 질의를 처리하기 위해서는 트리를 깊이 우선 탐색으로 방문하는 순서대로 원소를 나열하는 트리 순회 배열(Tree Traversal Array)을 만들고, 구간 트리(Segment Tree)를 사용하여 서브트리에 대응되는 구간의 값을 갱신하는 방식을 일반적으로 사용합니다.

특정 시점에 노드에 부여된 가중치를 구하는 과정은 노드마다 O(log N) 시간이 걸리기 때문에, 갱신이 이루어질 때마다 가중치의 합을 구하는 방식은 매우 비효율적입니다. 가중치의 합이 목표 점수를 언제 넘게 되는지만 구하면 되기 때문에, 목표 점수를 넘는 시간에 대한 이분 탐색을 진행할 경우, 특정한 가수의 평균 점수가 목표 점수를 넘는 시간을 O((K log N + N’ log N)log T) 시간에 계산할 수 있습니다. 이 때 N’은 해당 가수가 부른 곡의 수, 즉 노드의 개수이고 T는 시간의 최대 범위인 10⁹입니다.

문제에서는 각 가수 별로 목표 점수를 넘게 되는 시점을 구해야 하므로, 위 과정을 모든 가수에 대해 반복할 경우 시간 안에 답을 구하기 힘듭니다. 이때 사용할 수 있는 방법이 병렬 이분 탐색(Parallel Binary Search)입니다. 이분 탐색은 구하는 값의 상한과 하한을 정한 다음 구간의 길이를 반으로 줄여나가는 과정을 반복하는 방법인데요, 구하는 값이 여러 개인 경우 각각에 대해 상한과 하한을 저장하는 배열을 정의한 뒤 한 번 계산할 때마다 모든 구간을 각각의 범위에 맞게 절반씩 줄여나갑니다. 그러면 가수의 평균 점수를 계산하는 과정은 각 가수별로 진행해야 하지만 가중치를 부여하는 과정은 여러 번 반복할 필요가 없기 때문에 모든 가수에 대해 답을 계산하는 데 걸리는 시간이 O((K log N + N log N)log T)가 됩니다. 위 식과 비교하면 값을 갱신하는 과정의 시간 복잡도는 O(K log N log T)로 같으며, 가수별로 부른 곡의 수의 합이 N이 되므로 합을 계산하는 과정의 전체 시간이 O(N log N log T)가 됨을 알 수 있습니다.

프로도의 100일 준비

제출자 122명
정답자 7명
문제 풀러 가기

L-모양 직각다각형은 반드시 └ 또는 ┘ 모양이어야 하며, 밑변이 x축에 붙어 있어야 합니다. 이는 주어진 도형이 히스토그램 모양이기 때문입니다.┌ 또는 ┐ 모양이 가능하다면 넓이가 더 넓은 직사각형도 가능하고, 밑변이 x축보다 위에 있다면 도형을 연장하여 x축에 붙일 수 있습니다. 그러고 나면, L-모양 직각다각형은 밑변이 x축에 붙어 있고, 서로 인접한 두 개의 직사각형이 붙어 있는 형태임을 알 수 있습니다. 이렇게 정의를 하면 정점의 수가 4와 6인 경우를 모두 고려하게 됩니다.

가장 넓은 L-모양 직각다각형을 찾기 위하여, 역으로 두 직사각형이 붙어 있는 x좌표 x₀을 고정해 봅시다. x ≤ x₀인 영역과 x ≥ x₀인 영역은 독립적이므로, 각각에 대해 가장 넓은 직사각형을 구한 뒤 넓이를 더하면 됩니다. 즉, x = x₀ 왼쪽/오른쪽 영역에서, x = x₀에 붙어 있으면서 히스토그램에 들어 있는 가장 넓은 직사각형을 구하면 됩니다.

이렇게 접근했을 때 첫 번째로 당면하는 문제는 x₀이 너무 많다는 것입니다. 다행히도, x₀으로 가능한 값들은 입력으로 주어진 x좌표들뿐입니다. 이는 f(x₀)을 윗 문단의 상황에서 가장 넓은 L-모양 직각다각형의 넓이로 둔다면, f가 구간별로 선형인 함수(piecewise linear function)이며(연속 함수는 아닙니다), 끊기는 지점들이 입력으로 주어진 x좌표들뿐임을 관찰함으로써 알 수 있습니다.

남은 것은 x = x₀ 왼쪽 영역에서, 오른쪽 변이 x = x₀에 붙어 있으면서 히스토그램에 들어 있는 가장 넓은 직사각형의 넓이를 구하는 것입니다. 오른쪽 영역에서 구하는 것은 똑같이 할 수 있습니다. 문제 자체가 히스토그램에서 가장 넓은 직사각형을 구하는 상황과 굉장히 유사합니다. 이 문제는 스택을 활용해 해결할 수 있는 방법이 잘 알려져 있습니다. 이 방법을 “알고리즘 X”라고 부르겠습니다.

알고리즘 X는 히스토그램을 왼쪽에서부터 오른쪽으로 훑습니다. 각 x좌표를 고려하는 상황에서, 스택에는 (높이 h, 해당 높이 이상이 유지되는 가장 왼쪽 x좌표 x_l)의 쌍들이 들어 있습니다. 이 때, 오른쪽 변이 x = x₀인 가장 넓은 직사각형을 구하기 위해 할 수 있는 가장 쉬운 생각은 스택을 모두 순회해 보는 것입니다. 스택의 원소 (h, x_l)에 대해, 넓이는 h(x₀ - x_l)입니다. 하지만 모두 순회하는 것은 굉장히 느립니다.

그런데, 식의 꼴을 살펴보면 기울기가 h이고 y절편이 -hx_l인 직선임을 알 수 있습니다. 즉, 우리가 원하는 것은 여러 개의 직선들이 있을 때, x = x₀에서 최댓값을 구하는 것입니다. 컨벡스 헐 트릭(Convex Hull Trick)을 사용할 수 있을 것이라고 생각할 수 있습니다. 마침, 알고리즘 X를 생각해 보면 스택에 저장된 h는 아래에서 위로 갈수록 순증가하기 때문에, 직선의 기울기가 순증가할 때 사용할 수 있는 컨벡스 헐 트릭에도 알맞아 보입니다.

문제는, 알고리즘 X에서 스택의 원소가 빠지기도 한다는 것입니다. 컨벡스 헐 트릭에서 추가된 직선 l에 의해 삭제된 직선들이 있을텐데, 스택에서 원소가 제거되는 과정에서 이 삭제된 직선들이 다시 복구되어야 하는 경우가 발생할 수 있습니다. 이 점을 해결하기 위해 크게 세 가지 방법이 있습니다.

스택을 삭제된 데이터가 보존되는 형태(Persistent Stack)로 관리합니다. 다음의 글을 참고하시면 도움이 됩니다. http://codeforces.com/blog/entry/51684
구간에 직선을 추가하고(즉, 선분을 추가하는 것), 특정 x좌표에서의 최대 y좌표를 구하는 자료구조가 있습니다(Li Chao Segment Tree). 스택의 어떤 원소 (h, x_l)이 x = x_r에서 제거된다고 하면, 해당 자료구조에서 [x_l, x_r] 구간에 y = h(x - x_l)을 추가합니다. 모든 직선이 추가된 이후, 각 x좌표에서의 최댓값을 구하면 됩니다.
이 작업은 구간 트리(Segment Tree)의 각 노드에 컨벡스 헐 트릭 구조를 저장해놓는 방식으로도 구현할 수 있습니다. 추가해야 할 직선들에 대한 정보를 미리 처리한 뒤, h에 대해 오름차순 정렬하여 순서대로 추가하면 됩니다.

곧 있을 코드 페스티벌 본선을 기대해주세요!

예선 참가자 중 우수한 성적을 거둔 64명이 본선에 진출하게 됩니다. 예선 순위표는 홈페이지(https://www.kakaocode.com)에 같이 공지할 예정이니 참고하시기 바랍니다. 본선 진출자들이 즐거운 경험을 가지고 돌아갈 수 있도록, 카카오에서 열심히 준비하고 있으니 많이 기대해주세요!