프로그래밍
-
백준 14500 (테트로미노)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 15. 19:05
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 풀이 DFS를 사용하여 풀이하면 되는 문제이다. 1. 최대 입력값은 500이기 때문에 배열의 크기는 500으로 할당 2. ㅗ 도형을 제외한 나머지 도형은 위, 아래, 우측, 좌측 으로 이동하며 DFS를 돌리면 도형이 나온다. EX ) 우측, 우측, 우측, 우측 -> " ---- " 과 같이 예제에서 주어지는 도형 중 " ㅗ " 자 도형을 제외한 모든 경우의 수는 위, 아래, 왼쪽, 오른쪽 방향으..
-
백준 12100 ( Easy)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 14. 15:05
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 풀이 방법 1. 오른쪽, 왼쪽, 위, 아래 방향으로 map 배열의 요소를 이동시켜주는 함수 2. 위에서 만든 함수의 각 동작을 DFS로 완전탐색 시키며 중복순열을 이용한다. ( 위, 위, 위, 위, 위 -> 위 위 위 위 아래 -> 위 위 위 위 왼 -> 위 위 위 위 오 ) 3. max 회전 횟수인 5번일때 map 배열을 최대값 추출 후 최대값 갱신 위의 문제는..
-
백준 (1107) 리모컨컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 9. 15:00
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net 로직 2가지 경우의 수를 구해야 한다. 1. 100 에서 n의 값을 뺀 절대값 2. DFS를 사용하여 고장난 리모컨 채널을 제외환 모든 채널의 경우의 수를 만들면서 n과 모든 채널의 값을 뺀 절대값 1번과 2번의 최소 절대값을 비교하여 작은 수가 정답이 된다. 소스 #include #include using namespace std; int n; int nSize; int re..
-
N개의 수에 대한 최대공약수 구하기컴퓨터 공학 기초/알고리즘 ( algorithm ) 2020. 4. 22. 20:19
유클리드호제법을 이용하여 먼저 0번째와 1번째의 최대공약수를 구한뒤 구한 공약수와 다음 번째 수의 최대공약수를 구하는 방식으로 요소의 마지막 즉 N번째 까지 연산을 수행하게 되면 N개의 숫자의 공통 된 최대공약수를 구할 수 있다. 풀이 // HelloNew_C+.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다. // #include "stdafx.h" #include #include #include #include #include int gcd(int a, int b){ int tmp; while (b > 0){ tmp = a; a = b; b = (tmp % a); } return a; } using namespace std; int main(){ int n, s, nData; int res ..
-
팩토리얼 0의 개수 구하기컴퓨터 공학 기초/알고리즘 ( algorithm ) 2020. 4. 22. 13:08
팩토리얼이란 계승을 의미한다 예를들어 10의 팩토리얼은 1 * 2 * 3 * 4 * 5* 6 * 7 * 8 * 9 * 10 을 의미한다. 현재 구하고 싶은 값은 10 팩토리얼에서 나오는 연속된 0의 갯수이다. 예를들어 10팩토리얼의 값 3628800 이있다면 여기서 가장 뒤의 연속된 0 의 개수를 구하는 것이다. 뒤 자리가 0이 나오기 위해서는 값에 10이 더해지는 수 밖에 없다. 따라서 2 * 5 가 몇번나왔는지만 확인하면 된다. 해결을 하기 위해서는 2가지 방법이 있다. 1. 3628800 을 소인수 분해 하여 총 5가 몇개나오는지 확인하는 방법이 있다. 2. 10의 값을 5로 나누고 몫의 값을 파악하는 방법 + 25 * 1, 25 * 2 와 같이 5 * 5 가 두번 나올 경우를 파악 // Hello..
-
최대공약수 (유클리드호제법) 최소공배수컴퓨터 공학 기초/알고리즘 ( algorithm ) 2020. 4. 21. 12:42
최대공약수란 ? 어떤 수 A 와 B가 있을 때 A 와 B 서로의 약수에서 공통된 수들 중 가장 큰 수를 의미한다. 가장 간단하게 구할 수 있는 방법은 A와 B중 작은 값을 구하여 2부터 작은 값 까지 순회하면서 A와 B의 나머지 연산을 통해 구하는 방법이 있다. 해당 방법은 시간복잡도 o(N) 이라는 시간복잡도를 가지고 있으며 해당 방법보다 빠른 유클리드 호제법이라는 알고리즘이 존재한다. 유클리드호제법의 로직은 다음과 같다. int gcd(int a, int b){ if (b == 0){ return a; } else { return gcd(b, (a%b)); } } int main(){ int aNum, bNum; cin >> aNum; cin >> bNum; cout (16, (24 % 16)) ->..
-
Stack 을 이용한 알고리즘컴퓨터 공학 기초/알고리즘 ( algorithm ) 2020. 4. 13. 13:20
이번 포스트에서는 스텍 자료구조를 활용하여 문제를 해결한다. 스텍의 특성은 선입후출의 특성을 가지고 있다. 문제 1. 스텍 구현 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 해결 // Data_struct_c+.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다. // #include #include #include using namespace std; class STACK{ // ..
-
디폴트 복사생성자의 단점카테고리 없음 2020. 4. 7. 00:12
복사생성자의 단점 복사생성자는 디폴트 생성자와 같이 Class를 만들 때 직접 정의하지 않아도 컴파일러가 알아서 디폴트 복사생성자를 생성해 준다. 하지만 이런 디폴트 복사 생성자는 한가지 단점을 가지고 있는데 그것이 바로 디폴트 복사 생성자는 얕은 복사를 한다는 점이다. 그렇다면 얕은 복사란 무엇일까 ? 얕은 복사 // HelloNew_C+.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다. // #include "stdafx.h" #include #include using namespace std; class Ctest { public: // 디폴트 생성자 Ctest(int n){ p_A = new int; *p_A = n; } // 복사 생성자 Ctest(Ctest &rhs){ this->p_..