Algorithm

[프로그래머스] 행렬 테두리 회전하기

문제 정사각형 혹은 직사각형 형태의 2차원 행렬이 주어지면, 회전 queries에 따라 테두리에 있는 숫자들만 시계 방향으로 1칸씩 회전한다. 각 회전마다 가장 작은 숫자를 구하여라. 아래 예시에서 회전을 3번 하는데 각 회전 당 가장 작은 숫자는 8, 10, 25이다. (문제 링크) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 처음에 가장자리에 위치한 숫자들을 시계방향으로 이동시키다가, 모서리에 있는 숫자들을 계속 저장해야 한다는 점을 깨달았다. 숫자들을 하나씩 시계방향으로 이동하지 않고, 모서리에 있는 숫자가 안 겹치게 하기 위해 그림처럼 ..

[그래프] 서로소 집합으로 사이클 판별하기

해당 포스팅은 나동빈님의 이코테 강의를 듣고 정리한 내용입니다. 서로소 집합은 무방향 그래프 내에서의 사이클 판별에 사용될 수 있다. 방향 그래프의 사이클 판별 여부는 DFS를 사용한다. 사이클 판별 알고리즘 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다. 루트 노드가 서로 다르다면 두 노드에 대해 합집합(union) 연산을 수행한다. 루트 노드가 서로 같다면 사이클이 발생한 것이다. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다. 모든 간선이 처리되었을 때 사이클이 발생하지 않으면 사이클이 없는 그래프이다. 위와 같은 그래프에 사이클이 존재하는지 판별하는 코드는 아래와 같다. 전에 구현한 서로소 집합 알고리즘과 동일하고, 사이클 판단 여부만 추가되었다. def find_p..

[그래프] 서로소 집합

해당 포스팅은 나동빈님의 이코테 강의를 듣고 정리한 내용입니다. 서로소 집합(disjoint set) 서로소 집합(disjoint set)이란 공통 원소가 없는 두 집합을 의미한다. 두 집합 간에 교집합이 없으면 서로소 집합이다. 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 두 종류의 연산을 지원한다. 합집합(union): 두 원소가 포함된 각각의 집합을 하나의 집합으로 합치는 연산 찾기(find): 특정 원소가 어떤 집합에 속하는지 알려주는 연산 서로소 집합의 동작 과정 union 연산을 확인하며 서로 연결된 두 노드 A, B를 확인한다. A와 B의 루트 노드 A’, B’을 찾는다. A’, B’를 부모 노드로 설정한다. 모든 union 연산을 처리할 때까..

[자료구조] 우선순위 큐 (heapq)

우선순위 큐 우선순위 큐(Priority Queue)란 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 큐이다. 데이터를 우선순위에 따라 처리하고 싶을 때 유용한 자료구조이다. 힙 자료구조는 우선순위 큐를 구현하기 위해 사용되는 자료구조이다. 대부분의 언어에서 표준 라이브러리 형태로 지원한다. 파이썬에는 PriorityQueue 또는 heapq를 사용할 수 있는데, 일반적으로 heapq가 더 빠르게 동작하기 때문에 수행 시간이 제한된 경우에는 heapq 사용을 권장한다. 큰 숫자에 우선순위를 부여하는 힙을 최대 힙(Max Heap), 작은 숫자에 우선순위를 부여하는 힙을 최소 힙(Min Heap)이라고 한다. heapq는 내부적으로 트리로 구현되어 있어 데이터를 삽입, 삭제하는데 O(logN) 만큼의 ..

[최단경로] 다익스트라

다익스트라 특정 노드 → 모든 노드로 가는 최단 경로를 계산한다. 정확히 얘기하면 최단 경로는 아니고, (일반적으로 코딩 테스트에서는) 최단 경로의 길이를 계산한다. 매번 비용이 최소가 되는 경로를 선택하기 때문에 그리디 알고리즘으로 분류되기도 한다. 1. 간단한 다익스트라 알고리즘 위와 같이 가중치가 있는 방향 그래프에서 다익스트라 알고리즘을 사용해 최단 경로를 구해보자. 1번 노드에서 시작해 모든 노드로 가는 최단 경로를 구하는 예시이다. 다음에 선택되는 노드를 노란색으로 표시했다. 각 노드까지의 거리는 무한대로 초기화하고, 1번 노드는 자기 자신이므로 0으로 초기화한다. 가장 가까운 1번 노드를 방문해 현재 거리보다 더 짧은 경로를 발견하면 업데이트한다. 다음에는 가장 가까운 노드를 방문하고, 거리..

[백준] 18353번 - 병사 배치하기 (python)

문제 병사의 전투력이 내림차순이 되도록 하는 가장 긴 수열을 구한다. 문제 바로가기 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 LIS 알고리즘을 활용하면 쉽게 풀 수 있다. "증가하는" 부분 수열이 아닌, "감소하는" 부분 수열을 만들어야 하기 때문에 reverse()를 사용해 초기 전투력을 뒤집은 후에 계산했다. 이전 LIS 포스팅 [백준] 가장 긴 증가하는 부분 수열 (LIS) 가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subse..

[DP] 가장 긴 증가하는 부분 수열 (LIS)

가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)은 대표적인 다이나믹 프로그래밍 문제이다. {10, 20, 10, 30, 20, 50} 과 같은 수열이 주어졌을 때, 수가 점점 증가하는 수열의 가장 긴 길이를 구한다. 1) Dynamic Programming 풀이법 - O(N^2) 파라미터 설명: n = 수열의 길이 arr = 수열을 이루는 숫자가 담긴 배열 d = arr[i]를 마지막 원소로 가질 때 LIS의 길이 d[i] 값을 1로 초기화한다. 현재 위치(i)보다 이전에 위치한 원소(j)가 작은지 확인한다. (i는 기준이 되는 인덱스, j는 i보다 작은 인덱스) arr[i] > arr[j] 이면, 현재 위치 숫자 중 d의 최댓값..

[백준] 1932번 - 정수 삼각형 (python)

문제 위에서부터 시작해 아래로 내려오며 각 층의 수를 하나씩 선택해 더할 때, 총합이 최대가 되는 경로를 구하여라 문제 바로가기 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 파란색 글씨가 입력으로 들어온 삼각형 모양의 숫자이고, 빨간색 글씨가 각 경우에서 누적합이 최댓값이 되는 경우이다. 코드에서 파란색이 num, 빨간색이 d에 해당한다. 맨 위 꼭짓점은 더할 수 있는 값이 없으므로 자기 자신이다. 왼쪽 변과 오른쪽에 있는 숫자의 경우, 자기 자신에 바로 위에 있는 숫자만 더할 수 있다. 중앙에 있는 숫자의 경우, 자기 자신에 윗줄의 양옆 숫자 중 최댓값을 더한다. → 그..

[백준] 11403번 - 경로 찾기 (python)

문제 가중치 없는 방향 그래프 G가 주어진다. 모든 정점에 대해 i → j로 가는 경로가 있는지 확인해, 모든 노드에서 모든 노드로의 경로 존재 여부를 출력하라. 문제 바로가기 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 모든 노드 → 모든 노드로의 최단 경로를 찾는데 사용되는 알고리즘인 플로이드-와샬 알고리즘을 사용했다. (DFS, BFS를 사용해서도 풀 수 있을 것 같다.) 이 문제에서는 자기 자신으로 가는 경로도 존재하는지 확인하는 점이 기존 플로이드-와샬 알고리즘과 다르다. a → k → b 노드 순서로 노드 k를 경유한다고 볼 때, a..

[백준] 1463번 - 1로 만들기 (python)

문제 문제 링크 접근법 처음에 조건문을 떠올렸지만, 10의 경우 최소값이 3이라는 예시를 보고 조건문으로는 구현할 수 없어서 다른 풀이를 생각했다. DP를 사용해 풀었다. 숫자 1부터 시작해 각 숫자를 1로 만들기 위한 최소 연산 횟수를 리스트 d에 저장한다. 인덱싱을 편하게 하기 위해서 사용하지 않는 인덱스 0을 만들어 0으로 초기화했다. 위 그림처럼 2나 3으로 나눈 수가 이전에 있으면, 나눈 수의 최소값+1을 하고, 아닌 경우는 이전 값+1을 한다. 2: 1에서 +1 3: 1에서 +1 4: 2에서 +1 5: 4에서 +1 6: 3에서 +1 7: 6에서 +1 8: 4에서 +1 9: 3에서 +1 10: 9에서 +1 내 풀이 각 숫자가 3의 배수인 경우, 2의 배수인 경우, 배수가 아닌 경우 순서대로 조건..