목록알고리즘/C++ (56)

수학과의 좌충우돌 프로그래밍

[C++] BAEKJOON 5052번 전화번호목록

5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 www.acmicpc.net Trie 자료구조를 사용하는 문제였습니다. Trie 자료구조란? [Algorithm] Trie 자료구조 KMP 알고리즘 에 이어서 문자열에서 검색에 위한 새로운 방법들을 알아보도록 하겠습니다. 이번에..
알고리즘/C++ 2019. 8. 26. 23:01
[C++] BAEKJOON 8901번 화학제품(ACM-ICPC Daejeon 2011)

문제보러가기 8901번: 화학 제품 문제 상근이는 각기 다른 병에 담긴 세 화학 물질 A, B, C를 가지고 있다. 두 화학 물질을 같은 양만큼 혼합하면, 화학 제품을 얻을 수 있다. A와 B를 혼합하면 AB가 되고, B와 C를 혼합하면 BC, C와 A를 혼합하면 CA가 된다. (A 하나와 B 하나를 혼합하면 AB 하나를 얻게 된다) AB, BC, CA의 가격은 모두 다르다. 따라서, 만드는 화학 제품에 따라서 얻는 이익은 달라진다. 항상 정수 단위 만큼 두 화학 물질을 혼합할 수 있다. www.acmicpc.net 입력으로 주어지는 모든 숫자는 1000이하이기 떄문에 다음과 같이 어렵지 않게 접근하였습니다. ab 혼합물의 수를 0부터 a,b의 갯수의 최소값까지 만들어준다. bc 혼합물의 수를 0 부터 ..
알고리즘/C++ 2019. 8. 2. 21:10
[C++] BAEKJOON 8895번 막대배치(ACM-ICPC Daejeon 2012)

문제보러가기 8895번: 막대 배치 문제 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. 위의 두 배치는 모두 왼쪽에서 봤을 때 막대가 한 개 보이고, 오른쪽에서 봤을 때는 막대가 두 개 보인다. 막대의 개수 n과 왼쪽에서 봤을 때 보이는 막대의 개수 l, 오른쪽에서 봤을 때 보이는 막대의 개수 r이 주어진다. 이때, 이러한 결과를 만 www.acmicpc.net 동적계획법을 사용한 문제였습니다. 먼저 점화식을 세워보도록 하겠습니다. dp[n][l][r] 를 n 개의 막대에 대해, 왼쪽에서 보이는 막대가 l 개, 오른쪽에서 보이는 막대가 r 개인 경..
알고리즘/C++ 2019. 7. 31. 16:54
[C++] BAEKJOON 9455번 박스(ACM-ICPC Daejeon 2013)

문제 보러 가기 9455번: 박스 문제 m행 n열로 이루어진 그리드가 주어진다. 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때 까지 아래로 움직인다면, 박스는 쌓여진 상태가 된다. 그림 (a)의 그리드의 크기는 5행 4열이고, 7칸에는 박스가 들어있다. 모든 박스가 계속해서 아래로 움직이면, 그림 (b)와 같이 변하게 된다. 박스가 움직인 거리는 바닥에 쌓이기 전 까지 이동한 칸의 개수이다. 예를 들어, 맨 왼쪽 열에서 가장 위에 있는 박스가 움직인 거리는 2이 www.acmicpc.net ACM-ICPC 문제라고 하기에 쉽고 간단한 문제 였습니다. 박스는 각 column 에서만 이동을 할 수 있으므로 column 을 기준으로 나눠서 생각해주었습니다. 박스가 있을 경우, 바닥으..
알고리즘/C++ 2019. 7. 26. 02:57
[C++] 이진 탐색 알고리즘

이진 탐색 알고리즘 (Binary Search) 이진탐색의 특징 log N 의 시간복잡도 데이터가 정렬되있는 배열에서만 사용가능 반복문, 재귀함수를 통한 두 가지 방법으로 구현 가능 반복문을 통한 이진 탐색 구현 int search(int *arr, int length, int target) { int start = 0; int end = length-1; int mid = 0; while (start target) end = mid-1; } } return -1; } 재귀함수를 통한 이진 탐색 구현 int recursive_search(int *arr, int start, int end, int target) { int mid = (start+end) / 2; if (start > end) return..
알고리즘/C++ 2019. 3. 26. 00:21
[C++] 최적의 소수찾기, 에라토스테네스의 체

안녕하세요 강민성입니다. 이번 포스팅에서는 소수를 찾는 방법에 대해서 알아보도록 하겠습니다. 소수를 찾는 방법이 여러가지가 있지만 그 중에 가장 효율이 좋은 '에라토스테네스의 체' 에 대해서 알아보도록 합시다. 최적의 소수 찾기, 에라토스테네스의 체 먼저 동영상을 보고 어떠한 원리로 소수를 찾는지 보도록 하겠습니다. 2부터 120까지 수 중 소수를 판별한다고 해보겠습니다. 다음과 같은 알고리즘으로 소수를 찾게 됩니다. 1. 2는 소수이므로 오른쪽에 2를 쓰고 2의 배수들은 소수가 아니므로 체크한다. 2. 다음 숫자를 확인하여 체크가 안되있으면 그 수를 오른쪽에 쓰고 그 수의 배수들은 체크, 체크가 되어있으면 다음 수로 넘어간다. 3. 120의 제곱근까지 다음 과정을 반복한다. 이 알고리즘을 이제 C++ ..
알고리즘/C++ 2019. 2. 8. 14:00
Prev 1 ··· 3 4 5 6 Next

티스토리툴바