2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 처음에는 별생각없이 풀었고, 나중에 다들 map 을 쓴다는걸 알게되어서 추가하였다. 두가지 버전 모두 첨부한다. map(X) #include #include int main() { int N; bool visited[1000] = {false, }; std::vector input; std::vector output; std::cin >> N; std::string temp; // 입력 로직 for(int i = 0; i < N; ++i) { s..
Algorithm
14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 해당 문제에 대해서 여러 풀이가 존재하지만, 이 풀이가 가장 좋아보이기에 주석을 달아 포스팅 해 본다. 해당문제에서 명심해야 할 점은 그냥 최고 급여만 출력하면 된다는 점이다. 날짜는 기록할 필요도 없다. 힌트는 '거꾸로' 계산하는 것이다. 예로 문제 내용을 보면 7일과 6일은 근무일을 넘어가기에 계산에 포함시켜야될 필요도 없다. 5일 = 15 O 4일 = 20 + 15 O 3일 = 10 + 20 + 15 O 2일 = 20 < (10 + 20 + 15) X 1일 = (10 + 20 + 15) == (10 + 20 + 15) O 따라서 최고로 나올 수 있는 값은 45 이다. 위 지식을 기반으로 아래 코..
1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS, BFS 관련된 문제로 간단한 문제이다. 해석은 주석으로 기재 해 두었으며 코드의 흐름따라 주석과 함께 코드를 읽어보면 쉽게 이해가 될 것이다. #include #include // 이론상 정점의 개수는 1,000 개 이며 1 < N < 1000 이므로 1001 지정. // 간선의 개수는 10,000 개 미만임. // map 을 기준으로 1,000 x 1,000 = 1,000,000 의 간선 지정이 가능. #defin..
점화식을 구하는 방법에는 총 3가지가 존재한다. 재귀 트리 (Recursion Tree) 치환법 (Substitution method) 마스터 방법 (The Master method) 이 중 치환법의 경우 제한적으로만 사용 가능하기에(추측을 통한 방법이다.) 일반적으로 재귀 트리, 마스터 방법을 주로 사용한다. 1. 점화식이란? 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식. 2. 마스터 방법이란? 시간 복잡도를 계산하는 $Big - O$(worst) 표기법을 보면 $$ O(1), O(n), O(n\,log\,n), O(n^{3}), etc... $$ 이러한 대표적인 Big-O 표기법으로 표현될 수 있는 대다수의 식들은 간편하게 구할 수 있지만(반복문이 중첩으로 몇개인가 등.) 그렇지..
Loop Invariant 는 프로그램 구동시 알고리즘내의 반복문의 정확성을 증명하기 위해서 사용된다. 그 조건으로 초기조건, 유지조건, 종료조건이 존재한다. 각각 아래와 같은 의미를 갖는다 초기조건(Initialization) : Loop 가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이여야 함. 유지조건(Maintenance) : 반복 시작전 불변성이 참이었다면, 다음 반복 시작 전에도 계속 참이여야 함. 종료조건(Termination) : 루프가 종료될 때 그 불변식이 알고리즘의 타당성을 보이는데 도움이 될 유용한 특성을 가져야 함. 추가로 Quick Sort 의 동작원리상 partitioning이 발생한다. 이는 Quick Sort 내에서 Pivot 을 선택하고 재정렬 하는 과정을 의미하며. ..
15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 n 과 m 을 입력받아.자연수 $1 \sim N$ 까지의 자연수 중 중복 없이 이뤄진 수열 $M$ 개를 도출한다. 설명이 조금 애매한데, 예제를 보면 쉽게 이해가 가능하다. 엄밀히 말해 $1 \sim N$ 까지의 자연수 중 $M$ 개로 이뤄진 수열의 '모든 조합' 을 찾는 것이다. #include int n, m; int arr[9] = { 0, }; bool visited[9] = { 0, }; void DFS(int cnt) { // cnt 와 m..
1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 내용은 한번 읽으면 모두 파악할 수 있을정도로 간단하다. 그런데 난이도는 골드 1 티어로 생각보다 높은편에 속한다. 1. 헤딩 #include #include int N; long long zero = 0; long long one = 0; long long two = 0; long long three = 0; long long four = 0; long long five = 0; long long six = 0; long long seven = 0; long long eight = 0; long long nine = 0;..
2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 이 문제는 생각보다 쉬운데, 난 많이 돌아서 풀었다. 신발끈 공식을 적용하지 않은 풀이 방법이다. 1. 그냥 풀어 보았다 #include #include #include struct Point { public: int x; int y; }; std::vector dots; int count; // 2차원 평면공간서 두 점의 거리를 구합니다. double getDistanceBetweenPoints(Point d1, Point d2) { return std::sqrt(std::pow((d2..
문제 설명 백준 1305번 문제는 다음과 같다. 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 문제에 관해 간략히 해설하자면, 흔히 보는 전광판에서 글자가 돌아가며 출력될 때, 특정 순간에 전광판을 포착했을 때 전광판은 특정 문자열로 구성되어 있을 터인데, 전광판 사이즈보다 글자 수가 적다면, 특정 글자가 반복될 것이다. 이 때, 최소 str.length() 가 얼마인지 return 하면 되는 간단한 문제이다....... 간단한 문제라고 생각했었는데, 생각보다 복잡하였다. 풀이 시행착오 이 문제의 경우 KMP 알고리즘에서 사..
19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 이전부터 비트마스킹에 대해서 좀 무시하는 경향이 있었다. 때문에 비트마스킹으로 처리할 수 있는 문제도 굳이 우회해서 처리하곤 했는데, 이번 문제에서 비트마스킹의 필요성을 느껴 배워서 코딩 하였다. 삽질 원래 필자가 생각했던 방법은 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ..
