알고리즘/백준

문제 풀이 BFS를 이용하여 해결한다. 이전에 이동했던 위치인 visited를 큐에 넣을 때 true로 세팅하지 않고 꺼낼 때, 세팅하여 중복된 경로도 추가될 수 있도록 한다. 이동할 수 있는 방법 별로 큐에 넣는다. 코드 #include #include #include #include using namespace std; typedef struct { int X; int dist; }type; queue q; bool visited[100002]; map answer_map; int main() { int N, K; int answer = INT_MAX; cin >> N >> K; q.push({ N, 0 }); visited[N] = true; while (!q.empty()) { type curre..

문제 풀이 바이토닉 부분 수열의 가운데 값을 찾는 것으로 생각하는게 쉽다. 수열의 앞에서부터 탐색하여 증가하는 값을 cache로 두고, 마찬가지로 뒤에서 부터 탐색하여 증가하는 값을 cache_reverse로 둔다. cache와 cache_reverse의 합이 최대가 되는 인덱스를 찾는다. 코드 #include using namespace std; int main() { int N; int A[1001]; cin >> N; for (int i = 1; i > A[i]; } if (N == 1) { cout = i; --j) { if (A[i] > A[j]) { maxi = max(maxi, cache_reverse[j]); } } cache_reverse[i] = maxi + 1; } // 가장 긴 바이..

문제 풀이 N이 상당히 크기때문에 분할 정복으로 푼다. N이 짝수 일 경우 N / 2와 N / 2 N이 홀수 일 경우 N - 1과 N 행렬을 곱하면서 수가 점점 커지기 때문에 곱하면서 MOD연산이 필요하다. 코드 #include #include #include #define MOD 1000 using namespace std; int N; long long B; map cache; vector matrix; vector mulMatrix(vector m1, vector m2) { vector outMatrix; outMatrix.resize(N); for (int i = 0; i < N; ++i) { outMatrix[i].resize(N); } // m1과 m2 행렬의 곱 for (int i = 0; ..

문제 풀이 전체 입력받은 문자열을 처음부터 끝까지 폭발 문자열이 없을 때까지 검색을 반복하면 시간초과가 된다. answer 문자열을 따로 두어, 전체 문자열의 0번 인덱스부터 검사하여 answer문자열이 폭발 문자열의 길이보다 길어진다면 answer의 끝 부분을 폭발 문자열과 비교한다. answer의 끝 부분이 폭발 문자열이라면 삭제한다. 코드 #include #include using namespace std; int main() { string s; string bomb; cin >> s >> bomb; string answer; int bomb_len = bomb.length(); for (int i = 0; i < s.length(); ++i) { answer.push_back(s[i]); // ..

문제 풀이 DFS와 백트래킹을 사용한다. 지나온 알파벳을 확인할 vector를 생성하여 다음으로 지나갈 칸을 확인한다. 코드 #include #include #include using namespace std; int R, C; char board[21][21]; int move_x[4] = { 0, 0, 1, -1 }; int move_y[4] = { 1, -1, 0, 0 }; int answer = 0; void dfs(int x, int y, int dist, vector& alphabets) { answer = max(answer, dist); bool flag = false; for (int i = 0; i < 4; ++i) { int next_x = x + move_x[i]; int next_..

문제 풀이 다익스트라로 노드 간의 최단 거리를 구한다. 2가지 경로값 중 작은 값을 출력한다. 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 다익스트라는 1, v1, v2 총 3번만 실행하면 답을 구할 수 있다. 코드 #include #include #include using namespace std; vector edges; vector dists; void dijkstra(int start) { dists[start][start] = 0; priority_queue pq; pq.push(make_pair(0, start)); while (!pq.empty()) { int current_node = pq.top().second; int current_dist = (-1) * pq...

문제 풀이 `Union-Find` 알고리즘을 사용한다. 파티에 참가한 사람 별로 부모노드를 설정하여 서로간의 부모노드를 비교하여 같은 집합에 속해있는지 확인한다. 진실을 아는 집합 내의 사람이 파티에 속해있는 파티에서는 거짓말을 할 수 없다. 코드 #include #include using namespace std; vector knowns; vector parties[51]; int parent[51]; // 노드의 부모 노드를 반환 int getParent(int n) { if (parent[n] == n) { return n; } return getParent(parent[n]); } // 노드의 부모를 서로 연결하여 같은 집합에 속하게 한다. void Union(int n1, int n2) { n..

문제 풀이 DP와 그래프 탐색으로 풀 수 있다. 코드 그래프 탐색 #include #include #define VER 0 #define HOR 1 #define DIA 2 using namespace std; typedef struct { int x; int y; int dir; }type; // 파이프의 방향에 따른 이동 위치 vector move_x = { {0, -1, 1}, {-1, 1, 1}, {0, 1, 1} }; vector move_y = { {1, -1, 1}, {-1, 0, 1}, {1, 0, 1} }; // 파이프의 방향과 이동 위치에 따른 검사 위치 int check_x[3] = { 1, 1, 0 }; int check_y[3] = { 0 ,1, 1 }; //vector check..

문제 풀이 일반적인 다이나믹 프로그래밍으로 해결하려고 하면 메모리 초과 위의 식을 이용하여 피보나치 수열을 행렬의 거듭제곱으로 계산할 수 있다. 분할 정복을 이용한 거듭제곱으로 해결한다. 코드 #include #include #include using namespace std; #define MOD 1000000007 map cache; vector matrix = { {1, 1}, {1, 0} }; vector mulMatrix(vector m1, vector m2) { vector outM = { {0, 0}, {0, 0} }; outM[0][0] = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % MOD; outM[0][1] = (m1[0][0] * m2[0][1]..

문제 풀이 스택을 이용한다. 피연산자는 바로 answer의 뒤에 추가한다. 연산자는 다음으로 처리된다. 스택이 비어있다면 스택에 연산자를 push한다. 연산자는 스택의 top과 우선순위를 비교하여 자신보다 우선순위가 낮을 때까지 top을 answer의 뒤에 추가하고 스택을 pop한다. 그 후, 스택에 자신을 push한다. ' ( '는 바로 스택에 push한다. ' ) '는 스택에서 ' ( '가 나올때까지 top을 answer의 뒤에 추가하고 스택을 pop한다. 그 후, ' ( '를 스택에서 삭제한다. 코드 #include #include #include #include #include using namespace std; // 연산자 우선순위 unordered_map priority = { {'(', 0..