문제 풀이/백준 알고리즘
[baekjoon 17269] 이름궁합 테스트- 문자열, 구현 (C++)
www.acmicpc.net/problem/17269 17269번: 이름궁합 테스트 시윤이는 좋아하는 이성이 생기면 가장 먼저 이름궁합부터 본다. 이름궁합을 보는 방법은 간단하다. 먼저 이름을 알파벳 대문자로 적는다. 각 알파벳 대문자에는 다음과 같이 알파벳을 적는데 www.acmicpc.net 단순한 문자열, 구현 문제이다. 문자열에 익숙하지 않아서 연습을 해야겠다. #include #include using namespace std; string name1, name2, sumName; int size1, size2; vector num; int main() { ios::sync_with_stdio(false); cin.tie(0); int arr[26] = { 3, 2, 1, 2, 4, 3, 1, ..
[baekjoon 14425] 문자열 집합- 문자열, map (C++)
www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 요즘 map 자료구조를 연습 중이다. 이 문제는 간단한 문제인데 map 자료구조를 사용해서 해당 string key 값을 통해 value값을 비교해서 풀어주었다. #include #include #include using namespace std; int N, M, cnt; string word; int main() { ios::sync_with_stdio(false); cin...
[baekjoon 14502] 연구소 - 그래프탐색(BFS,DFS), 브루트포스
www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 기본적인 그래프 탐색에 벽을 쌓아야하는 경우를 생각해야하는 문제이다. 처음에 문제를 읽고 무작위 벽 3개를 어떤 로직을 통해 세워야할까, 고민을 하다가 입력값의 최대 배열 크기가 8x8 인것을 보고 브루트포스로 모든 경우를 탐색해보면 되겠다고 생각을 했다. 벽을 세우는 케이스는 크게 두가지 인 것 같다. 1. 그래프를 입력받을 때 벽도 없고, 바이러스도 없는 x,y 좌표값을 따로 vector에 보관해두고 이 벡터에서 3가지..
[baekjoon 1922] 네트워크 연결 - 최소 스패닝 트리(크루스칼, Union-Find)
www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소 스패닝 트리를 만들어서 간선들의 합이 최소가 되게끔 풀면 된다. 쓰인 알고리즘은 크루스칼 알고리즘과 Union-Find 알고리즘이다. 크루스칼 알고리즘을 통해 모든 Vertex를 최소의 비용으로 연결을 시키면 되고, 연결 하는 도중 싸이클이 생기지 않도록 Union-Find 알고리즘을 사용하면 된다. - 최소 스패닝 트리란? : 우선 스패닝 트리란 트리의 모든 노드를 포함하고, 노드끼리 연결이 되어있으며 싸이클이 발생하지 않는 트리다. : 여기에 최소의 뜻을 더하면 노드끼리 연결하되, 최소의 비..
[baekjoon 2468] 안전영역 - 그래프탐색(BFS, DFS)
www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 기본적으로 배열에 데이터를 받아서 그래프 탐색을 수행하는 문제였다. 다만 문제 마지막 조건에 아무 지역도 물에 잠기지 않을 수 있다는 조건으로 바로 맞추진 못했다.. #include #include using namespace std; int bound[101][101], N, height, resultMax, xmove[4] = { 1, -1, 0, 0 }, ymove[4] = { 0, 0, 1, -1 }; bool..
[baekjoon 14438] 수열과 쿼리 17 - 세그먼트 트리
www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net 기본적인 세그먼트 트리 문제. 최근에 전공 기말프로젝트 하느라 문제를 못풀었더니 바로 풀리진 않았다. 함수는 init, 구간의 최솟값을 저장해주는 minTree, update 함수로 구성하였다. update함수를 구현할때 diff값을 이용해서 (기존 값 - 변경하려는 값) 했었는데 곱셈이나 나눗셈 등 애매한 경우가 있어서 아예 ta..