본문 바로가기

Algorithm

 (77)
[프로그래머스] 코딩테스트 연습 - 배달 (Python) 코딩테스트 연습 - 배달 [Summer/Winter Coding(~2018)] 풀이 해당 문제에서 중요한 점은 탐색을 할 때 방문을 했느냐 안 했느냐의 문제가 아니라 가장 적은 시간을 통해왔느냐 라는 점인 것 같습니다. 예를 들어 K가 5일 때 6시간으로 A를 방문했었지만 다른 경로를 통해 4시간으로 방문할 경우도 있으니까요. Code from collections import defaultdict def solution(N, road, K): answer, mydict = {1:0}, defaultdict(set) for st, end, cost in road: mydict[st].add((end, cost)) mydict[end].add((st, cost)) def dfs(curr, total_c):..
[프로그래머스] 코딩테스트 연습 - [1차] 뉴스 클러스터링 코딩테스트 연습 - [1차] 뉴스 클러스터링 [2018 KAKAO BLIND RECRUITMENT] 풀이 문제는 집합의 IoU(Intersection of Union)을 구하는 문제였습니다. 문제를 풀고나서 다른 분들의 풀이를 보았는데 Intersection(교집합)과 Union(합집합)을 구하는 과정에 비트 연산자 &와 | 를 쓰셨던 분들이 계시더라고요. 다중집합을 사용하는 문제였으니 Counter의 value값을 사용하면 되지만 Counter에 &와 |를 사용한다는 생각을 못해본 저로써는 참 충격적인 풀이가 아닐 수 없었습니다... 사용법을 간단히 설명해보자면 &연산은 1001(9) & 0001(1) = 0001(1)처럼 작은 값이 나오게 되는 것처럼 Counter에 같은 key의 value 중 작은..
[프로그래머스] 코딩테스트 연습 - 행렬 테두리 회전하기 코딩테스트 연습 - 행렬 테두리 회전하기 [2021 Dev-Matching: 웹 백엔드 개발(상반기)] 풀이 해당 문제는 특별한 알고리즘을 적용시키는 것보다는 구현에 집중된 문제였던 것 같습니다. 범위만큼 회전시키고 그중에서 최솟값을 찾아 answer에 넣으면 되니까요. 하지만 저는 테스트 케이스 3번부터 쭉 틀려서 한참을 헤맸네요...ㅎㅎ 회전이나 최솟값을 찾는 로직을 아무리 쳐다봐도 이상할 게 없었는데 왜 계속 틀리는지 이해 안 되더라고요ㅠㅠ 이유는 생각보다 간단한 곳에 있었습니다! 처음 배열의 값을 초기화할 때에 잘못된 값으로 초기화한 것이었죠.. 문제 설명에서 주어지는 입출력 예 중에서 직사각형 형태의 예제는 테두리만 돌리고 최솟값이 1이니 아무런 의심이 없이 통과하겠거니 싶었는데 그게 아니었고 ..
[프로그래머스] 코딩테스트 연습 - 수식 최대화 코딩테스트 연습 - 수식 최대화 [2020 카카오 인턴십] 문제 설명은 아래에 있습니다 :) 이전 글까지는 문제 설명을 먼저 적고 code를 맨 밑에 적었는데 생각해보니 알고리즘 문제에 대한 글을 찾아보실 분이라면 이미 문제를 알고 계실 것 같아서 풀이에 대해 먼저 적어봅니다ㅎㅎ 자신의 생각 문제를 풀면서 가장 핵심적인 부분은 permutations과 eval(문자열로 되어있는 식을 계산해주는 함수) 이였던 것 같네요. 사실 문제를 처음봤을 때는 '우선순위'라는 말에 꽂혀서 좀 헤맸는데 찬찬히 생각해보다 결국은 모든 연산자 우선순위에 대해 확인해 봐야되는 점이 곧 permutations을 확인해보면 되겠다라는 생각이 들어서 문제를 풀기 시작했습니다ㅎㅎ.. Code from itertools import ..
[프로그래머스] 코딩테스트 연습 - 게임 맵 최단거리 코딩테스트 연습 - 게임 맵 최단거리 [찾아라 프로그래밍 마에스터] 문제 설명 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진..
[프로그래머스] 코딩테스트 연습 - 추석트래픽 코딩테스트 연습 - 추석 트래픽 [2018 KAKAO BLIND RECRUITMENT] 문제 설명 이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리 초) 간 처리하는 요청의 최대 개수를 의미한다. 입력 형식 solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000) 개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답 완료 시간S와 처리시간 T가 공백으로 구분되어 있다. 응답 완료 시간S는 작년 ..
[프로그래머스] 코딩테스트 연습 - 오픈채팅방 코딩 테스트 연습 - 오픈 채팅방 [2019 KAKAO BLIND RECRUITMENT] 문제 설명 카카오톡 오픈 채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김 크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리 자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. "[닉네임]님이 들어왔습니다." 채팅방에서 누군가 나가면 다음 메시지가 출력된다. "[닉네임]님이 나갔습니다." 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경한다. 닉네임을 ..
[프로그래머스] 코딩테스트 연습 - 문자열 압축 코딩 테스트 연습 - 멀쩡한 사각형 [2020 KAKAO BLIND RECRUITMENT] 문제 설명 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2 a 2 ba3 c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은..

티스토리툴바