프로그래머스

프로그래머스: n^2 배열 자르기 (파이썬, 구현)

규칙만 알면 금방 풀 수 있는 문제라 생각한다. 먼저 제한사항부터 보면 n의 최댓값이 10^7이다. 만약 2차원 배열을 2중 반복문으로 일일히 초기화하여 푼다면 시간복잡도가 10^14이상으로 시간초과가 날 것이다. (일반적으로 시간복잡도는 10^9를 넘기지 않아야 한다.) 따라서 2차원 배열을 직접 만들어서 풀수는 없고 다른 풀이를 생각해야 한다. 테스트케이스 설명을 애니메이션으로 아주 현란하게 설명하는 문제였는데 나는 그런건 할줄 몰라서 파워포인트로 간단하게 그림을 그려 설명해보겠다. 테스트 케이스2의 n=4인 2차원 배열이다. 왼쪽에 숫자는 배열에 채워지는 수들이고 괄호안의 숫자는 배열의 몇번째에 있는지를 나타낸 것이다. 문제에서 주어지는 left와 right가 괄호안의 숫자에 해당함을 알 수 있다...

프로그래머스: [1차] 뉴스 클러스터링 (파이썬, 구현)

우선 문제가 꽤나 길다. 코딩테스트는 수학, 공학문제 풀이와 다르게 풀이를 구현하는데 시간이 꽤나 걸려 문제 조건을 꼼꼼히 읽는 것이 특히 더 중요한 것 같다. 문제에선 자카드 유사도라는 새로운 개념을 소개하고 이를 응용하여 두 문자열의 유사도를 출력할 것을 요구한다. 문제를 읽으면서 집중했던 부분은 크게 네가지이다. 첫째로 원소의 중복을 허용하는 다중집합에 대해서도 자카드 유사도를 적용할 수 있다는 것이다. 이는 두 집합간의 교집합을 구할때 중요하다. 왜냐하면 중복을 허용하지 않는다면 리스트를 집합으로 변환 후 뺼셈을 통해 교집합의 원소의 갯수를 쉽게 구할 수 있지만 중복이 있다면 반복문을 통해 교집합을 구해야하므로 교집합을 구하는 구현 방법이 달라진다. 둘째로 두 집합이 모두 공집합일 경우 자카드 유..

프로그래머스: 점프와 순간이동 (파이썬, 구현)

간단한 구현문제이다. 최소값을 구하는 문제이기에 완전탐색, DP, 구현 세가지 방법이 떠올랐으나 제한 사항을 보고 바로 구현문제임을 알 수 있었다. 왜냐하면 N이 10억 이하의 자연수로 일반적으로 효율성 테스트를 통과하기 위해서는 1초안에 통과해야 하는데 1초안에 통과하기 위해선 시간복잡도가 1억 이하여야 하기 때문이다. 문제의 조건을 우선 보면 지나온 거리에 2를 곱하여 이동하는 순간이동은 count를 올리지 않고 1씩 이동하는 것만 count를 올리므로 N이 짝수라면 2로 나누고 N이 홀수라면 1을 빼주어 짝수로 만들어 다시 2로 나누는 작업을 N이 1이 될 때까지 반복하면 됨을 알 수 있다. def solution(n): answer = 1 while n != 1: if n % 2 == 1: n -..

프로그래머스: 가장 먼 노드(파이썬, BFS)

그래프의 root node로부터 가장 멀리 떨어진 노드들의 개수를 구하는 문제이다. 문제의 조건에서 가장 멀리 떨어진 노드의 정의에 대하여 최단경로로 이동했을 때, 간선의 개수가 가장 많은 노드라 명시하였다. 그래프의 탐색이기에 우선 그래프를 인접 행렬로 표현하였고 그 다음으로 그래프의 탐색방법인 DFS, BFS중 고민하였는데 BFS로 푸는 것이 더 효율적이라는 생각이 들었다. 왜냐하면 DFS는 모든 경로를 전부 탐색하여 비교하기에 BFS보다 시간복잡도측에서 비효율적이기 때문이다. 일반적으로 그래프를 탐색하거나 간선들의 가중치가 모두 같을 때 최단경로를 구한다면 BFS가 효율적이다. 혹은 DP를 쓰던지.. 따라서 BFS로 문제를 풀었다. 기본적인 BFS 구현 코드를 사용하였고 거기에 queue에 자식 노..

프로그래머스: 여행 경로 (파이썬, DFS, 백트래킹)

꽤나 어려운 문제였다. 코드를 짜는 것 자체는 어렵지 않았으나 문제의 엣지케이스를 생각하는데 어려움이 있어 처음에 접근을 잘못한 문제다. 주어진 항공권을 모두 써야 하므로 DFS로 접근을 해야함을 알 수 있다. 이때 가능한 경로가 여러 개일수도 있는데 나는 tickets배열을 lambda식으로 정렬하면 알파벳 순서가 앞서는 경로를 탐색할 것이라 생각했다. 그러나 그렇게 풀면 테스크 케이스1에서 계속 실패했는데 이에 대한 엣지케이스를 생각하는 것이 쉽지 않았다. 특정한 엣지 케이스를 생각하진 못했지만 여러개의 경로를 비교해야 하므로 백트래킹을 이용해 풀어야겠다고 생각했다. 백트래킹은 DFS의 응용으로 분기점에서 다른 경로들또한 탐색하도록 하는 알고리즘이다. 문제에서 여행 경로의 길이는 tickets배열의 ..

프로그래머스: 단어 변환 (파이썬, BFS)

변환 횟수가 최소인 경우를 구해야 하므로 BFS로 접근하였다. 처음에 단어들을 어떻게 그래프로 표현할까 하다가 변환 경우의 수를 그려보니 굳이 그래프로 표현 안해도 풀 수 있다는 생각이 들었다. 처음에 테스트케이스3에서 계속 틀렸었는데 그 이유는 두 단어간에 다른 알파벳 갯수를 셀 때 set을 이용해 세었기 때문이다. 그럼 'ccec'같은 단어는 'ce'가 되므로 적절한 비교가 이루어지지 않음을 알 수 있다. 아직 엣지케이스를 생각하는 능력이 부족한 것 같아 그 부분에 대해 좀 더 훈련이 필요하겠다.. 풀이 코드는다음과 같다. BFS는 넓이를 우선으로 탐색하므로 처음에 begin과 차이가 1인 단어들을 deque에 넣고 그 단어들에 대해 다시 차이가 1인 단어들을 deque에 넣으면 넓이 우선 탐색으로 ..

프로그래머스: 네트워크 (파이썬, DFS)

비교적 쉬운 난이도의 문제였다. DFS를 통해 그래프를 탐색하는 전형적인 문제였기 때문이다. LV3에서 정답률이 높은 문제가 LV2에서 정답률이 낮은 문제보다 쉬운 것 같다.. 먼저 두 노드간에 간선 유무를 2차원 배열을 통해서 알려주는데 인접 행렬을 이용해서 그래프를 표현한다. 그래프를 표현하는데는 인접 리스트와 인접 행렬이 있는데 난 인접 행렬을 선호하고 그 중에서도 본 문제풀이와 같이 부모, 자식을 각각의 인덱스에 해당하는 리스트에 넣어서 구현하는 방법을 선호한다. 문제풀이 코드는 다음과 같다. def dfs(node, graph, visited): visited[node] = True for child in graph[node]: if not visited[child]: dfs(child, gra..

프로그래머스: 게임 맵 최단거리(파이썬, DFS, BFS)

N*M 행렬에서 (0,0)에서 (N,M)까지 도달하는 최단경로를 찾아야 하는 문제이다. 최단거리를 구할때는 BFS를 이용하는 것이 좋다. 왜냐하면 DFS는 노드의 끝까지 도달하기에 여러 경로를 비교하기에는 시간복잡도가 크기 때문이다. DFS와 BFS를 구현해본지 오래 되었기에 공부하는 차원에서 두가지 방법 모두로 풀어보려 했다. 먼저 DFS이다. DFS는 분기점에서 트리의 끝까지 탐색하고 돌아오기에 탐색 시간이 길고 deepcopy를 이용해 행렬을 탐색마다 새로 할당해주어야 해서 일반적으로 시간초과가 잘 난다. BFS가 아닌 방법으로 최단경로를 찾으려면 사실 DFS말고 DP를 쓰는게 시간복잡도면에서 좋긴하다. from copy import deepcopy import sys sys.setrecursion..