분류 전체보기

이 문제는 다른 D4문제보다는 쉬웠던 것 같다. 처음에는 D4를 보고 DP로 풀어야 하나 생각했지만 N(검증 값의 길이)가 최대 20인 것을 보고 Itertools 라이브러리를 사용하면 풀 수 있지 않을까? 생각했다. 문제를 간략히 설명하자면 점원들이 선반의 물체만 한 탑을 쌓는데(점원들의 키의 합) 선반의 물체보다 높지만 가장 낮은 탑을 쌓는 경우 선반 높이와 점원들의 키의 차이를 구하는 문제이다. 문제를 살짝 봤을 때 DP로 풀어야하는 문제인가 싶었지만 위에서 말했듯이 점원들의 수가 최대 20명이었기 때문에 부분집합으로 풀 수 있었고, 더하여 집합을 만드는데 조건도 없었기 때문에 라이브러리를 사용할 수 있었다. 이를 코드로 나타내면 이렇게 나타낼 수 있다. 이번문제는 어떻게 푸는 문제인지 확실히 감잡..

이 문제는 인도네시아의 섬들을 모두 연결하는데 환경부담금이 가장 적게 나오도록 연결하는 방법을 묻는 문제이다. 즉 가중치(환경부담금)를 이용한 최소 신장 트리를 구하는 문제이다. 조금 더 쉽게 말하자면 부담금이 가장 적게 나오는 방법으로 모든 섬을 한점 잇기 하는 방법을 찾는 방법이다. 이 문제에서는 X좌표와 Y좌표, 환경부담세율을 Input값으로 각 거리에 비례하는 환경부담금이 최소가 되는 최소 신장 트리를 구하는 문제이다. 문제에 대한 설명은 이 정도로 하고 내가 이문제를 풀기 위해 사용한 Prim알고리즘에 대해 잠깐 알아보고 코드를 정리해 보겠다. MST(Minimum Spanning Tree)를 구하는 알고리즘 중 대표적으로 Prim과 Kruskal 알고리즘이 있는데, 두개다 자신이 없었던 나는 ..

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

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

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

프로그래머스 문제 중 매칭 점수 (42893)을 풀면서 내가 알고 있는 무기인 split매서드와 strip매서드로 최대한 활용해보았지만 TC 9번을 해결할 수가 없어서 포기하고 다른 사람들의 풀이를 찾아보았다. 파이썬을 이용해서 푼 사람들 대부분이 re라이브러리를 불러와서 정규화라는 것을 활용하는 것을 확인할 수 있었다. TC 9번과 11번의 어려운 예외를 정규화라는 것으로 뚝딱 해결하는 것을 보고, 이건 좀 공부해놓으면 좋겠는데?라는 생각이 들어 공부를 해보았다. 1. 정규표현식(Regular expression)이 무엇일까? 정규 표현식(REs, regexres, regex pattern)이란 파이썬 내부의 re모듈을 통해 사용할 수 있는, 전문화된 프로그래밍 언어이다. 정규표현식은 문자열 집합에 대..

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

SWEA D4 문제를 아직 많이 풀어보진 못했지만, 혁진이의 프로그래밍 다음으로 어려웠던 문제였다. 결론부터 말하자면 이문제의 핵심은 최선을 다한다는 것이고, 이를 구현하기 위해서 뒤에서부터 접근하면 한결 편해지는 문제였다. 문제를 간략히 소개하자면 Alice와 Bob이 목표숫자 N을 정해놓고 숫자 게임을 한다. 숫자게임은 자신의 차례일 때 숫자 x를 x*2로 키우거나 x*2+1로 키울 수 있고, 자신의 차례일 때, 어떻게 숫자를 키우더라도 N보다 크게 된다면 그 사람의 패배이다. 우리가 흔히 아는 31게임이랑 비슷하지만 숫자를 키우는 방식에서 조금 차이가 있다. 문제는 Alice와 Bob이 최선을 다해 게임을 할 때, 누가 이기게 되는지 묻는다. 한번씩 31게임을 할 때, 계산 따위 하지 않고 운에 모..