본문 바로가기

분류 전체보기

 (88)
[프로그래머스] 코딩테스트 연습 - 셔틀버스(Python) 코딩테스트 연습 - 셔틀버스 [2018 KAKAO BLIND RECRUITMENT] 풀이 저는 문제를 이해하는 데도 생각보다 오래 걸렸던 것 같네요. 문제를 이해하고 보니 입출력 예제 2번은 보면 정답이 왜 "09:10"이 아니고 "09:09"인가 싶었습니다. 이유는 "08:00"시에 온 크루는 "09:00"시 버스를 타고 갔고 다음 버스 시간은 "09:10"시인데 이때 탑승할 수 있는 사람이 "09:09"와 "09:10" 두 명이고 다음 버스는 없으므로 셔틀버스를 타기 위해선 "09:10"보다 빠른 "09:09"분이 답이었던 것이죠. 처음 문제를 보고 생각했던 풀이 방식은 defaultdict(list)를 이용하여 각 시간별로 탑승자를 저장하는 방법이였는데 달리 생각해보니 결국 timetable을 so..
[프로그래머스] 코딩테스트 연습 - 불량 사용자(Python) 코딩테스트 연습 - 불량 사용자 [2019 카카오 개발자 겨울 인턴십] 풀이 저는 itertools의 product를 이용했는데 아마 효율성 점수가 있었다면 다른 방법을 찾았어야 할 것 같네요. product를 사용하면 카타시안곱을 하는 것인데 카다시안 곱은 결과가 굉장히 많을 수도 있어 굉장히 큰 테스트 케이스가 주어진다면 아마 효율성에서 시간 초과를 겪었을 것 같네요. Code from itertools import product def solution(user_id, banned_id): ban_len = len(banned_id) answer, ban_list = [], [[] for i in range(ban_len)] for idx, ban in enumerate(banned_id): # 각 ..
[프로그래머스] 코딩테스트 연습 - 보석 쇼핑(Python) 코딩테스트 연습 - 보석 쇼핑 [2020 카카오 인턴십] 풀이 처음 문제를 풀 때는 리스트의 특정 범위를 set을 변환해서 비교하는 방식으로 풀었었는데 정확성은 모두 통과하지만 효율성에서 모두 시간 초과되더라고요. 그래서 다른 분들의 풀이를 보며 두 개의 포인터를 놓아 end 포인터를 증가시키다가 조건을 만족시키면 start 포인터를 옮기며 최소 길이를 찾는 방식을 사용하여 문제를 풀었습니다. Code def solution(gems): gemset = set(gems) if len(gemset) == 1: return [1, 1] # gem의 종류가 하나일 때 answer, mydict = [0, len(gems)], dict() s, e = 0, 0 while e < len(gems): if gems..
[논문리뷰] PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation [Introduction] 일반적으로 Image는 행렬로 표현된 pixel값을 사용하여 표현합니다. 여기서 기하학적인 정보는 행렬의 좌표 (x, y)에 해당하죠. 반면 3D data는 depth정보를 포함하여 (x, y, z)좌표를 사용하여 rgb값을 표현하며 Image처럼 행렬이 아닌 Point들의 집합으로 표현됩니다. 정리하면 Image는 Regular format으로 Point들의 집합은 Irregular format으로 표현되는 것이니 Point는 Image와 달리 특정한 순서가 없고 Grouping되어 있지도 않죠. 그로 인해 발생하는 문제점들이 있기에 Point들을 아래와 같이 Mesh(polygon) 또는 Voxel(volume+pixel)의 형태로 표현하여 사용합니다. 위처럼 Point c..
[프로그래머스] 코딩테스트 연습 - 영어 끝말잇기(Python) 코딩테스트 연습 - 영어 끝말잇기 [Summer/Winter Coding(~2018)] 풀이 지난번 스킬트리문제를 풀며 새로 배웠던 for...else...를 처음으로 사용해봤는데 꽤 편한것 같네요ㅎㅎ Code def solution(n, words): for i in range(1, len(words)): if words[i-1][-1] != words[i][0] or words[i] in words[:i]: return [(i%n)+1, (i//n)+1] else: return [0, 0] 문제 설명 1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다. 마지막 사람이 ..
[프로그래머스] 코딩테스트 연습 - 스킬트리(Python) 코딩테스트 연습 - 스킬트리 [Summer/Winter Coding(~2018)] 풀이 스킬트리ㅎㅎ RPG게임을 좋아하는 사람이라면 문제이름부터 참 친숙할 것 같네요ㅋㅋ 난이도가 높지않아 금방풀었지만 다른분들의 풀이를 보며 새로 배운점이 있다면 python에 for...else...문이 있다는 점이였습니다. for문에서 어떠한 조건을 확인하기 위해 보통 flag를 두어 사용하는 것이 보편적인데 for...else....는 flag를 대신해서 for문이 break문으로 끝나지 않고 정상적으로 끝난경우 else문장을 실행해주는 것이죠. Code def solution(skill, skill_trees): answer = 0 for skill_t in skill_trees: flag, index = 0, 0 ..
[프로그래머스] 코딩테스트 연습 - 괄호 회전하기(Python) 코딩테스트 연습 - 괄호 회전하기 [월간 코드 챌린지 시즌2] 풀이 제 풀이과정에서 중요했던 점은 stack이었습니다. 괄호의 종류가 다르니 괄호 별로 비교를 해주기 위해서 stack을 사용했습니다. 정석적인 풀이와 다른점이 있다면 if문을 많이 쓰기 싫어서 괄호에 해당하는 숫자를 정하고 숫자를 stack에 넣은 점이 있겠네요ㅎㅎ.. Code def solution(s): answer, rotate = 0, len(s) for d in range(rotate): parenthesis, stack, total = s[d:]+s[:d], [], 0 for i, pt in enumerate(parenthesis): if pt in ['[', '{', '(']: idx = ['[', '{', '('].index..
[프로그래머스] 코딩테스트 연습 - 순위 검색(Python) 코딩테스트 연습 - 순위 검색 [2021 KAKAO BLIND RECRUITMENT] 풀이 참.. 효율성에서 많은 시간을 보냈던 문제입니다... 그리고 효율성문제를 해결할 수 있도록 해준 방법은 바로 이분탐색입니다. 처음에는 dictionary에 점수들을 list형태로 정렬하여 저장했고 list를 순차탐색해서 점수 조건을 만족하는 개수을 구하는 방법으로 구현했습니다. 순차탐색을 사용한다면 최악의 경우 dict['----']에 50,000개의 점수들이 있게되고 100,000개의 query가 모두 '- and - and - and - 500' 이라면 50,000 * 100,000번의 비교가 필요하게 되죠. 그렇기에 O(n)인 순차탐색보다 O(logn)인 이분탐색의 방식을 사용하면 성능이 향상될 것입니다. C..

티스토리툴바