알고리즘/백준 알고리즘21 [Baekjoon] 백준 알고리즘: 1010 - 다리놓기 문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 내가 생각했던 풀이과정 1) 순서가 없는 조합 문제이다. 조합이란 집합에서 서로 다른 n개의 원소 중에서 순서와 상관없이 r개를 선택하는 것이다. 순서가 없다고 생각한 이유는 어떤 다리를 놓아도, 순서에는 영향을 미치지 않기 때문이다. 2) m이 n보다 크기 때문에 최대 연결할 수 있는 다리의 갯수는 n개이다. m개의 지역에 n개의 다리를 놓을 수 있는 경우를 찾는 것이기 때문에 mCn 문제.. 2021. 5. 17. [Baekjoon] 백준 알고리즘: 1920번 - 수 찾기 문제 www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 내가 생각했던 풀이과정 1) 이진탐색을 사용하려면 정렬되야 하기 때문에, 처음 정렬을 한다 2) 시작을 start, 끝을 end로 index를 설정해주고, 찾아야할 숫자는 in 함수를 통해 반복문을 돈다. 3) 시작이 끝보다 작을 때까지 반복하며 이진 탐색을 위해 중간지점을 찾는다 중간지점이 타겟이라면 1을 return하고 중간지점의 값보다 타겟이 작을 경우.. 2021. 5. 6. [Baekjoon] 백준 알고리즘 - 1157: 단어 공부 1. 문제 www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 2. 내가 생각했던 풀이과정 1) 대소문자를 구분하지 않고, 출력결과가 대문자이기 때문에 upper()함수를 이용하여 단어를 대문자로 바꿔준다. 2) 파이썬의 자료형인 set을 이용하면 중복을 제거할 수 있는데 set으로 중복을 없애준 후에 중복을 없앤 리스트를 넣어준다. 3) wordlist에 들어있는 리스트들을 반복하면서, 해당 문자가 리스트에 몇 개 있는지를 세어주고, 세어준 값을 cnt 리스트에 넣어준다. 4) cnt 리스트에.. 2021. 4. 21. [Baekjoon] 백준 알고리즘 - 11047: 동전 0 1. 문제 www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 2. 내가 생각했던 풀이과정 이 문제는 그리디이다. 그리디라고 생각한 이유는 입력받는 숫자의 단위의 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 돈을 종합해 다른 해가 나올수 없기 때문이다. 또한, 그리디라고 힌트를 문제에서 주고 있는데 문제 풀이를 위한 최소한의 갯수를 사용하라고 했기 때문이다. 1) 단위의 갯수와, 돈을 입력받.. 2021. 3. 26. 이전 1 2 3 4 5 6 다음