알고리즘

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

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

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

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

최근에 풀었던 문제 중에 가장 재밌게 푼 문제인 것 같다. 물론 쉽게 푼 문제는 아니었지만, 어떻게 풀지 고민하는 과정과 실제로 그 과정에서 정답이 나오는 게 알고리즘 문제를 푸는 재미인 것 같다. 문제를 간단히 설명하자면, 몇 번의 클릭으로 지뢰가 아닌 곳을 오픈할 수 있는지 횟수에 대한 최솟값을 묻는 문제이다. 추가적인 제약사항은 *(지뢰가 아닌 곳)을 클릭했을 때, 인접한 곳에 지뢰가 없다면 인접한 블록까지 공개가 된다. 그림에서 숫자는 인접한 위치의 지뢰 개수인데, 문제에서 묻는 것은 최소 클릭 횟수이기 때문에 구현하지 않았다. 문제를 처음 보고 최소한의 횟수? 'DFS!'를 생각했지만, 게임판의 길이(N) 이 300까지 가능하기 때문에 DFS는 절대 아니라고 생각했다. 그럼 내 지식에서 남은 보..

이 문제는 수업과정에서 한번 풀어봤던 문제였지만, 그 이후로 그래프나 완전 탐색 문제 위주로 풀다가 오랜만에 마주하니 어떻게 풀어야 할지 감이 잡히지 않았다. 문제는 음주가무를 즐기다가 조교들의 눈을 피해 일사천리로 자신의 방으로 돌아가야하는 고등학생들의 자기 방으로 돌아가는 최단 시간을 구하는 문제이다.(경로가 겹치는 경우 한 명씩 지나갈 수 있으므로 한 단위 시간이 증가한다) 문제만 읽었을 때는 막막했지만, 교수님께서 알려주신 필살기인 손으로 문제 상황을 적으면서 생각을 해보았다. 이 문제는 친절하게 그림으로도 설명을 해주었기 때문에 쉽게 이해할 수 있었다. 손코딩을 하면서 내가 생각해낸 해법은 통로를 하나의 배열로 생각하여 그 통로를 지나는 경우 방문 체크를 하는 것이다. 즉, 위 그림에서 1번 방..