Redddy's Devlog

N의 약수가 모두 구해졌을 때 N을 구하는 문제!! 📘풀이 1. N의 모든 약수가 주어지니 최대값과 최소값을 곱하면 N을 구할 수 있다. 2. 만약 N이 소수의 제곱수라면 약수는 제곱근 하나밖에 없다. 그래서 그것을 따로 처리해주었다. (지금생각해보니까 필요없는 작업이었을지도...?ㅎㅎ) 💻코드 n = input() measuar = list(map(int, input().split())) print(max(measuar)*min(measuar)) if len(measuar) != 1 else print(measuar[0]**2) 📎문제링크: https://www.acmicpc.net/problem/1037

정답 비율과 푼사람이 적었지만 문제 해결 알고리즘은 쉽게 생각나서 이 문제를 골랐지만 의외로 복잡했고, 코드가 지저분해졌었다. 그래서 다른 사람의 도움을 얻어보려 열심히 구글링을 해봤지만 맞힌 사람이 63명 밖에 없었고(2022.4.18기준) 파이썬으로 풀이를 적어둔 사람은 한명도 보지 못했다...ㅎㅎ 📘풀이 1. 입력된 단어들을 사전순으로 정렬한다. 이때 인덱스도 같이 저장해준다. 2. 정렬된 단어들을 한글자씩 비교해가면서 접두사의 길이가 최대인 경우를 찾는다. 3. 접두사의 길이가 최대이면서 가장 먼저 입력된 단어를 출력한다. 💻코드 n = int(input()) a = [input() for _ in range(n)] # n = 9 # a = ["noon", "is", "for","lunch","m..

처음에는 단순히 itertoors에서 combinations를 import해서 사용했는데 예상했던대로 시간초과가 나왔다. (요즘 문제 푸는데 시간초과가 너무 많이 나와...ㅜ) 그래서! 조합을 combinations를 사용하는 것이 아니라 식을 factorial을 불러와서 조합의 경우의 수를 만들어 주었다. 📚 풀이 1. math 모듈을 가져와 factorial을 사용한다. 2. mCn 을 factorial을 사용해서 만든다면 => (m!/(m-n)!)/n! 3. 2번에서 사용한 식을 컴퓨터에서 실행하면 오차가 발생한다. (23 24 입력시 23.9999996이 나옴) 그래서 어차피 몫과 값이 다를리가 없기 때문에 /가 아닌 //를 사용해준다. 💻 코드 import sys, math input = sys..

월과 일이 주어졌을때 무슨요일인지 알아내는 프로그램이다. 처음부터 2007년이라는 연도가 주어졌기 때문에 조금은 쉽게 갔다. 만약 연도까지 입력값에 따랐다면 훨씬 더 복잡한 알고리즘으로 작성됐을 것이다. 📚 풀이 1. 입력받은 월(month)을 일로 변경하여 입력받은 일(date)과 더한다. 2. 더해진 일을 7로 나누어 나머지로 요일을 확인한다. 💻 코드 # PYTHON month, date = map(int, input().split()) # 매월의 마지막 일수 month_list = [31,28,31,30,31,30,31,31,30,31,30,31] day_list = ["MON","TUE","WED","THU","FRI","SAT","SUN"] days = 0 # 주어진 달의 이전달까지 모든 일을..

● 스택을 사용한 문제 ● 그리고 - 가 입력됐을때 어떻게 처리할지가 키포인트 우선 입력이 들어오면 바로 리스트에 담지 않고 입력이 ,- 중에 있는지 먼저 체크하였다. 만약

문제해결: 입력받은 값을 가장 큰 팩토리얼 숫자부터 내림차순으로 빼준다. https://www.acmicpc.net/problem/2057

coordinate 라는 리스트를 만들어준 다음 입력 받은 것을 넣어 주었다. 여기서 coordinate는 좌표라는 뜻! 넣어줄때 [x, y] 로 넣어준게 아니라 [y, x] 로 넣어주었는데 문제가 y가 증가하는 순으로 출력하는 것이니 sort() 함수를 써주기 위해 y를 먼저 집어넣었다.

브루트 포스 (Brute-force) 는 '무차별 대입' 이라는 의미이다. 말 그대로 모든 경우의 수를 대입해보는 것이다. 완전탐색 전략을 사용하여 확실하게 답을 구하는 알고리즘이지만 단점은 시간복잡도에 있다. 모든 경우를 돌아보기 때문에 문제에서 시간초과가 발생 할 수 있다. 다음 문제를 보자. N개의 수를 입력 받아서 두 수를 뽑아 합이 가장 클 때는? 브루트 포스를 사용한다면 2중 for문을 돌면서 두 수를 골라 더해서 최댓값을 갱신하면 '두 수를 뽑는 모든 경우'를 살펴보게 되고, 답을 확실하게 구할 수 있다. 이때 시간 복잡도는 O(N^2)이 된다. 버뜨 list 사용해서 최댓값 찾고 그 두개를 더하면 시간복잡도는 O(NlogN)이다. 브루트 포스로 문제를 풀 때는 반복문을 사용할 때도 있고, ..

Stack은 '쌓다', '무언가가 쌓여 있는 더미' 등을 의미한다. 스택은 의미 그대로 어떤 데이터를 삽입/삭제하는 과정을 '쌓는' 형태로 나타낼 수 있는 자료구조이다. 스택의 특징은 FILO (First In Last Out) 즉 먼저 저장된 데이터가 가장 나중에 나가는 방식으로 저장된다. 이름에서 힌트를 준것처럼 데이터가 차례대로 쌓인다. 가장 나중에 들어온 데이터는 먼저 나간다 LIFO (Last In First Out). 풜스트인풜스트 아웃 이말은 전에 TV 프로그램을 보다가 소방관 얘기가 나왔을 때 먼저 접했던 것 같다. 자료구조 얘기 하다가 뭔 소방관 얘기냐? 할 수 있겠는데 소방관들이 화재 현장을 들어 갈 때 FILO을 한다고 한다. 즉 먼저 들어가서 구조를 하고 끝까지 현장에 남아서 구조를..

요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 예제 입력 예제 출력 7 3 문제 풀이 import sys input..