백준 2407번: 조합

수학 문제 처럼 조합을 푸는 문제다!실버 3이라서 간단하게 이론을 코드로 그대로 표현했더니 시간 초과가 났다. import sysfrom functools import reducedef fuc(n): mylist = [i for i in range(1, n + 1)] result = reduce(lambda x, y: x * y, mylist) return resultinput = sys.stdin.readlinen, m = map(int, input().split())print(int(fuc(n) / (fuc(m) * fuc(n - m))))  조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음)이 공식을 보고 펙토리얼로 재귀함수를 구현하려고 했지만 ..

• format_list_bulleted 알고리즘/백준
• · 2024. 7. 8.
• textsms

백준11779번: 최소비용 구하기 2

11779번 최소비용구하기2문제 해설n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다.A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다.그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하면 된다. 항상 시작점에서 도착점으로의 경로가 존재한다. 문제 링크https://www.acmicpc.net/problem/11779문제 풀이우선 순위 큐와 다익스트라 알고리즘 활용하면 최소비용을 구할 수 있다.우선 각 출발 도시별 도착도시 번호와 버스 비용이 주어질때 graph[출발도시].append(도착도시,비용)을 해준다.이제 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출..

• format_list_bulleted 카테고리 없음
• · 2024. 5. 26.
• textsms

백준 10819번: 차이를 최대로

10819번: 차이를 최대로문제해설N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|풀이과정dfs로 구현을 하려다가 너무 복잡해서 순열 라이브러리를 이용하였다.순열을 구해주는 permutation함수를 for문안에 넣어줘서, 순열이 나올때마다 그 순열대로 식이 실행되게 해주었다.m=0으로 처음에 초기화를 해준다음 m보다 식의 값이 크다면 교환해주었다.import sysfrom itertools import permutationsinput=sys.stdin.readlinem = 0for a in permutation..

• format_list_bulleted 알고리즘/백준
• · 2024. 5. 26.
• textsms

백준 1003번: 피보나치함수

이 문제는 N번째 피보나치 수를 구하는 c++로 이루어진 함수의 동작을 이해하여, 0과 1이 몇번 출력되는지 구하는 프로그램을 작성해야하는 문제이다.위 C++함수는 재귀적으로 0과 1을 반환하며 피보나치 함수의 답을 구하기 때문에 0과 1이 나올때마다 카운트 해주면 된다고 생각했다.처음에는lst=[]def fibonacci(n): i=0 if n == 0: i=0 lst.append(i) elif n == 1: i=1 lst.append(i) else: i=fibonacci(n-1)+fibonacci(n-2) lst.append(i) return lstdef count(Lst): s1=0 ..

• format_list_bulleted 알고리즘/백준
• · 2024. 5. 26.
• textsms

백준 20920번: 영단어 암기는 괴로워

화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.자주 나오는 단어일수록 앞에 배치한다.해당 단어의 길이가 길수록 앞에 배치한다.알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자.import sysinput=sys.stdin.readlineeng=dict()n,m=map(int,input().split())f..

• format_list_bulleted 알고리즘/백준
• · 2024. 2. 27.
• textsms

백준 4195번:친구 네트워크

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.from sys import stdininput = stdin.readlinedef find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x]def union(a, b): a = find(a) b = find(b) if a != b: ..

• format_list_bulleted 알고리즘/백준
• · 2024. 2. 27.
• textsms