분류 전체보기

오랜만에 백준을 풀었고, 오랜만에 시간 초과 늪에 빠졌다. 최대한 시간을 줄여 파이썬까지 통과해보고 싶었지만 아직 내실력에서는 Pypy통과가 최선이었다. 문제를 간략히 설명하자면, 존이 N개의 동영상 중 N-1개의 동영상 쌍을 만들어서 유사도를 구해놓았다. 동영상 쌍을 만들 때 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 만들었을 때, Q개의 질문(v번의 동영상과 유사도가 k이상인 동영상의 개수)의 답을 구하는 문제이다. 문제에서 가장 큰 힌트부분은 한 동영상에서 한 동영상으로 가는 경로가 반드시 하나인 점. 즉, 방향이 존재하지 않고 사이클이 없는 그래프인 트리구조로 만들 수 있다는 점이다. 나는 위 점에서 힌트를 얻어 딕셔너리를 활용하여 트리를 만들었고, 이를 이용한 BFS탐색..

사실 이 문제는 어렵지는 않지만, 제한사항과 문제 카테고리가 없었으면 좀 헤매었을 것 같다. 왜냐하면 완전 탐색 문제만 보면 DP문제가 아닌가? 하는 겁이 나기 때문이다. 하지만, 위에 말한것 처럼 제한사항에서 주어지는 숫자 개수가 20개 이하인걸 확인한다면, 쉽게 풀 수 있을 것이다. 이문제는 숫자들의 배열과 타겟넘버가 주어질 때, 숫자들의 배열의 합과 차로 타깃 넘버를 만들 수 있는 방법의 개수를 묻는 문제이다. 더하거나 뺄 수 있다는 부분에서 부분집합(itertools)를 활용하기에는 조금 어려움이 있을 것 같아 나는 완전 검색(DFS) 방식으로 문제를 풀었다. 원하는 타겟넘버가 되는 조건을 종료 조건으로 그전까지는 배열을 진행하면서 합과 차를 각각 구해보는 전형적인 완전 탐색 풀이법을 사용해 보았..

달팽이 문제는 많이 기억에 남는 문제이다. 왜냐하면 싸피를 시작하며 처음 알고리즘을 알게 되었고, 알고리즘 스터디에서 문제를 풀 때, 나에게 절망을 준 문제 중 하나였기 때문이다. 그때 다른 분들이 조건을 찾아서 풀거나 delta기법을 이용하여 문제를 풀 때, 어떻게 그렇게 구현하지 생각하며 부러워했던 기억이 난다. 그래도 이제는 나도 그때 달팽이 문제보다 조금 어려워진 문제를 구현으로 바로 풀어내는 것을 보니 성장했다는 것이 체감되는 아주 기분 좋은 문제였다. 문제는 아마 알고리즘 문제를 풀어 보는 모든 사람들이 익숙한 문제일 것이다. 이문제가 다른점은 달팽이가 삼각형 모양으로 움직인다는 것이다. 문제를 보면 1번위치에서 출발해서 왼쪽 아래 꼭짓점, 오른쪽 아래 꼭짓점, 다시 위쪽 꼭짓점 방향으로 달팽..

사실 이 문제는 자신 있게 풀었다가 완전히 오답이 나서 내 접근 자체가 틀렸단 걸 느껴 질문하기를 통해 힌트를 보고 풀었다. 질문하기를 보니 나처럼 접근했다가 답을 틀린 사람이 많았던 것 같다. 우선 문제를 간단히 설명하자면 다단계 조직원들의 수입을 리스트로 반환하는 문제이다. 이런 식으로 다단계 조직원들의 구조가 이루어져 있을 때, 자신이 개당 100원짜리의 칫솔을 판매하거나 자신의 자식이(추천받은 사람) 수익을 얻어 자신이 수익을 받는다면 90%를 내가 가지고 10%를 자신의 부모(추천인)에게 보내주어야 한다. 여기서 나는 두가지 실수를 하였다. 1. 모든 자식노드의 수입이 정해진 후 자신의 수입을 정한다(트리의 후위 순회) -> 틀린 이유 : 수입을 받을 때마다 부모에게 보내주어야 함(10%를 보내..

이 문제는 문제 설명을 길지만 내용은 간단한 문제였다. 요약하자면 주차장에 입출고한 차량의 시간 / 차번호 / 입출고 여부 가 주어질 때, 각 차량 당 하루 주차요금을 계산하는 문제이다. 문제를 보면서 고민했던점은 1. 시간 계산을 어떤 식으로 할 것인가 2. 데이터를 어떤 컨테이너에 넣어서 요금계산을 할 것인가였다. 우선 나는 문제의 세부조건에서 '입고한 후, 출고 기록이 없다면 23:59에 출고된 것으로 한다' 부분과 TC에서 '입고-출고를 했던 차량이 다시 입고하는 경우'를 보고 아이디어를 떠올렸다. 1. 시간 계산 아이디어 우선 모든 차들은 max_time(23:59)을 쓴다고 가정하고, 입고되면 입고 시간만큼 빼고 출고되면 출고시간부터 23:59시까지 시간을 뺐다. 이렇게 하면 별다른 구현 없이..

프로그래머스 문제를 풀고 다른 사람들의 풀이를 보다가 collections의 Counter를 사용하여 딕셔너리를 이용해 푸는 문제를 두문 장정도로 깔끔하게 풀어내는 것을 보고 저 라이브러리는 뭘까 하며 알아보았다. 1. collections 1.1 collections collections모듈은 파이썬에서 일반적으로 제공되고 있는 dict, list, set, tuple의 대안을 제공해주는 특별한 데이터 컨테이너들의 집합이다. 큐를 이용하는 구현을 할 때 사용하는 deque 역시 collections 모듈에서 사용할 수 있다. collections 모듈에는 활용도 높아 보이는 container들이 많이 보였는데 오늘은 그중 Counter에 대해 공부해 보았다. 2. Counter 2.1 Counter C..

이 문제는 문제 설명은 길지만 짧게 설명하자면 A선수의 번호와 B선수의 번호가 주어졌을 때, 몇 번 만의 두 선수가 겨루게 될지 묻는 문제이다. 즉 총 8명의 선수가 있을 때, 현재 A의 번호는 4이고 B의 번호는 7이므로 A의 대진번호는대진 번호는 2, B의 대진 번호는 4가 된다. 이 문제의 조건인, A와 B는 항상 이기기 때문에 그다음 A의 대진 번호는 1, A의 대진 번호는 2가 된다. 다음 경기도 이길 것이고 그다음 A의대 진번호는 1, B의 대진 번호도 1로 같게 되므로 정답 3이 나오게 된다. 문제만 이해한다면 구현자체도 어렵지 않기 때문에 금방 풀 수 있는 문제였던 것 같다. 결국 자신의 번호(대진번호)가 1,2이면 그다음 대진 번호는 1, 3,4이면 대진 번호 2, 5,6이면 3 이 될 ..

SWEA D4문제를 추천순으로 풀고 있는데 어제오늘은 좀 쉬운 문제를 풀게 됐다. (사실 요즘 바빠서 알고리즘 풀 수 있을까? 했는데 다행이다.) 이 문제는 제목이 길찾기이지만, 사실 미로 찾기, 그래프 탐색하라는 문제이다. 제한시간도 30초이고 최대 방문지 점도 100개이기 때문에 BFS로 풀지, DFS 풀지 고민 없이 풀고 싶은 방식으로 풀어도 해결할 수 있을 것이다. 나는 처음보자마자 BFS가 떠올랐기 때문에, BFS로 풀어보았다. 우선 100개의 방문 체크를 할 리스트를 만들고 인접 행렬을 만들었다. 이 문제는 "출발 도착 출발 도착 출발 도착..." 이런식으로 Input값을 주기 때문에 한 번에 다 받은 다음에 두 개씩 끊어서 인접 행렬에 넣어 줄 필요가 있었다. 변수를 받고 도착지(99)에 도..