알고리즘 문제풀이/백준
-
[백준/BOJ] 1926번 그림 (C++)알고리즘 문제풀이/백준 2021. 1. 9. 02:21
www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net BFS 유형의 문제였습니다. 프로그래머스의 카카오프렌즈 컬러링북 문제와 거의 동일한 문제입니다. 배열을 탐색하면서 탐색이 완료된 곳의 값을 0으로 바꿔줌으로써 따로 방문 배열을 두지 않았습니다. #include #include using namespace std; int n, m; int map[501][501]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int..
-
[백준/BOJ] 1158번 요세푸스 (C++)알고리즘 문제풀이/백준 2021. 1. 8. 20:03
www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 분류는 큐를 이용하라고 되어있었지만, 저는 삭제 작업에 유리한 리스트 자료구조를 이용하여 문제를 해결했습니다. 리스트에 1번부터 n번까지 값을 넣고, 리스트가 빌 때까지 k - 1번마다 현재 이터레이터가 가리키는 원소를 벡터에 넣고 그 값을 삭제하는 과정을 반복하면 됩니다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n, k; cin >..
-
[백준/BOJ] 5397번 키로거 (C++)알고리즘 문제풀이/백준 2021. 1. 8. 20:01
www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net 리스트 자료구조를 이용하는 유형. 백준 1406번 문제를 해결했다면 어렵지 않게 풀 수 있는 문제입니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; while(n--) { string s; cin >> s; list li; list::i..
-
[백준/BOJ] 1406번 에디터 (C++)알고리즘 문제풀이/백준 2021. 1. 8. 19:50
www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 리스트 자료구조에 익숙해질 수 있는 문제였습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); string s; int n; cin >> s >> n; list li; for(int i = 0; i < s.size(); i++) { li.push_back(s[i]); } lis..
-
[백준/BOJ] 2164번 카드2 (C++)알고리즘 문제풀이/백준 2021. 1. 8. 01:11
www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 분류는 큐를 이용하는 걸로 되어있는데, 덱을 이용해서 해결했습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n, answer; cin >> n; deque dq; for(int i = 1; i 1) { dq.pop_front(); dq.push_back(dq..
-
[백준/BOJ] 4949번 균형잡힌 세상 (C++)알고리즘 문제풀이/백준 2021. 1. 8. 00:41
www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 스택을 이용하는 문제 닫힌 괄호 ')' 혹은 ']'를 만났을 때, 스택이 비어있거나 스택의 top이 짝이 아니라면 무조건 답이 될 수 없으므로 flag 변수를 false로 바꾸고 break 해줘야 합니다. 또한 모든 탐색이 끝나고, 스택에 원소가 남아있으면 이것 역시 답이 될 수 없으므로 flag를 flase로 바꿔주는 것을 주의해야합니다. #include #include using namespa..
-
[백준/BOJ] 10773번 제로 (C++)알고리즘 문제풀이/백준 2021. 1. 7. 23:37
www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 기초 스택 문제 #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int k; cin >> k; stack s; while(k--) { int n; cin >> n; if(!s.empty() && n == 0) s.pop(); else s.push..
-
[백준/BOJ] 3273번 두 수의 합 (C++)알고리즘 문제풀이/백준 2021. 1. 7. 23:12
www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 정렬 + 투포인터 유형의 문제 수열을 입력받아 정렬한 후, 두개의 포인터를 각각 인덱스 0번과 n - 1번에 가리키게 한 후 다음과 같이 분기를 둡니다. 1. 둘의 합을 x와 비교하여 같으면 head와 tail 모두 1씩 증가 후, answer 1 증가 2. 둘의 합이 x보다 크면 tail 1 감소 3. 둘의 합이 x보다 작으면 head를 1 증가 #inc..