알고리즘

문제 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이현재 채울 칸의 범위를 x1, x2, y1, y2로 설정, 상우하좌의 순서로 해당 칸을 채운다.x1의 y1부터 y2y2의 x1부터 x2x2의 y2부터 y1y1의 x2부터 x1현재 칸을 채웠으면 x1, x2, y1, y2를 조절코드#include #include using namespace std;vector> solution(int n) { vector> answer; answer.resize(n); for (auto& v : answer) { v.resize(n); } int x1 = 0; int x2 = n - 1; int y1 = 0; in..

문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이다익스트라무지와 어피치가 S에서 경유지 I까지 같이 이동한다. 무지와 어피치가 따로 A, B로 이동한다. 한명은 I에서 A로, 한명은 I에서 B로 이동한다.즉, 최소 거리는 S -> I, I -> A, I -> B, 세 경로의 합의 최솟값이다. S, A, B 세 노드에서 다른 노드로의 최소 거리만 있으면 문제를 풀 수 있다.현재 그래프는 양방향 경로이기 때문에, 다익스트라는 S, A, B 총 세 번만 실시해도 문제를 풀 수 있다.코드#include #include #include #include #incl..

문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이문자열 dic 안에서 spell의 유무를 판단하면 된다. s.find(c) == string::nposstring s에서 string c를 찾을 수 없다면 string::npos를 반환한다.  코드#include #include #include using namespace std;int solution(vector spell, vector dic){ int answer = 2; for (const auto& s : dic) { bool flag = true; for (const auto& c : sp..

문제https://www.acmicpc.net/problem/7562풀이너비 우선 탐색 간단한 BFS 문제로 기존 문제와 다른 점은 목적지에 도착할 때까지 걸린 count가 필요하다. bool 배열로 해당 칸의 방문 여부를 판별하는 것보다 int 배열로 해당 칸에 도착할 때까지 걸린 count를 기록한다. 방문 여부는 해당 칸의 count가 0인지를 확인하면 된다. 코드#include #include #include #include using namespace std;int T;int I;// visited 배열이 아닌 int로 count와 방문 여부를 동시 관리int moveCount[300][300];int moveX[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };int moveY[..

문제https://www.acmicpc.net/problem/9020풀이수학, 에라토스테네스의 채, 소수 판정 소수 판정에는 에라토스테네스의 채를 사용하여, 알고리즘 시작 전에 10000까지 소수를 판정해 둔다. 두 소수의 차이가 가장 적은 것을 출력해야 하므로, 시작 값(start)을 n / 2로 설정하여, 중앙에 가장 가깝도록 한다. start를 1씩 감소 시키면서, n - start가 소수라면 해당 값이 차이가 가장 적은 소수이므로 이를 출력하고 알고리즘을 중지한다. 처음에는 두 포인터로 문제를 해결하였지만, 위의 방법이 더 효율적이였다. 코드방법 1#include #include using namespace std;const int MAX = 4'000'001;bool prime[MAX];// 에..

문제https://www.acmicpc.net/problem/1065풀이수학, 브루트포스 알고리즘 입력되는 수는 1000 이하의 수이다. 100 미만의 수는 모두 한수를 이루기 때문에, 100 미만의 수가 들어온다면 N을 출력한다.0 ~ 9까지의 수는 그 자체로 등차수열이다.10 ~ 99까지의 수는 수열을 이루는 수가 2개이기 때문에 등차수열이다.100 이상의 수가 들어온다면 100부터 N까지 아래의 검사를 실시하여, 통과된 개수를 출력한다.현재 수의 각 자리수를 구한다. 연속된 자리수 사이의 차이가 일치한다면 한수이다. 코드#include using namespace std;int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.t..

문제https://www.acmicpc.net/problem/2512풀이이분 탐색 간단한 이분 탐색 문제. 상한액을 이분 탐색으로 찾으면 된다.start를 1, end를 예산요청액 중 최댓값으로 설정한다.mid를 (start + end) / 2로 설정한다.mid를 상한액으로 설정했을 때의 현재 합계를 구한다.mid보다 작은 예산 요청액은 그대로 sum에 더한다.mid보다 큰 예산 요청액은 mid만큼을 sum에 더한다.sum과 M을 비교하여 start와 end 값을 조정한다. start가 end를 넘을 때까지 진행한다.코드#include #include #include #include #include #include #include #include #include #include #include #incl..

문제 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 풀이 백트래킹, 브루트포스 알고리즘 연산자의 수는 N - 1로 어떤 연산에서 사용되지 않는 연산자를 생각할 필요가 없고, 전체 연산자를 어떤 순서로 사용할지 정하면 된다. 재귀 함수에서 현재까지 연산한 값(current)과 사용할 피연산자(operands[depth + 1]와 각 연산자의 남아 있는 수를 인자로 받는다. current와 피연산자를 남아 있는 연산으로 계산하고, 사용한 연산자를 1 줄여..

문제 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 구현, 시뮬레이션 vector(sharks)에 상어를 입력받는다. 보드 배열(board)의 각 칸에는 현재 위치한 상어의 index가 입력된다. 상어가 위치해 있지 않은 경우 -1이 기본값으로 설정된다. 다음 보드(next_board)의 상태를 나타내는 배열을 만든다. 마찬가지로 기본값은 -1로 설정된다. 다음의 작업이 C번 실행된다. 낚시왕이 위치한 열에 있는 상어 중에서 행이 0과 가장 가까운 상어를 잡는다. 남아 있는 상어의 위..

문제 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 구현, 시뮬레이션 풀이 1 현재 칸에서 왼쪽에 위치한 블록들 중 최고 높이와 오른쪽에 위치한 블록들 중 최고 높이를 구한다. 현재 칸에서는 최고 높이들 중에서 작은 값과 현재 높이의 차만큼의 물이 찬다. 풀이 2 한 행에서 물이 차는 칸을 계산한다. 현재 행에서 블록과 블록으로 막히는 칸들은 물이 차는 칸이다. 행에서 0번 열부터 시작하여 W - 1번 열까지 탐색한다. 처음 블록이 등장했다면 flag를 true로 설정한다. flag가 ..