전체 글
LeetCode(1)::Two Sum
문제 Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Given an array of Integers nums and an integer target Return indices of the two numbers such that they add up to target Rules Not use the szme element twice Only one valid answer exists Solution 완전탐색(Brute Force) : 단순 완전탐..
BaekJoon(10989)::수 정렬하기 3
문제 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제파악 오름차순 정렬 수의 개수가 최대 10,000,000개 → 시간초과 주의 수의 범위가 10,000보다 작기 때문에 'Counting Sort' 선택 문제풀이 'Counting Sort'를 이해하고 알고 있다면 쉽게 풀수 있는 문제이다. 나올수 있는 수의 범위가 작다 수의 범위가 자연수로 한정되어 있다. #include #define _CRT_SECURE_NO_WARNINGS using namespace std; int main() { short arr[10001] = ..
정렬 알고리즘이란?(What is Sorting Algorithm?)
Sorting이란, 순서없이 나열된 요소들(elements,key)을 특정한 기준(내림차순 or 오름차순)에 따라 비교하여 재배열(rearrange)하는 것을 말한다. 정렬 알고리즘(Sorting Algorithm) 그렇다면 왜 정렬알고리즘을 사용할까? 정렬알고리즘은 자료탐색에 있어서 필수적이다. 예를 들어, 사전에서 단어를 찾고자 할 때 정렬되어 있지 않다면 찾고자하는 단어를 구하기 까지 오랜시간이 걸리게 된다.(비효율적이며 정보의 양이 많아지면 불가능해진다.) 여러 Sorting Algorithm의 분류와 특징들을 통해 상황에 알맞는… 효율적인 알고리즘을 선택할 수 있어야한다. Sorting 기준 오름차순(ascending) : 요소들이 증가하는 순서대로 재배열 내림차순(descending) : 요소..
Array Initialization(배열 초기화)
Array Initialization C++에서 배열을 초기화 할때 어떻게 해야할까? 일반적으로 배열을 선언하면 기본타입(Primitive type)의 초기값(int → 0)을 가지고 있는 반면 참조타입(Reference type)은 null 값으로 초기화 되어있다. Declaration c++ 에서는 변수의 이름 뒤에 '[]'를 붙여 배열을 선언해주며, 대괄호 사이에 배열의 크기를 지정해 줄 수있다. Initialization 만약 배열의 개수가 적고, 고정된 크기와 그리고 특정 값으로 초기화를 한다면 다음과 같이 초기화할 수 있으며, 모든 배열의 값을 초기화 해준다면 굳이 배열의 크기를 정해주지 않더라도 배열의 크기가 5개로 초기화된다. int arr[5] = {1, 1, 1, 1, 1};//1,1,..
BaekJoon(2798)::블랙잭
문제 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제파악 주어진 N개의 카드에서 3장을 선택하여, 더한 값이 M의 값보다 작으면서 최대값 N개에서 3개를 고른다 → $ _{n} \mathrm{C}_{3} $ M보다 작으면서 최대값의 조건을 만족하는지 확인 문제풀이 이 경우는 단순 완전탐색을 선택하였다. 이유는 문제의 사이즈가 그렇게 크지 않았기 때문이다. $ _{n} \mathrm{C}_{3} $ 에서 n이 500이라면 $500 \times 499 \times 498 = ..
Brute Force Search(완전 탐색)
Brute Force Search 단순하게 컴퓨터의 계산 능력을 이용하여 모든 경우의 수를 구하여 문제를 해결하는 방법이다. 즉, 완전! 모든 경우를 탐색하는 것이다. 즉, 다른 하나의 특정 알고리즘이라고 하기보다는 하나의 탐색 기법(방법)으로 이해하면 된다. 알고리즘 보다는 좀 더 넓은 분류로 볼 수 있는것으로 다음 알고리즘 등이 있다. 단순 완전 탐색 : 반복문과 조건문을 통해 처음부터 끝까지 탐색 비트마스크 : 이진수 표현을 이용 재귀 순열 백트래킹 BFS / DFS 문제를 해결함에 있어서 각 알고리즘에 특성에 맞게 선택하여 문제를 해결하면 된다. 완전 탐색의 특징 일반적으로 완전 탐색을 실전에서 사용하는 경우는 많겠지만 대표적으로 알고리즘 문제를 풀 때 완전탐색을 경험하는 경우가 많을 것이다. 물..
Hanoi Tower(하노이의 탑)
Hanoi Tower(하노이의 탑) 프랑스 수학자 에두아르 뤼카가 클라우드 교수라는 필명으로 발표하였고 그 후 1년 후 헨리 드 파르빌이 다음과 같은 이야기로 하노이 탑을 소개하였다. 인도베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1 큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있습니다. 이것은 신성한 브라흐마의 탑입니다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮깁니다. 이 일..
BaekJoon(11729)::하노이의 탑 이동 순서
문제 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제파악 하노이 탑의 이동 원리 파악 → 출력 하노이 탑의 이동 횟수 → 재귀식을 일반항으로 도출하여 주워진 판의 갯수를 통해 총 이동횟수를 알 수 있다. 문제풀이 하노이 탑의 이동횟수 → $a_n = 2^n-1$ 각 하노이의 마지막 판의 이동을 출력 #include #include using namespace std; void hanoi(int n, int from, int via, int to) { if (n == 1) { printf("%d..
BaekJoon(10872)::팩토리얼
문제 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제파악 팩토리얼 → $n! = 1 \times 2 \times · · · \times n $ 문제풀이 재귀 이용 : $factorial(n)$ → $n \times factorial(n-1)$ #include using namespace std; int factorial(int n) { if (n == 1 || n == 0) return 1; return n * factorial(n - 1); } int main() { int n; cin >> n; cout > n; for(int i = 1; i
BaekJoon(1002)::터렛
문제 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 문제파악 각 터렛에서 근무하는 직원에서 적까지의 거리가 주어짐 → 적이 위치할수 있는 위치는 원이 된다. 즉, 근무하는 직원은 원의 중심, 적의 위치는 원 위에 존재한다. 적이 있을 수 있는 위치는 두 원의 위치관계에 의하여 해결 될 수 있다. 문제풀이 두 원의 위치관계를 조건으로 문제를 해결할 수 있다. 동심원인 경우 완전 동일한 원일 경우 다른 원일 경우 동심원이 아닌 경우 접할경우 두점에서 만날 경우 만나지 않는 경우 #include using namespace std; int main() { int t..