이것저것

https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓..

DFS/BFS 란 DFS/BFS는 그래프를 순회할 때 사용되는 방법이다. DFS는 Depth-First Search, 깊이우선탐색이라는 뜻이고, BFS는 Breadth-First Search, 너비우선탐색이라는 뜻이다. DFS는 한 정점에서 연결되어 있는 정점 중 한 정점을 우선적으로 방문한다. 즉, 이미 방문한 정점이 나올 때까지 최대한 깊게 방문한다. 반대로 BFS는 한 정점에서 연결되어 있는 모든 정점을 차례로 방문한다. DFS/BFS 구현 DFS는 재귀를 활용해서 구현하는 것이 편리하다. 더 방문할 정점이 없을 때 뒤로 돌아가서 방문할 다른 정점은 없는지 탐색하는데 재귀를 이용하면 이를 자연스럽게 구현할 수 있다. BFS는 큐를 활용해서 구현하는 것이 편리한데, 인접한 정점들을 큐에 넣고 저장해야..

이분탐색이란? 보통 간단하게 배열을 탐색하고자 한다면 선형탐색 (Linear Search)를 많이 사용하곤 한다. 하지만 배열의 길이가 굉장히 길거나 배열을 여러번 탐색해야한다면 선형탐색은 매우 느리다. 선형탐색보다 탐색시간을 조금더 줄일 수 있는 것이 바로 이분탐색 (Binary Search) 이다. 이분탐색은 탐색할 배열의 중간의 값을 확인하여 탐색 범위를 절반씩 줄여나가며 탐색하는 알고리즘이다. 예를들어, [1,3,5,7,9] 인 배열에서 7을 찾는다고 하면 check 함수를 다음과 같이 설정하고 [check() = 7보다 크거나 같은 수이면 True, 그렇지 않으면 False] 배열의 중간값인 5를 먼저 확인한다. check(5) = False 이므로 5보다 배열 왼쪽에 있는 1, 3은 확인하지 ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 베이직한 다이나믹 프로그래밍(DP) 문제로 DP 개념을 이해하기에 좋다. [문제 풀이] 문제의 조건을 간단히 표현하면 다음과 같다. (조건 1) 계단은 1칸 또는 2칸만 올라갈 수 있다. (조건 2) 1칸씩 3번 연속 올라갈 수 없다. (조건 3) 마지막 계단은 반드시 밟아야한다. 이 문제는 각 계단마다 해당 계단에 도착할 때까지 얻을 수 있는 최대 점수를 구하면 된다. 이렇게 마지막 계단에서의 최대 점수를 ..

다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍이라고 쓰면 좀 길어서 줄여서 DP라고도 많이 부른다. 이 글에서도 줄어서 그냥 DP라고 적겠다. DP 문제를 여러 작은 문제(subproblem)들로 나누고 작은 문제의 계산결과를 이용하여 다음 작은 문제의 결과를 찾아가는 것을 반복하여 최종 정답을 찾아가는 알고리즘이다. DP 문제를 푸는 과정은 다음과 같다. 문제의 해답을 찾기 위한 문제풀이과정을 생각한다. 문제풀이 과정 중 반복되는 연산은 결과값을 메모리에 저장하고 이를 다음 연산에 이용하도록 한다. (메모이제이션) 코드를 작성하고 해답을 찾는다. 아래글의 예시를 보면 DP가 어떤 알고리즘인지 어떻게 풀어야하는지 감을 잡기가 쉽다. https://hojun.xyz/13 [백..

이 글은 아래의 구글 C++ 스타일 가이드의 명명법을 번역, 요약한 것이다. 꼭 이렇게 변수이름을 지어야한다는 법은 없다. https://google.github.io/styleguide/cppguide.html#Naming Google C++ Style Guide Google C++ Style Guide Background C++ is one of the main development languages used by many of Google's open-source projects. As every C++ programmer knows, the language has many powerful features, but this power brings with it complexity, which in ..

이 문제는 이분탐색을 활용하는 문제다. 이분탐색을 통해 가장 긴 조각의 최소값을 찾을 수 있다. 1~L(통나무전체길이) 까지의 길이 중 검사할 길이를 이분탐색으로 정하고 통나무의 가장 긴 조각이 이보다 작은지 검사해서 가장 긴 조각의 최소값을 찾으면 된다. 그런데 통나무의 모든 조각이 특정 길이보다 작은지 검사할 수 있는 방법이 생각이 안났다. 그래서 아래 질문 글의 코드를 참고하여 그 방법을 알아보았다. https://www.acmicpc.net/board/view/51740 간단하게 말하면 그냥 한쪽끝에서 통나무조각이 검사하는 길이에 최대한 가깝게 자르면 된다. 처음에는 잘 이해가 안됐는데 생각보다 간단했다. 그림과 같이 길이가 L인 통나무가 있고 통나무의 모든 조각이 S보다 작은지 확인해보자 x <..

float 숫자는 C/C++ 코드에서 float var0 = 1.2f 와 같이 f를 붙여 나타낸다. 여기서 소수점 앞뒤의 0은 생략 가능하다. 1.0f = 1.f 0.1f = .1f 와 같이 두가지 방식으로 나타낼 수 있다.