본문 바로가기

알고리즘231

[BAEKJOON] 2004 조합 0의 개수 문제 요약 알고리즘 분류: 수학, 조합 난이도: Silver2 문제내용: 조합 결과값에서 끝자리 0의 개수를 구해라! 사이트 주소: https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 문제풀이 1. 문제 접근방법 https://jih3508.tistory.com/21 [BAEJOON] 11051 이항 계수 2 문제 요약 알고리즘 분류: 조합, 동적계획법 난이도: Silver3 문제내용: 이항 계수( N K)를 10007로 나눈 나머지를 결과를 출력해라 사이트 주소: https://www.acmicpc.net.. 2022. 10. 5.
[BAEKJOON] 1010 다리놓기 문제 요약 알고리즘 분류: 조합, 동적계획법 난이도: Silver5 문제내용: 각케이스마다 서쪽과 동쪽 중복되지않고 연결할수 있는 방법을 출력해라. 사이트 주소: https://www.acmicpc.net/problem/1010 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제풀이 위 문제는 서쪽과 동쪽을 연결할수 있는 다리를 놓아야 하는데 중복이 되지 않아야 하고 서쪽 지점보다 동쪽 지점이 많아야 한다. 그러므로 조합을 생각해서 풀면된다. 2가지 푸는 방법이 있다. 하나는 조합공식을 사용해서 푸는 방법과 동적계획법으로 푸는 방식이다. 조합 공식 사용 방법 위의 조합 공식으로 .. 2022. 10. 4.
[BAEKJOON] 1629 곱셈 - Python 문제 요약 알고리즘 분류: 재귀호출, 분할정복 난이도: Silver1 문제내용: A 를 B 번 곱해서 C로 나눠서 출력한다. 사이트 주소: https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제풀이 위 문제는 아래처럼 pow 함수 사용하거나 제곱으로 연산하거나 for문으로 사용하면 시간 초과가 나올것이다. A, B, C = map(int, input().split()) # 그냥 제곱 연산으로 사용할 경우 result = A ** B % C # for 문으로 사용할 경우 result = 1 for i in ran.. 2022. 10. 3.
[BAEKJOON] 2744 대소문자 바꾸기 문제 요약 알고리즘 분류: 문자열 난이도: Bronze5 문제내용: 문자열 대문자를 소문자, 소문자를 대문자로 변경해서 출력하면 된다. 사이트 주소: https://www.acmicpc.net/problem/2744 2744번: 대소문자 바꾸기 영어 소문자와 대문자로 이루어진 단어를 입력받은 뒤, 대문자는 소문자로, 소문자는 대문자로 바꾸어 출력하는 프로그램을 작성하시오. www.acmicpc.net 접근 방법 이번 문제는 함수 사용 하는 방법을 알면 된다. 파이썬은 isLower, isUpper로 체크 한다음에 .lower(), upper()함수 사용 하면된다. 자바는 문자열을 전체 대소문자 처리는 가능하는데. 이번 문제는 각 문자를 변환 하는거라서 원시적인 방법을 사용해야 한다. char 문자형으로 .. 2022. 10. 1.
[BAEKJOON] 11051 이항 계수 2 문제 요약 알고리즘 분류: 조합, 동적계획법 난이도: Silver3 문제내용: 이항 계수( N K)를 10007로 나눈 나머지를 결과를 출력해라 사이트 주소: https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제풀이 2가지 푸는 방법이 있다. 하나는 조합공식을 사용해서 푸는 방법과 동적계획법으로 푸는 방식이다. 조합 공식 사용 방법 위의 조합 공식으로 사용 하면 된다. 파이썬에서는 factorial 함수를 제공한다. DP로 접근하는 방법 위 사진은 파스칼 삼각형이다. 파스칼 삼각형의 공식은 아래와 같이 정의 할수 .. 2022. 9. 30.
[BAEKJOON] 1149 RGB거리 문제 요약 알고리즘 분류: 동적계획법 난이도: Silver1 문제내용: 빨강, 초록, 파랑색의 N개 집이 있다. 그리고 각 집에 각 색에 칠하는 색의 비용이 있다. i번째와와 i-1, i + 1번째 색은 달라야 한다. 모든 집의 최소 비용으로 칠하는 비용을 구하여라 사이트 주소: https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제풀이 문제 접근 방법 이 문제는 동적계획법이다. 그래서 점화식을 짜는 방법만 알면 된다. 위 .. 2022. 9. 26.

티스토리툴바