해당 문제는 골드 3 티어이지만, 나는 동의하지 않는다.골드 2티어에서 골드 1티어까지 부여할만한 문제라고 생각한다.문제 자체를 이해하는 과정이 직관적이지 않기에다른 골드 3 티어 문제보다 난이도가 높다고 생각한다.#include #include #include #include class baekjoon_17142{public: int N, M; int blank_count{}; std::vector> loc_virus; // 바이러스의 위치를 기억할 벡터 std::vector> content; int directions[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}; // 동서남북 const int MAX_INT = 2147483647; // 모든 가능한 조합을 저장할 이..

해당 문제는 삼성 SW 역량 테스트 에서 출제된 문제로골드 3 티어의 적절한 난이도를 지니고 있는 문제이다. 2차원 벡터를 기준으로 각 행, 열이경사로를 설치하여 '지나갈 수 있는 길인지' 구하는 문제이다. #include #include #include class baekjoon_14890{public: int N, L; bool constraint(const std::vector& line) { int value_before = line[0]; int limitPoint = 0; for (int i = 1; i = 2) return false; // 현재값이 이전 값보다 1 작을 경우. ..

해당 문제는 BFS, DFS 를 통해 해결할 수 있는 문제이다.난이도는 실버 2 티어이다. 연습하기 좋은 문제라고 느껴 BFS, DFS 두가지 유형으로 모두 풀어보았다.소스코드에 적절한 주석을 작성해 두었으므로, 보면서 이해하면 좋다. BFS#include #include #include #include class baekjoon_1012_bfs{public: static const int MAX = 50; int field[MAX][MAX]; bool visited[MAX][MAX]; int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 서, 동, 남, 북 int M, N, K; // 핵심은 bfs를 통해서 vi..

백준 1343 문제는 실버 5티어 정도의 문제로 그다지 어려운 문제는 아니다.#include class baekjoon_1343{public: int run() { std::string input; std::cin >> input; std::string result; int count = 0; for (char ch : input) { if (ch == 'X') { ++count; } else if (ch == '.') { // 짝수가 아닐경우 폴리오미노 제작 불가, 종..

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 > temp; input.push_..

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 간의 1의 갭을..