본문 바로가기

Algorithm

 (77)
[프로그래머스] 코딩테스트 연습 - 점프와 순간 이동(Python) 코딩테스트 연습 - 점프와 순간 이동 [Summer/Winter Coding(~2018)] 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 풀이 문제를 풀고 나서 잠시의 기쁨 뒤에 다른 사람의 풀이를 보며 "아..." 했던 문제입니다ㅋㅋ 문제의 요점은 현재위치*2의 위치로 갈 수 있는 순간이동을 최대한 많이 활용하는 것이죠. 순간이동을 다르게 생각해본다면 반복적으로 n//2로 변환하여 중간이 되는 지점을 찾고 n이 홀수 일 때는 (n-1)//2으로 중간이 되는 지점을 찾아 해당 지점들을..
[프로그래머스] 코딩테스트 연습 - 가사 검색(Python) 코딩테스트 연습 - 가사 검색 [2020 KAKAO BLIND RECRUITMENT] 코딩테스트 연습 - 가사 검색 programmers.co.kr 풀이 개인적으로 쉽지 않은 문제였다고 생각합니다. 저는 이 문제를 풀기 전까지 Trie의 개념을 모르고 있었거든요ㅎㅎ 그래서 Trie를 사용하지 않고 선형 방법으로 구현했었는데 효율성 1~3번을 뚫기가 쉽지 않아 결국 Trie를 사용했습니다. Trie의 개념은 간단합니다. 하나의 string을 Tree형태로 저장해서 빠른 문자열 검색에 적합하도록 만들어진 자료구조입니다. Trie를 사용한다고 해도 문제를 풀기 위해서 생각해야 할 점이 하나 더 있습니다. 바로 "?"의 위치에 따라 (1) 접미사의 경우 (2) 접두사의 경우 (3) 전체가 "?"인 경우로 나뉘게..
[프로그래머스] 코딩테스트 연습 - [1차] 캐시(Python) 코딩테스트 연습 - [1차] 캐시 [2018 KAKAO BLIND RECRUITMENT] 풀이 캐시는 컴퓨터와 관련된 많은 분야에서 쓰이는 중요한 개념이죠. 캐시의 교체 알고리즘들 중 LRU(Least Recently Used), 가장 오래 쓰이지 않은 것을 빼고 새로운 것을 추가하는 방법을 구현하는 문제로 어렵지 않은 문제였던 것 같습니다ㅎㅎ Code def solution(cacheSize, cities): answer = 0 cache = [] if cacheSize==0: return len(cities)*5 for cityname in cities: city = cityname.lower() if city in cache:# Hit - [오래된 것 ~ 최근 사용]의 순서로 재배치 idx = ca..
[프로그래머스] 코딩테스트 연습 - 호텔 방 배정(Python) 코딩테스트 연습 - 호텔 방 배정 [2019 카카오 개발자 겨울 인턴십] 풀이 level 4의 문제였지만 천천히 생각해보면 어렵지 않게 풀 수 있는 문제였다고 생각됩니다. 하지만 저는 천천히 생각해서 어려운 길로 돌아갔습니다..ㅎㅎㅎ 문제의 중점은 k의 값이 엄청크니까 겹치는 방이 있을 때 얼마나 효율적으로 다음 방을 찾느냐겠죠. 제가 생각했던 방식은 dictionary를 사용해서 dict [방 번호] = 다음 방 번호의 형식으로 저장하는 것이었습니다. 풀이하는 과정에서 필요 이상으로 복잡하게 구현해서 코드가 길어졌지만 통과는 하더군요. 풀이 후에 다른 사람들의 풀이를 보며 제 코드에 불필요한 작업들이 많았구나를 느껴서 한 번 더 구현했습니다ㅎㅎ Code 1 from collections import d..
[프로그래머스] 코딩테스트 연습 - 무지의 먹방 라이브(Python) 코딩테스트 연습 - 무지의 먹방 라이브 [2019 KAKAO BLIND RECRUITMENT] 스킬 체크가 생겨서 해보고 이전엔 어떻게 풀었나 보러 왔는데 설명이 신기할 정도로 별로였네요.. 하하.. 풀이 효율성을 통과하기가 생각보다 쉽지 않은 문제였던 것 같습니다. 1. 처음 시도했던 방법은 역시 무지성 반복문이었습니다ㅎㅎ 무지성 반복문에서 혹시나 하고 사용했던 방법은 dictionary를 사용해 linked list처럼 음식에 대해 이전 인덱스, 다음 인덱스를 저장해서 0이 되는 음식을 지우기 편하게 한 것입니다. 2. 두 번째로는 가장 적은 양의 음식들이 먼저 사라지게 되다는 점에서 heapq를 생각했던 것 같습니다. 회전판의 N개의 음식이 있다고 가정했을 때, 1번 음식을 먹고 다음으로 1번 음식..
[프로그래머스] 코딩테스트 연습 - 이진 변환 반복하기(Python) 코딩테스트 연습 - 이진 변환 반복하기 [월간 코드 챌린지 시즌1] 풀이 간단한 문제였죠. 문제에서 원하는 과정을 전부 코드로 적어도 몇줄 안되네요ㅎㅎ Code def solution(s): answer = [0,0] while len(s) != 1: cnt = s.count('0') s = bin(len(s)-cnt)[2:] answer[0] += 1 answer[1] += cnt return answer 문제 설명 0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다. x의 모든 0을 제거합니다. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다. 예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "..
[프로그래머스] 코딩테스트 연습 - 합승 택시 요금(Python) 코딩테스트 연습 - 합승 택시 요금 [2021 KAKAO BLIND RECRUITMENT] 풀이 문제의 키워드를 꼽자면 Graph와 최소금액이 있을 것 같네요. 이 두개의 키워드를 통해 문제의 풀이 방법이 알 수 있으니까요. 저는 graph의 최소금액의 경로를 찾기 위해 다익스트라 알고리즘을 사용하였습니다. graph의 최소경로를 알 수 있다면 풀이는 간단해집니다. 합승 지점을 옮기며 [합승 요금 + A까지의 요금 + B까지의 요금]을 계산해 가장 작은 합승 요금을 반환하면 문제가 해결됩니다. Code from collections import defaultdict import heapq def solution(n, s, a, b, fares): answer = float('inf') mdict = de..
[프로그래머스] 코딩테스트 연습 - 경주로 건설(Python) 코딩테스트 연습 - 경주로 건설 [2020 카카오 인턴십] 풀이 문제를 보고 처음 들었던 생각은 BFS로 모든 경로를 탐색하고 최소 비용으로 도착한 경우를 찾으면 될 거라고 생각했습니다. 이러한 방식으로 풀이를 하였더니 테스트 케이스 14번과 24번를 통과하지 못하더라고요ㅎㅎ 그래서 한참을 고민하다가 다른 분들이 올려주신 테스트 케이스를 보며 해결했습니다. 그중에서 중요했던 케이스는 [[0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 1, 0, 0], [1, 0, 0, 0, 1], [0, 1, 1, 0, 0]] 입니다. start 100 (1) 200 (2) 300 (3) 400 (4) 100 (1) 1 1 1 1000 (5) 200 (2) 800 (3) 1 1700 (7) 110..

티스토리툴바