오픈채팅방 문제 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. [닉네임]님이 들어왔습니다. 채팅방에서 누군가 나가면 다음 메시지가 출력된다. [닉네임]님이 나갔습니다. 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경한다. 닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다. 예를 들어, 채팅방에..

자물쇠와 열쇠 문제 https://programmers.co.kr/learn/courses/30/lessons/60059# 문제 설명 고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다. 자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에..

괄호 변환 문제 programmers.co.kr/learn/courses/30/lessons/60058 문제 설명 카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다. 용어의 정의 '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개..

개요 YAML : YAML Ain't Markup Language 재귀를 통해 이름짓기 쿠쿠 기존에는 프로그램의 설정을 저장하고 읽는데에 xml 형식을 써왔다. 하지만 작성이 너무 귀찮아서 다른 방식을 강구하게 되었다. 정보를 저장할 수만 있다면 다른 방식도 가능하다. 그래서 나온게 json 파일 형식이다. json은 객체 형식으로 xml보다는 간편한 작성이 가능하다. 허나 더 쉽게 작성할 수 있는 형식이 바로 YAML 형식이다. YAML은 가독성이 좋아서 JSON에 비해 구조가 복잡하지만 사람이 보기에는 자연스러운 형태이다. 이에 따라 YAML은 설정 파일의 목적으로 많이 쓰이고, JSON은 설정 파일을 제외한 분야에서 모두 널리 쓰이고 있다. 이러한 파일 형식들은 상황마다 필요에 따라서 사용하면 된다..

2020 KAKAO BLIND RECRUITMENT 문자열 압축 문제 문제 설명 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 ..

최단 경로 그래프에서 유도되는 문제들 중 최단 경로 문제가 있다. 주어진 그래프에서 특정 정점에서 다른 정점까지의 최단 경로(가중치 합이 최소인 경로)가 무엇인지를 알아내는 문제이다. 이는 이전의 MST 문제와 다르다. 모든 정점을 포함할 필요가 없기 때문이다. 하지만 MST에서 사용했던 Prim(Dijkstra) 알고리즘을 응용해서 구현할 수 있다. [MST] Dijkstra 알고리즘 구현 vertice(정점)는 3가지 분류로 나뉜다. tree vertice(T) : tree에 속해 있는 정점 fringe vertice (F) : tree에 포함되지 않으면서 연결되어있는 정점 unseen vertice (U) : 나머지 MST에서 T와 F의 정점 사이의 최소 가중치를 계속 갱신해주었던 것 대신에, 최단..

MST Spanning Tree : 그래프 내의 모든 정점을 포함하는 트리 우선 트리의 정의는 connected undirected acyclic graph (연결 비방향 비순환 그래프)이다. 모든 노드는 연결되어있으며, 방향성은 없고 순환이 존재하지 않는 그래프이다. 하나의 그래프가 주어졌을 때, 그래프 내에서 여러 트리를 찾을 수 있다. 그 중 특별하게 모든 정점을 포함하는 트리를 Spanning Tree라고 한다. 다르게 말하면 Spanning tree(신장 트리)는 그래프의 부분 그래프면서 간선의 수가 가장 적은(최소 연결) 그래프이다. 감이 안온다면 그림으로 살펴보자. 위의 그림과 같이 그래프가 주어졌을 때, 최소한의 간선을 사용하여 모든 정점을 포함하는 부분 그래프가 여러 개 존재한다. 이 부..

여행경로 문제 https://programmers.co.kr/learn/courses/30/lessons/43164 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합..