알고리즘/구현(24)
-
[백준/C++] 5525번 IOIOI
문제: www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 문제풀이 IOI가 연속되는 개수를 세서 N에 도달하면 정답 개수를 1개 카운트한다. ex) IOIOIOIOIOI IOIOIOIOIOI IOIOIOIOIOI IOIOIOIOIOI IOIOIOIOIOI 위와 같이 계속 IOI가 연속된다면 그 개수를 센다. 코드 #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N,M; ..
2021.02.25 -
[백준/C++] 1780번 종이의 개수
문제: www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 문제풀이 기준점 x, y와 종이의 변의 길이 N을 매개변수로 하는 함수를 선언하여 재귀방식으로 문제를 해결했다. 기준점과 종이의 나머지 부분을 비교하여 같으면 카운트를 하고 다르면 기준점과 N를 적절하게 나누어 9개의 함수를 호출했다. (9등분) 코드 #include using namespace std; int cntm1 = 0; //-1인 종이 갯수 int cnt0 = 0; //0 종이 갯수..
2021.02.23 -
[백준/C++] 1541번 잃어버린 괄호
문제: www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제풀이 문제의 분류는 그리디 알고리즘이지만 문자열 처리만으로 풀 수 있는 문제였다. 식의 '-' 연산을 만나기 전까지의 수는 계속 더해주고 '-' 연산을 만난 후 부터는 '+' 연산을 만나든 '-' 연산을 만나든 관계없이 빼주면된다. 예를 들어 10+10+10-10+10+10 은 10+10+10-(10+10+10) 즉, 10+10+10-10-10-10 이 된다. 코드 #include using n..
2021.02.22 -
[백준/C++] 1260번 DFS와 BFS
문제: www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제풀이 DFS와 BFS의 구현문제이다. DFS는 재귀함수의 형식으로 구현했고 BFS는 queue를 이용하여 구현했다. 코드 #include #include using namespace std; int N,M,V; int visited[1001] = {0,}; //방문여부 int link[1001][1001] = {0,}; //간선 void init(){ //dfs후..
2021.02.21 -
[백준/C++] 9375번 패션왕 신해빈
문제: www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 문제풀이 해빈이가 입을 수 있는 옷의 경우의 수는 옷의 종류가 상의, 하의, 모자가 있다고 했을때 (상의+1) x (하의+1) x (모자+1) - 1 이다. 여기서 상의, 하의, 모자에 1을 더해준 것은 옷을 입지 않는 경우이고 마지막으로 1을 빼준 것은 해빈이가 세 종류의 옷들 모두 입지 않았을 때를 빼준 것이..
2021.02.16 -
[백준/C++] 11723번 집합
문제: www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제풀이 간단한 구현문제 코드 #include #include using namespace std; vector v(20); //크기 20의 전역 벡터 선언 void add(int); void remove(int); void check(int); void toggle(int); void all(); void empty(); int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int M; ci..
2021.02.04