Algorithm
[프로그래머스] 🤳 방금 그 곡 - [3차] 2018 카카오 블라인드 채용 / Python
[프로그래머스] 🤳 방금 그 곡 - [3차] 2018 카카오 블라인드 채용 / Python
2019.02.04🤳 방금 그 곡 - [3차] 2018 카카오 블라인드 채용 / Python라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 ‘방금그곡’ 서비스를 이용하곤 한다. 방금그곡에서는 TV, 라디오 등에서 나온 음악에 관해 제목 등의 정보를 제공하는 서비스이다. 네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다. 그런데 라디오 방송에서는 한 음악을 반복해서 재생할 때도 있어서 네오가 기억하고 있는 멜로디는 음악 끝부분과 처음 부분이 이어서 재생된 멜로디일 수도 있다. 반대로, 한 음악을 중간에 끊을 경우 원본 음악에는 네오가 기억한 멜로디가 들어있다 해도 그 곡이 네오가 들은 곡이 아닐 수도 있다. 그렇기 때문에 네오는 기..
[프로그래머스] 😎 자동완성 - [3차] 2018 카카오 블라인드 채용 / Python
[프로그래머스] 😎 자동완성 - [3차] 2018 카카오 블라인드 채용 / Python
2019.02.03😎 자동완성 - [3차] 2018 카카오 블라인드 채용문제 설명포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.예를 들어, 학습된 단어들이 아래와 같을 때gogoneguildgo를 찾을 때 go를 모두 입력해야 한다.gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go..
[프로그래머스] 📁 파일명 정렬 - [3차] 2018 카카오 블라인드 채용 / 파이썬 / python / KAKAO BLIND RECRUITMENT
[프로그래머스] 📁 파일명 정렬 - [3차] 2018 카카오 블라인드 채용 / 파이썬 / python / KAKAO BLIND RECRUITMENT
2019.02.02📁 파일명 정렬 - [3차] 2018 카카오 블라인드 채용 / KAKAO BLIND RECRUITMENT 문제 설명 파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램의 과거 버전을 모두 담고 있어, 이름 순으로 정렬된 파일 목록은 보기가 불편했다. 파일을 이름 순으로 정렬하면 나중에 만들어진 ver-10.zip이 ver-9.zip보다 먼저 표시되기 때문이다. 버전 번호 외에도 숫자가 포함된 파일 목록은 여러 면에서 관리하기 불편했다. 예컨대 파일 목록이 [img12.png, img10.png, img2.png, img1.png]일 경우, 일반적인 정렬은 [img1.png,..
[프로그래머스] 💾 압축 - [3차] 2018 카카오 블라인드 채용 / 파이썬
[프로그래머스] 💾 압축 - [3차] 2018 카카오 블라인드 채용 / 파이썬
2019.02.02💾 압축 - [3차] 2018 카카오 블라인드 채용 / 파이썬 문제 설명 신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다. 어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다. LZW 압축은 다음 과정을 거친다. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다. w에 해당하는 ..
[프로그래머스] 📊 추석 트래픽 - [1차] 2018 카카오 블라인드 채용 / 파이썬 / python / KAKAO BLIND RECRUITMENT
[프로그래머스] 📊 추석 트래픽 - [1차] 2018 카카오 블라인드 채용 / 파이썬 / python / KAKAO BLIND RECRUITMENT
2019.02.01[프로그래머스] 📊 추석 트래픽 - [1차] 2018 카카오 블라인드 채용 / 파이썬 / python / KAKAO BLIND RECRUITMENT 📊 추석 트래픽 문제설명 이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다. 입력 형식 solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S..
[알고리즘] 🤷♂️ 백트래킹 알고리즘 / Backtracking Algorithm
[알고리즘] 🤷♂️ 백트래킹 알고리즘 / Backtracking Algorithm
2019.02.01🤷♂️ 백트래킹(Backtracking) 알고리즘모든 경우의 수를 전부 고려하는 알고리즘으로 트리형 자료구조에 적합하며 계속해서 답이 될 수 있는 후보 노드들을 만들어내고, 해당 후보로는 적절한 답을 얻을 수 없는 후보를 철회("Backtracks")하면서 문제를 해결하는 알고리즘이다. 가장 유명한 예제로는 서로를 공격할 수 없는 8개의 퀸의 위치 배열을 찾는 N-queens 문제가 있다. N-queens 문제를 백트래킹 알고리즘으로 접근하면, 첫 행부터 아래로 내려가면서, 이미 존재하는 퀸에 가로 세로 대각선에 존재하는 후보는 철회하는 방식으로 풀 수 있다. 백트래킹 알고리즘은 '부분적 후보 해결책'의 개념을 확인하는 문제와 그것이 유효한 해결책으로 완성될 수 있는 지의 여부를 상대적으로 빠르게 시험..
[BOJ] 👸 N-Queens / 파이썬
[BOJ] 👸 N-Queens / 파이썬
2019.02.01👸 N-Queens 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 😃 나의 풀이 def nqueen(sol, n): global count if len(sol) == n: # 정답 배열(sol)의 길이가 n과 같아지면, count 증가 count += 1 return 0 candidate = list(range(n)) # 0부터 n-1까지를 후보 배열로 만든다. for i in range(len(sol)): if sol[i] in candid..
[프로그래머스] 🚍 셔틀버스 - [1차] 2018 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
[프로그래머스] 🚍 셔틀버스 - [1차] 2018 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
2019.02.01🚍 셔틀버스 - [1차] 2018 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT 문제 설명 카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다. 이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자. 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다. 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다. 일찍 나와서 ..
[프로그래머스] 이상한 문자 만들기 / 파이썬
[프로그래머스] 이상한 문자 만들기 / 파이썬
2019.01.31🤔 이상한 문자 만들기 문제 설명 문자열 s는 한 개 이상의 단어로 구성되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 리턴하는 함수, solution을 완성하세요. 제한 사항 문자열 전체의 짝/홀수 인덱스가 아니라, 단어(공백을 기준)별로 짝/홀수 인덱스를 판단해야합니다. 😃 나의 풀이 def solution(s): answer = '' lst = s.split(' ') for idx, string in enumerate(lst): for i in range(len(string)): if i%2 == 0: string = string[:i] + string[i].upper(..
[프로그래머스] 👨🎓 N으로 표현 / 파이썬
[프로그래머스] 👨🎓 N으로 표현 / 파이썬
2019.01.31N으로 표현 문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 😃 나의 풀이 dic = {0:1..
[프로그래머스] 🔐 시저 암호 / 파이썬
[프로그래머스] 🔐 시저 암호 / 파이썬
2019.01.31🔐 시저 암호어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다. 예를 들어 AB는 1만큼 밀면 BC가 되고, 3만큼 밀면 DE가 됩니다. z는 1만큼 밀면 a가 됩니다. 문자열 s와 거리 n을 입력받아 s를 n만큼 민 암호문을 만드는 함수, solution을 완성해 보세요.제한 조건공백은 아무리 밀어도 공백입니다.s는 알파벳 소문자, 대문자, 공백으로만 이루어져 있습니다.s의 길이는 8000이하입니다.n은 1 이상, 25이하인 자연수입니다.😃 나의 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 def solution(s, n): upper = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' lower = upper.lower() f..
Q. 정렬 알고리즘에 대해 설명해주세요.
Q. 정렬 알고리즘에 대해 설명해주세요.
2018.12.22Q. 정렬 알고리즘에 대해 설명해주세요. Goal 정렬 알고리즘의 개념을 설명할 수 있다. 정렬 알고리즘의 종류에 대해 설명할 수 있다. 정렬 알고리즘의 개념 정렬 알고리즘이란 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 얼마나 효과적으로 해결하는 지가 정렬 알고리즘의 핵심 정렬 알고리즘이 중요한 이유 데이터가 정렬되어 있으면 이진탐색이라는 강력한 알고리즘을 사용할 수 있다. 대표적인 정렬의 종류 실제 응용에서는 상황에 따라 두 가지 이상의 정렬 방법을 사용하는 경우가 많다. 정렬 대상이 특정 크기 이하로 단편화될 때까지는 퀵 정렬을 쓰다가, 삽입정렬을 쓴다던가, 특정 횟수 이상 재귀호출이 발생하면 O(nlgn)의 힙 정렬을 사용한다. 버블정렬(Bubble Sort) 방법 1번째와 2 번째 ..