목록전체 글 (305)
백준11053 - 가장 긴 증가하는 부분 수열 (DP) Python
https://www.acmicpc.net/problem/11053 해당 문제는 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제다. 인덱스 순서대로 가장 긴 수열을 구해나가면 결국 가장 긴 수열이 무엇인지 파악할 수 있으므로, 다이나믹 프로그래밍(DP)으로 풀이가 가능하다. 먼저 각 인덱스 별로 가장 긴 수열의 길이를 저장해야 하므로 수열의 크기에 맞게 리스트를 만든다. 이때, 리스트에서 각 원소가 갖는 기본값(최솟값)은 1인데, 수열에서의 각 인덱스들은, 자기 자신만을 갖는 길이 1의 수열을 만들 수 있기 때문이다. N, arr = int(data[0]), list(map(int, data[1].split())) dp = [1 for _ in range(N)] 사실 처음 보는 문제 유형..
백준1991 - 트리순회 (그래프, 재귀) Python
https://www.acmicpc.net/problem/1991 해당 문제는 이진트리의 전위 순회 / 중위 순회 / 후위 순회한 결괏값을 출력하는 문제다. 문제에서 해당 순회들이 무엇인지는 설명하고 있기 때문에 추가적인 설명은 하지 않는다. 해당 입력값에 따른 그래프 구현은 아래와 같다. 들어오는 문자열을 쪼갠 뒤 root 노드를 key로 설정, 왼쪽 | 오른쪽 자식이 '.'이면 None으로 설정한 뒤 두 자식을 리스트로 하여 value로 설정했다. def makingGraph (data) : _graph = {} for _str in data : root, left, right = _str.split() left = left if left != '.' else None right = right if ..
백준1283 - 단축키 지정 JS
https://www.acmicpc.net/problem/1283 문제는 n개의 문자열을 주고, 주어진 규칙에 따라 순서대로 단축키가 적용된 문자를 대괄호로 감싼 전체 문자열 출력하는 문제다. 단축키를 설정하는 기준은 먼저 각 문자열이 가진 단어들의 첫 글자가 단축키로 지정되어 있는지 살핀 뒤, 지정되어 있지 않다면 단축키로 등록한 뒤 단축키를 대괄호로 감싸 문자열 반환. 각 단어의 첫 글자가 모두 단축키로 등록되어 있다면 왼쪽부터 단축키로 지정되어 있는지 확인 후 단축키로 등록한 뒤 지정되어 있지 않다면 단축키로 등록한 뒤 단축키를 대괄호로 감싸 문자열로 반환하면 된다. (이때, 단축키는 대소문자를 구분하지 않고, 특정 문자열에 단축키를 지정할 수 있는 문자가 없는 경우 문자열을 그대로 반환해야하니, ..
백준24444 - 알고리즘 수업 - 너비우선탐색1 (deque) Python
https://www.acmicpc.net/problem/24444 문제는 너비우선탐색을 구현하여, 각 정점의 방문순서를 출력하는 문제다. 너비우선탐색 문제 풀이 대해 포스팅을 몇 번 진행한 적 있지만, 이번 포스팅에서는 파이썬 내장모듈인 deque에 대해 소개한다. deque는 double-end queue의 약자로 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조를 말한다. deque는 collections 모듈에 포함되어 있으며 리스트와 유사한 동작을 수행하지만 효율적인 연산을 제공한다. 개인적으로 생각하는 deque와 리스트의 큰 차이점은 맨앞에서 요소를 제거할 때인데, 이때, n이 전체 길이라고 한다면 deque는 O(1)의 시간복잡도, 리스트는 O(n)의 시간복잡도로 처리된다는 것에 있다. (..
백준11652 - 카드 (정렬) Python
문제는 다음과 같이 '가장 많이 보유하고 있는 정수'를 구하되, 여러가지라면 가장 값이 작은 정수를 출력하는 문제다. 풀이 방식은 다음과 같다. 먼저 가지고 있는 정수의 수를 헤아리기 위해, Counter 메서드를 사용하거나, 딕셔너리에 직접 데이터를 대입하여 구할 수도 있다. # Counter 메서드 _count = Counter(data) # 딕셔너리 _dic = {} for v in data : _dic[v] = _dic.get(v, 0) + 1 이후 정렬이 필요한데, 객체 자체를 정렬하는 기능은 없기에, 2차원 배열로의 변환이 필요하다. # 2차원 배열로 변환 _arr = [[key, value] for key, value in _count.items()] #_count.items() 를 활용하여..
백준1138 - 한 줄로 서기 (그리디) Python
https://www.acmicpc.net/problem/1138 문제는 원소의 수와, 차례대로 자기보다 큰 원소가 왼쪽에 몇 개가 존재하는지 주어질 때 주어진 조건에 맞춰 순서대로 줄을 세워 반환하는 문제다. 예시를 설명하면 다음과 같다. 즉, arr = [2,1,1,0] 일 때, arr[0] == 2 인 경우 => 1보다 큰 수가 앞에 두 개 존재한단 의미 [x,x,1,x] arr[1] == 1 인 경우 => 2보다 큰 수가 앞에 한 개 존재한단 의미 [x,2,1,x] arr[2] == 1 인 경우 => 3보다 큰 수가 앞에 한 개 존재한단 의미 [x,2,1,3] arr[3] == 0 인 경우 => 4보다 큰 수가 앞에 존재하지 않는다는 의미 [4,2,1,3] 풀이한 방식은 다음과 같다. 입력값에서 ..
백준12851 - 숨바꼭질2 (DP) Python
https://www.acmicpc.net/problem/12851 문제는 첫 번째, 두 번째 입력값을 각각 n,m 이라고 하고 n은 한번의 연산으로 n - 1 | n + 1 | n * 2 로 바꿀 수 있을 때 m 이 되기 위한 최소 횟수를 구하는 문제다. 해당 문제의 유형은 너비우선탐색으로 분류되어 있었지만, 다이나믹 프로그래밍으로 풀이하듯 접근했다. 처음 작성한 코드 import sys data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r') input_data = data_temp.read() def solution (data) : n,m = map(int,data.split()) dp = [[n]] idx = 0 while..
백준6118 - 숨바꼭질 (BFS) Python
https://www.acmicpc.net/problem/6118 주어진 간선들로 그래프를 구현한 뒤, 루트 노드인 1에서 가장 멀면서 수는 가장 번호는 가장 낮은 노드 | 1과 가장 먼 노드와의 거리 | 가장 먼 노드의 갯수를 출력하는 문제다. '가장 먼 노드'를 찾는 것이기에 주저없이 BFS(너비 우선 탐색) 로직으로 접근하여 해결했다. (프로그래머스에도 비슷한 문제가 있는데, 해당 문제에 대해 자바스크립트로 풀이했던 링크를 남겨두도록 한다.) 2023.09.09 - [개발/algorithm] - 프로그래머스 - Lv.3 가장 먼 노드 (BFS) JS 나는 그래프를 구현하는 로직과, BFS 로직을 통해 정답을 찾는 로직으로 나누어 풀이했다. 먼저 그래프 구현 로직은 다음과 같다. (일반적인 그래프 구..