목록개발/algorithm (175)
백준20291 - 파일 정리 Python | JS
https://www.acmicpc.net/problem/20291 해당 문제는 입력값에서 등장하는 확장자 파일의 갯수를 확장자 이름의 사전순으로 정렬하여 반환하는 문제다. 파이썬에서는 아래와 같은 콜렉션 모듈에서 제공하는 Counter 메서드를 사용해도 되지만, 이번 포스팅에서는 다루지 않고, 파이썬과 자바스크립트 모두 딕셔너리(Python) | 객체(JS)를 사용하여 풀이했다. from collections import Counter 문제 풀이는 그리 어렵지 않다. 먼저 확장자를 key | 등장 횟수를 value로 가질 딕셔너리 | 객체를 선언한다. 이후 파일명에서 등장하는 온점이 하나 뿐이라고 했으니, '.'을 기준으로 입력값을 쪼갠 뒤에 뒤에 있는 확장자를 딕셔너리 | 객체에 추가한다. 데이터 추..
백준4948 - 베르트랑 공준 (에라토스테네스의 체) Python
https://www.acmicpc.net/problem/4948 해당 문제는 입력값이 1
백준11286 - 절댓값 힙 (heap) Python
https://www.acmicpc.net/problem/11286 어제 포스팅한 최소 힙과 비슷한 문제지만, 절댓값으로 정렬한 힙을 구현하는 문제다. 특이사항으로는 가장 작은 값이 여러 개일 경우, 가장 작은 수(절댓값이 같은 수가 둘 있다면 음수)를 먼저 출력하고 제거해야 한다. 내가 풀이한 방법은 다음과 같다. - 힙 데이터 추가의 경우 ( v != 0 ) 먼저 정수 절댓값으로 변환 후 절댓값 힙에 넣기 전, 해당 정수를 기록하기 위한 빈 딕셔너리를 선언했다. 이 딕셔너리는 중복도 헤아리기 위해 현재 힙에 있는 특정 정수의 수를 기록한다. storage = {} for v in arr : if v != 0 : # 자바스크립트의 경우 단축평가를 활용한 # storage[v] = (storage[v] ..
백준1927 - 최소 힙(heap) Python
https://www.acmicpc.net/problem/1927 먼저 힙은 이진트리를 기반으로 한 자료구조로 특정한 규칙에 따라 원소들이 정렬되어 있는 자료구조다. 이진트리란, 한 노드가 최대 두 개의 자식 노드를 가질 수 있는 노드로, 이 덕분에 계층적 정렬 저장이 가능하다. (간단히 [1,2,3] 을 하나의 큐라고 한다면, 중간에 위치한 2는 앞에 1 | 뒤에 3 이라는 자식 노드를 가짐을 의미한다.) 자료구조 힙의 경우는, 파이썬에서 heapq라는 내장 모듈을 불러와 사용이 가능하다. 물론 직접 힙을 구현하여 사용하는 방법도 있겠지만, 비슷한 자료구조인 큐보다는 비교적 사용빈도가 적기에 해당 포스팅에서는 모듈을 사용한 풀이만 다룬다. heapq를 사용한 힙에서 사용하는 메서드는 여러가지가 있겠지만..
백준15656 - N과 M (7) | Python itertools 모듈
https://www.acmicpc.net/problem/15656 해당 문제는 등장하는 모든 수열을 중복없이 나열하는 문제로, 예전 자바스크립트로 풀던 방식처럼 백트래킹 로직을 활용하여 풀었더랬다. import sys data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r') input_data = data_temp.read().splitlines() def solution (data) : [_,m], temp = map(lambda x : list(map(int, x.split())),data) arr = sorted(temp) result, storage = [],[] def backTracking () : if len(sto..
백준1966 - 프린터 큐 Python
https://www.acmicpc.net/problem/1966 문제에서 입력은 여러 테스트케이스를 함께 주고, 하나의 테스트 케이스에는 출력 순서를 원하는 요소의 위치와, 요소 집합이 주어진다. 파이썬에서는 모듈로 queue를 제공한다고는 하지만, 모듈을 사용하지 않고 구현해보고 싶다는 생각에 사용하지 않았다. 접근한 풀이 방식은 다음과 같다. 출력을 원하는 위치(location) 0 | 그리고 요소 집합(arr) [1,1,9,1,1,1] 이 주어졌다고 한다면, 요소 집합을 내림차순으로 정렬하여 따로 저장하고, (이는 나가야 하는 숫자의 순서를 의미하는 배열로써 활용) 정렬된 배열의 첫 숫자를 우선 순위 값의 지시표로 활용하였다. 또 특정 위치에 존재하는 값을 따로 저장해두고, 집합에서의 특정 위치에..
백준2776 - 암기왕 Python
https://www.acmicpc.net/problem/2776 문제는 다음과 같다. 쉽게 얘기하면, N개의 테스트 케이스 | 수첩1의 길이 | 수첩1의 내용 | 수첩2의 길이 | 수첩2의 내용이 주어질 때, 수첩2의 요소가 순서 상관없이 수첩1에 포함되어 있다면 1을, 그렇지 않다면 0을 반환하면 된다. a : [1,2,2,3] 배열과 b : [2,3,4] 배열이 있다고 가정했을 때, b의 요소가 a 배열에 포함되있는지 확인하는 방법은 딕셔너리를 활용하거나 혹은 정렬하여 이분탐색으로 활용하는 등 여러 방법이 있겠지만, 나는 중복된 요소를 제거하고 고유한 요소만 남긴다는 특징을 가진 set를 활용하여 문제를 해결했다. (문제에서 주어지는 정수 데이터의 수가 1백만 이하이기 때문에, 키 | 밸류값을 함께..
백준9506 - 약수들의 합 JS | Python
https://www.acmicpc.net/problem/9506 해당 문제는 특정 수 n이 주어질 때, n을 제외한 n의 약수의 합이 n과 같다면 예제와 같은 문자열을 만들어 반환, 그렇지 않은 경우는 n is NOT perfect.라는 문자열을 반환하는 문제다. 해결한 방식으로는 다음과 같다. 먼저 약수를 담을 리스트를 만든다. 만약 n으로 6이 주어졌다고 한다면 반복문을 통해 1~3까지의 수만 6과 나누어 떨어지는지 계산한 뒤, 리스트에 추가한다. 6은 이미 무조건 약수일 뿐더러, 3을 초과하는 수는 6의 약수가 될 수 없기 때문에 반복문의 범위를 줄인다고 보면 된다. 이후 약수를 담은 리스트의 총합과 n의 값을 비교하여 출력 양식에 맞춰 출력한다. 파이썬 소스코드 import sys temp = ..