알고리즘
-
* 브루트 포스 (Brute Force) 무차별 대입하여 억지로 문제를 해결한다는 뜻이다. 즉, 모든 경우의 수를 다 탐색하여 문제를 해결하는 알고리즘이다. ex ) 네자리 비밀번호의 자물쇠는 0000~9999를 전부 대입해보면 풀린다. (경우의 수는 10,000) *브루트 포스 알고리즘 설계 문제의 가능한 경우를 계산해본다. (직접 손으로 계산, 일반적으로 100만이 넘어가는 경우의 수라면, 브루트포스로 문제를 해결할 수 없다.) 가능한 모든 방법을 만들어 코딩한다. (for문, 순열사용, 재귀호출, 비트마스크 등이 있다.) 각각의 방법을 통해 답을 구한다. 시간 복잡도는 대부분 O(경우의 수 * 방법 1가지의 소요시간) *브루트 포스 구현 *N중 for문 N개 중에 M개를 선택해야 하는 경우에 자주 ..
알고리즘 (미작성) - 브루트 포스(Brute Force) - 순열(permutation)* 브루트 포스 (Brute Force) 무차별 대입하여 억지로 문제를 해결한다는 뜻이다. 즉, 모든 경우의 수를 다 탐색하여 문제를 해결하는 알고리즘이다. ex ) 네자리 비밀번호의 자물쇠는 0000~9999를 전부 대입해보면 풀린다. (경우의 수는 10,000) *브루트 포스 알고리즘 설계 문제의 가능한 경우를 계산해본다. (직접 손으로 계산, 일반적으로 100만이 넘어가는 경우의 수라면, 브루트포스로 문제를 해결할 수 없다.) 가능한 모든 방법을 만들어 코딩한다. (for문, 순열사용, 재귀호출, 비트마스크 등이 있다.) 각각의 방법을 통해 답을 구한다. 시간 복잡도는 대부분 O(경우의 수 * 방법 1가지의 소요시간) *브루트 포스 구현 *N중 for문 N개 중에 M개를 선택해야 하는 경우에 자주 ..
2020.04.19 -
문제 링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 에라토스테네스의 체를 이용하면 된다. https://infinitt.tistory.com/232 알고리즘 (1) - 수학 : 유클리드 호제법 , 에라토스테네스의 체 (나머지 연산, 최대 공약수, 최소공배수, 소수) codepuls의 sw역량테스트_기초파트를 듣고 정리한 내용입니다. 수학과 관련한 기초문제에는 크게 3가지 분류로 나뉘어진다. 나머지 연산 최대 공약수, 최소 공배수 소수 (prime number) 1...
백준 (boj) 파이썬 - 1929 : 소수 구하기문제 링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 에라토스테네스의 체를 이용하면 된다. https://infinitt.tistory.com/232 알고리즘 (1) - 수학 : 유클리드 호제법 , 에라토스테네스의 체 (나머지 연산, 최대 공약수, 최소공배수, 소수) codepuls의 sw역량테스트_기초파트를 듣고 정리한 내용입니다. 수학과 관련한 기초문제에는 크게 3가지 분류로 나뉘어진다. 나머지 연산 최대 공약수, 최소 공배수 소수 (prime number) 1...
2020.04.18 -
수학과 관련한 기초문제에는 크게 3가지 분류로 나뉘어진다. 나머지 연산 최대 공약수, 최소 공배수 소수 (prime number) 1. 나머지 연산 (Modular Arithmetic) Python 으로 문제를 푼다면 상관없겠지만, C++ , Java와 같은 경우에는 표현할 수 있는 정수의 길이가 제한되어있다. 가장 긴 정수 표현방법인 longlong으로 했을때 8byte이므로.... 따라서 문제에서는 이를 n으로 나눈 나머지를 구하라 와 같은 방식으로 출제하게 된다. 흔히 %를 사용하는 modular. * 이러한 유형의 문제를 풀때 알아두면 좋은 공식 덧셈 : (A+B)%C = (A%C + B%C)%C 곱셈 : (A*B)%C = (A%C * B%C)%C 뺄셈 : (A-B)%C = ((A%C)-(B%C)..
알고리즘 (1) - 수학 : 유클리드 호제법 , 에라토스테네스의 체 (나머지 연산, 최대 공약수, 최소공배수, 소수)수학과 관련한 기초문제에는 크게 3가지 분류로 나뉘어진다. 나머지 연산 최대 공약수, 최소 공배수 소수 (prime number) 1. 나머지 연산 (Modular Arithmetic) Python 으로 문제를 푼다면 상관없겠지만, C++ , Java와 같은 경우에는 표현할 수 있는 정수의 길이가 제한되어있다. 가장 긴 정수 표현방법인 longlong으로 했을때 8byte이므로.... 따라서 문제에서는 이를 n으로 나눈 나머지를 구하라 와 같은 방식으로 출제하게 된다. 흔히 %를 사용하는 modular. * 이러한 유형의 문제를 풀때 알아두면 좋은 공식 덧셈 : (A+B)%C = (A%C + B%C)%C 곱셈 : (A*B)%C = (A%C * B%C)%C 뺄셈 : (A-B)%C = ((A%C)-(B%C)..
2020.04.17 -
문제 링크 : https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 일단 이 문제를 풀기 위해서는 버블정렬을 알아야했다. 그래서 버블정렬에 대해 먼저 정리해 보았다. https://infinitt.tistory.com/228 버블 정렬 (bubble sort) * 버블정렬의 개념 두 인접한 원소를 검사하여 정렬하는 방법을 말한다. 시간 복잡도는 느리지만, 코드는 단순하다. 교환정렬의 일부에 속한다. 원소가 이동하는 모습이 거품..
백준(boj) 파이썬 - 1377 번 : 버블 소트문제 링크 : https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 일단 이 문제를 풀기 위해서는 버블정렬을 알아야했다. 그래서 버블정렬에 대해 먼저 정리해 보았다. https://infinitt.tistory.com/228 버블 정렬 (bubble sort) * 버블정렬의 개념 두 인접한 원소를 검사하여 정렬하는 방법을 말한다. 시간 복잡도는 느리지만, 코드는 단순하다. 교환정렬의 일부에 속한다. 원소가 이동하는 모습이 거품..
2020.04.13 -
문제 링크 : https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1
백준 (boj) 파이썬 - 2775 부녀회장이 될테야문제 링크 : https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1
2020.03.27