프로그래머스

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

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

이 문제는 문제 자체가 어렵다기보다는 손 코딩을 통해 어떻게 풀어나갈지 정하고 풀기 시작하지 않는다면, 문제를 풀면서 코드가 복잡해지는 문제 같았다. 나도 손 코딩부터 하지 않고 하여 코드가 뒤죽박죽이 됐었다. 이 문제는 설명이 매우 길지만 요약하자면 주어진 두개의 문자열을 각각 문자로만 이루어진 두 개의 단어로 쪼개어 다중집합으로 저장한 후, 자카드 유사도를 구하는 문제이다. 문제를 읽으면서 다중집합과 자카드유사도를 보며 처음 보는 개념에 당황했지만, 개념을 이해하기보다는 문제가 시키는 대로 풀려고 노력했다. 다중집합은 중복을 허용하는 집합이었고 그렇기 때문에 교집합과 합집합을 구하는 방식이 일반 집합과 달랐다. 나는 문제를 풀기위해 총 세 가지 부분으로 나누어 풀었다. Q1. 문자열을 두글자씩 모두 ..

이번 문제는 문제 카테고리가 깊이/너비 우선 탐색이기 때문에 문제를 풀 때 어느 정도 힌트를 얻을 수 있었다. 이 문제는 항공권 정보가 담긴 (출발지 , 목적지) 티켓들이 적혀있다. 이 티켓들로 모든 도시들을 방문하고자 할 때 경로를 반환해야 한다. 추가 제약사항으로는 모든 도시를 방문하는 경우의 수가 두 개 이상 있을 때, 알파벳순으로 가장 앞의 값을 리턴해야 한다는 점이 있다. 내가 이문제를 풀면서 생각한 두 가지 키포인트는 1. 주어진 항공권은 모두 사용해야 한다 + 이 문제는 시간 제약이 없다 2. 경로를 return 해야 한다. 이다 첫 번째로 주어진 항공권을 모두 사용해야 한다는 점에서 나는 시간단축을위해 해쉬자료형이나, 방문기록을 위해 인접행렬을 만들 필요없이 항공권의 인덱스와 갯수로 방문체..

프로그래머스의 불량 사용자 문제를 풀어보았다. 지난번에 풀다가 실패했던 링크 점수 이후로 정규화에 대해 공부해 보았기 때문에 이 문제를 봤을 때, 정규화로 풀어볼 수 있겠다는 생각이 들었다. 이 문제는 모든 아이디가 공개되어 있는 이벤트 응모자 아이디와 아이디가 일부분 '*'로 가려져 있는 불량사용자 아이디를 제공한다. 이 정보를 통해 이벤트 응모자 아이디 중 불량 아이디를 가려내고자 할 때, 불량 아이디로 가려내질 응모자 아이디의 경우의 수를 묻는다. 이렇게 두 정보가 제공됐을 때, 불량사용자로 인해 제재받는 경우의 수는 [frodo, abc123], [fradi, abc123] 이렇게 두 가지의 경우가 있다. 추가적으로 고려해야 할 제약사항은 불량사용자 아이디는 무조건 하나의 응모자 아이디를 가리키고..

이 문제는 무지와 어피치가 출발점 S에서 택시를 타고 가는데 둘이 각자의 집으로 갈 때 최소 택시요금을 구하는 문제이다. 여기서 둘이 공통된 방향으로 택시를 타고 갈 때는 합승이 가능하다는 추가 조건이 있다. 이 부분까지 읽었을 때 다행이 내 머릿속에 바로 다익스트라가 떠올랐다. 다익스트라 알고리즘이란 그래프 경로 간에 가중치가 있는 경우, 한 꼭짓점에서 다른 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 나는 이 문제를 보고, 각 목표점(꼭짓점)과 그 사이를 이동할 때 택시요금(가중치)의 최단 택시요금을 구하는 점에서 다익스트라로 충분히 구현 가능하다고 생각했다. 하지만 이 문제를 풀기 위해서 추가로 고민했던 점이 있다. 1. 이 문제는 효율성 테스트도 점수가 있다. 시간/공간 제약을 정확히 명시해주지는..

알고리즘 스터디를 준비하며 풀게 된 문제이다. 물론 어려운 문제였지만 이때까지 완전 검색과 DFS를 풀면서 많이 봤던 유형이었기 때문에 어떻게 풀지 비교적 쉽게 방향을 잡을 수 있었다. 문제를 간략히 설명하자면, 배열이 주어졌을 때, 그 배열을 정사각형으로 나누고, 그 정사각형이 모두 같은 값이면 하나로 압축할 수 있고 이렇게 압축했을 때 배열의 최종적으로 남는 0의 개수와 1의 개수를 출력하는 문제이다. 이 문제에서 제공하는 그림을 본다면, 가장 왼쪽 사각형처럼 초기배열 상태에서는 모든 수가 같지 않기 때문에 2^(1/2) 배수로 정사각형을 나눠야 하고, 그렇게 나누어진 게 두 번째 사각형이다. 두 번째 사각형에서는 1 사분면의 값이 모두 같아지기 때문에 0으로 압축할 수 있다. 이 과정은 정사각형의 ..