본문 바로가기
728x90
반응형

알고리즘115

[BOJ] 3036번 링 / 사용언어 : 파이썬(python) ※ 문제링크 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net ※ 관련 개념 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 ko.wikipedia.org 이번 문제는 최소공약수를 통해 문제를 해결하는 문제였다. 문제를 풀기 위해서는 반지름으로 원의 둘레를 구하는 방법을 알아야했다. 원의 둘레는 반지름에 2를 곱하고 𝝅를 추가적으로.. 2021. 12. 21.
[BOJ] 2981번 검문 / 사용언어 : 파이썬(python) ※ 문제링크 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net ※ 관련 개념 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 ko.wikipedia.org 해당문제는 나머지정리와 유클리드 호제법을 사용해서 풀어야하는 문제였다. 처음에는 단순히 브루스포트방식으로도 풀 수 있지 않을까 해서 해당 방식으로 풀어봤는데 역.. 2021. 12. 20.
[BOJ] 2609번 최대공약수와 최소공배수 / 사용언어 : 파이썬(python) ※ 문제링크 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 해당문제는 두개의 수가 주어졌을때, 두 수의 최대공약수와 최소공배수를 구하는 문제였다. 문제를 해결하기 위해 최대공약수와 최소공배수의 성질을 이용했다. 예시) 18, 24 -> 18 = 2x3x3 / 24 = 2x2x2x3 -> lcm = 2x3(6) / gcf = 2x2x2x3x3(72) 자세한 문제풀이 방식은 아래와 같다. 1. 에라토스테네스의 체를 활용하여 10000이하의 소수리스트 생성 2. 소수리스트를 활용하여 두개의 숫자를 소인수 분해하여 리스트 생성 3. 리스트들을 합쳐서 소인수들을 확인하고 해당 소인수.. 2021. 12. 19.
[BOJ] 14889번 스타트와 링크 / 사용언어 : 파이썬(python) ※ 문제링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net ※ 관련 알고리즘 설명 [알고리즘] 백트래킹(Backtracking)이란? (feat. DFS, 기준함수, sum of subset) 백트래킹(Backtracing)의 개요 백트래킹은 구하고자 하는 해를 튜플로 나타내고 튜플에 기준 함수(한정 함수)를 적용했을 때의 결과가 최대치, 최소치 혹은 일정 조건을 만족하게끔 만들어주는 퇴 it00.tistory.com 해당문제는 DFS와 백트래킹을 활용하여 푸는 문제였다. 문제를 해결하기 위해 처음 떠올린 풀이방법은 아래와 같았다.. 2021. 12. 19.
[BOJ] 1037번 약수 / 사용언어 : 파이썬(python) ※ 문제링크 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 해당 문제는 약수를 통해 해당 값들을 약수로 가지는 수를 도출해내는 문제였다. 비교적 간단하게 풀 수 있는 문제로 약수 중 가장 작은 값과 가장 큰 값을 곱하면 해당 숫자를 구할 수 있는 성질을 이용하여 문제를 풀었고, 결과도 정상적으로 출력되는 것으로 확인하였으며, 해당 코드는 아래와 같다. N = int(input()) number_list = list(map(int, input().split())) maxValue = max(number.. 2021. 12. 19.
[BOJ] 17298번 오큰수 / 사용언어 : 파이썬(python) ※ 문제링크 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 해당문제는 스택을 사용하여 풀어야하는 문제였다. 처음 문제를 읽고 반복문으로도 풀 수 있을 것 같아서 시도해봤는데 역시나 시간초과가 뜨는 것을 확인하였다. 그 후 스택을 활용하여 문제를 풀어보려고 시도를 했는데 생각보다 쉽지않아 구글링을 통해 해결방법을 글로 확인한 후 이를 직접 구현해보기 위해 계속 시도를 해보았다. 스택을 활용한 문제풀이 방법과 이를 바탕으로 내가 직접 구현해본 코드는 아래와 같다. 1. 입력값으로 받은 숫자들로 리스트를 만든다. 2. 숫자 .. 2021. 12. 19.
[BOJ] 1874번 스택 수열 / 사용언어 : 파이썬(python) ※ 문제링크 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net ※ 기본문제 [BOJ] 10828번 스택 / 사용언어 : 파이썬(python) ※ 문제링크 : https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 data-is-power.tistory.com ※.. 2021. 12. 17.
[BOJ] 4949번 균형잡힌세상 / 사용언어 : 파이썬(python) ※ 문제링크 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net ※ 기본문제 [BOJ] 10828번 스택 / 사용언어 : 파이썬(python) ※ 문제링크 : https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 data-is-power.tistory.com ※ 문제풀이 while True: check_list = [] sent.. 2021. 12. 17.
[BOJ] 14888번 연산자 끼워넣기 / 사용언어 : 파이썬(python) ※ 문제링크 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net ※ 관련 알고리즘 설명 [알고리즘] 백트래킹(Backtracking)이란? (feat. DFS, 기준함수, sum of subset) 백트래킹(Backtracing)의 개요 백트래킹은 구하고자 하는 해를 튜플로 나타내고 튜플에 기준 함수(한정 함수)를 적용했을 때의 결과가 최대치, 최소치 혹은 일정 조건을 만족하게끔 만들어주는 퇴 it00.tistory.com ※ 문제풀이(실패사례) N = int.. 2021. 12. 17.
728x90
반응형

티스토리툴바