본문 바로가기

2019/124

백준 14500번 테트로미노 완전탐색(brute-force) 알고리즘 문제 :: 코드자몽 [백준] 14500번 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 풀이 이런 블록 형태의 문제가 나오면 실제로 도형을 그려보면서 문제를 푸는 것이 가장 좋은 방법인 것 같다. 먼저 N*M 크기의 종이 위에 블록 하나만 놓는다고 했으니.. 2019. 12. 23.

백준 2309번 일곱 난쟁이 완전탐색(brute-force) 알고리즘 문제 :: 코드 자몽 완전 탐색 Brute-Force 완전 탐색은 말 그대로 모든 경우의수를 일일이 탐색하여 정답을 찾아내는 알고리즘이다. 가능한 방법을 모두 확인하여 정확도가 높고 강력한 방식이지만, 시간은 다소 오래 걸리는 단점이 있습니다. 그래서 브루트 포스 알고리즘을 사용하기 전에 문제의 가능한 경우의 수를 먼저 계산을 해봐야한다. 컴퓨터가 1초에 대략 1억 번 정도의 일을 할 수 있다고 한다. 효율성을 고려하여 브루트 포스 알고리즘으로 문제를 접근할 경우 기준은 정해주는 것이 좋다. 예를 들어 "천만(10,000,000) 건 이하의 경우 수가 존재할 때만 브루트 포트 알고리즘을 사용하겠다."라는 기준을 정하고 문제를 접근하는 것이 유리하다. [백준] 2309번 일곱 난쟁이 2309번: 일곱 난쟁이 아홉 개의 줄에 걸.. 2019. 12. 23.

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽 소수(Prime Number) 소수는 자신보다 작은 두개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. ex) 5는 5*1 또는 1*5로 수를 곱합 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 소수 (수론) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 좌측은 소수, 우측은 합성수. 소수란 자신보다 작은 두 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1x5 또는 5x1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 .. 2019. 12. 22.

최대공약수(GCD), 최소공배수(LCM) 구하기 유클리드 호제법 알고리즘 :: 코드자몽 최대공약수 GCD(Greatest Common Divisor) 최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다. ex) 72 와 30의 최대공약수는 6이다. 최소공배수 LCM(Least Common Multiple) 최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다. 최소공배수 = 두 자연수의 곱 / 최대공약수 ex) 72 와 30의 최소공배수는 360이다. 유클리드 호제법(Euclidean Algorithm) 2개의 자연수를 받아 최대공약수를 받기 위해 2부터 두 자연수 중 작은 자연수까지 모두 나누어보면서 가장 큰 공약수를 구할 수 있다. 위와 같은 방법으로 문제를 풀면 시간복잡도는 O(N)이 된다. 나쁜 방법은 아니지만 효율을 높이기 위해 유클리드 호제법이란 알고리즘.. 2019. 12. 22.

이전 1 다음

티스토리툴바