PYTHON
파이썬을 이용해서 순회 알고리즘을 구현해보자 ♻ (feat. DFS, BFS)
파이썬을 이용해서 순회 알고리즘을 구현해보자 ♻ (feat. DFS, BFS)
2019.02.08이전 포스트에서 이진 탐색 트리(Binary Search Tree)를 구현해보았습니다. 트리는 배열이나 스택, 큐등의 자료구조와는 달리 데이터를 직관적으로 살펴보기 어렵습니다. 따라서, 트리를 위한 별도의 순회 알고리즘이 필요합니다. 트리 순회 알고리즘트리 순회 알고리즘은 트리에 저장된 모든 값을 중복이나 빠짐없이 살펴볼 때 사용합니다. 이진 트리의 순회 방법 중 깊이 우선 순회 방법(Depth First Traversal, DFS)으로는 전위 순회(Pre-order Traversal), 정위 순회(In-order Traversal), 후위 순회(Post-order Traversal)가 있으며, 너비 우선 순회 방법(Breadth First Traversal)으로는 레벨 순회(Level-order Tra..
[프로그래머스] 124 나라의 숫자 / Python
[프로그래머스] 124 나라의 숫자 / Python
2019.02.08[프로그래머스] 124 나라의 숫자 / Python 문제 설명 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니 다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 10진법 124 나라 10진법 124 나라 1 1 6 14 2 2 7 21 3 4 8 22 4 11 9 24 5 12 10 41 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요. 제한사항 n은 500,000,000이하의 자연수 입니다. 😃 나의 풀이 def solution..
[프로그래머스] 콜라츠 추측 / Python
[프로그래머스] 콜라츠 추측 / Python
2019.02.08[프로그래머스] 콜라츠 추측 / Python 문제 설명 1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다. 1-1. 입력된 수가 짝수라면 2로 나눕니다. 1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다. 2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다. 예를 들어, 입력된 수가 6이라면 6→3→10→5→16→8→4→2→1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야하는지 반환하는 함수, solution을 완성해 주세요. 단, 작업을 500번을 반복해도 1이 되지 않는다면 –1을 반환해 주세요. 제한 사항 입력된 수, num은 1 이상..
파이썬을 이용해서 이진 탐색 트리 구현하기 🎄
파이썬을 이용해서 이진 탐색 트리 구현하기 🎄
2019.02.08이진 트리(Binary Tree)는 최대 두 개의 자식 노드를 가진느 트리 형태의 자료구조로, 단순히 값을 저장하는 용도보다는 효율적인 탐색 혹은 정렬을 위하여 사용됩니다. 이진 탐색 트리(Binary Search Tree)를 사용하여 주어진 값 혹은 이보다 작거나 큰 값들을 평균 O(logn)의 시간 복잡도로 찾을 수 있으며, 이진 트리의 한 종류인 힙(heap)을 사용한 힙 정렬(heap)은 O(nlogn)의 시간 복잡도를 가집니다. 이진 탐색 트리 구현 이진 탐색 트리(Binary Search Tree)는 이진 트리의 특수한 케이스 중 하나입니다. 이진 트리 중 모든 노드에 대해 왼쪽 자식 노드들의 값이 현재 노드 값보다 작거나 같으며, 오른쪽 자식 노드들의 값이 현재 노드의 값보다 크다는 조건을 ..
[프로그래머스] 🎮 길 찾기 게임 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
[프로그래머스] 🎮 길 찾기 게임 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
2019.02.08[프로그래머스] 🎮 길 찾기 게임 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT 문제 설명 전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다. 라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다. 그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀..
[Python] itertools를 이용한 조합
[Python] itertools를 이용한 조합
2019.02.07Python 내장 라이브러리인 itertools는 Python에서 제공하는 자신만의 반복자를 만드는 휼륭한 모듈입니다. 특정 배열에 대하여 순열이나 조합을 만들어 이를 이용하는 문제를 풀 때, 직접 구현해도 되지만, 이 itertools를 이용한다면 효율적으로 반복자를 구할 수 있습니다. product() import itertools itertools.product('ABCD', repeat=2) # 결과: AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD 인수: p, q, ... [ 반복 = 1 ] 결과: 중첩된 for loop에 해당하는 데카르트의 곱 permutations() import itertools itertools.permutations('ABCD', ..
[프로그래머스] 🐰 무지의 먹방 라이브 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
[프로그래머스] 🐰 무지의 먹방 라이브 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
2019.02.07[프로그래머스] 🐰 무지의 먹방 라이브 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT 문제 설명 무지의 먹방 라이브 * 효율성 테스트에 부분 점수가 있는 문제입니다. 평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다. 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다..
[프로그래머스] 🔑 후보키 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
[프로그래머스] 🔑 후보키 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
2019.02.06[프로그래머스] 🔑 후보키 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT 문제 설명 프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다. 그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다. 후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다. 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성..
[Python] Dictionary(사전) 자료형 : { k : v }의 sort(정렬)
[Python] Dictionary(사전) 자료형 : { k : v }의 sort(정렬)
2019.02.051. Key 값을 정렬 Python의 Dictionary 자료형은 { key: value } 쌍으로 값이 들어가 있다. Dictionary는 Default(기본) 정렬이 Key값을 기준으로 오름차순으로 Key 값을 정렬하는 것이다. fruits \= { 'apple': 2, 'banana' : 1, 'melon' : 0, 'pear' : 2, 'plum' : 1} sorted(fruits) # \['apple', 'banana', 'melon', 'pear', 'plum'\] sorted(fruits.keys()) # \['apple', 'b..
[프로그래머스] 😔 실패율 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
[프로그래머스] 😔 실패율 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
2019.02.05[프로그래머스] 😔 실패율 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT 문제 설명 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라. 실패율은 다음과 같이 정의한다. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레..
[프로그래머스] 🙋♂️ 오픈 채팅방 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
[프로그래머스] 🙋♂️ 오픈 채팅방 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT
2019.02.05🙋♂️ 오픈 채팅방 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT 문제 설명 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. [닉네임]님이 들어왔습니다. 채팅방에서 누군가 나가면 다음 메시지가 출력된다. [닉네임]님이 나갔습니다. 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경..
[프로그래머스] 🧶 네트워크 / python
[프로그래머스] 🧶 네트워크 / python
2019.02.05🧶 네트워크 - 깊이/너비 우선 탐색(DFS/BFS) / python 문제 설명네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.제한사항컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.각 컴퓨터는 0부터 n-1인 정수로 표현합니다.i..