알고리즘 문제풀이/백준
-
[백준/BOJ] 2563번 색종이 (C++)알고리즘 문제풀이/백준 2021. 9. 26. 18:09
https://www.acmicpc.net/problem/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 색종이를 붙인 위치 x, y ~ x + 10, y + 10 영역을 2차원 배열의 좌표로 1로 만들어준다. 이 1의 개수가 전체 영역의 넓이라고 할 수 있다. 이때 중복되는 영역은 한번만 셀 수 있도록 현재 2차원 배열 좌표의 값이 1일땐 continue 처리 해준다. #include #include using namespace std; int N, answer; int map[101][101]; in..
-
[백준/BOJ] 1822번 차집합 (C++)알고리즘 문제풀이/백준 2021. 9. 26. 17:33
https://www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소 www.acmicpc.net 이분 탐색을 이용하면 시간복잡도 O(N * logN)으로 해결할 수 있다. 다만 주의할 점은 a 집합에서 교집합 원소를 제거하는 방식으로 문제를 접근하면 원소의 재배치 과정 때문에 TLE이 발생할 수 있다. 그러므로, 이분 탐색을 통해 찾을 수 없는 원소인 경우에 새로운 벡터에 값을 넣는 방식으로 해결하면 된다. #include #include #include ..
-
[백준/BOJ] 6581번 HTML (C++)알고리즘 문제풀이/백준 2021. 9. 25. 22:56
https://www.acmicpc.net/problem/6581 6581번: HTML 원래의 HTML 문서가 입력으로 주어진다. 이 텍스트는 단어와 HTML 태그들로 이루어져 있으며, 태그는 한 개 이상의 공백문자나 탭, 개행 문자 등으로 구분된다. 단어는 연속된 알파벳, 숫자, 또는 www.acmicpc.net #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); string str = ""; string bar = "--------------------------------------------------------------------------------"; int line_..
-
[백준/BOJ] 1919번 애너그램 만들기 (C++)알고리즘 문제풀이/백준 2021. 9. 20. 19:45
https://www.acmicpc.net/problem/1919 1919번: 애너그램 만들기 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs www.acmicpc.net 처음에 map을 2개 정의해서 활용해서 풀이를 시도했는데, map의 값을 빼주는 과정에서 뭔가 내부적으로 동작되는 방식(?)에 의해 원하는대로 작동을 안하는 것 같았다. 그래서 배열 2개를 이용하여 a~z까지 서로 값이 다른 경우 값을 빼주는 방식으로 해결했다. #include #include using namespace std; int check1[26], check2[..
-
[백준/BOJ] 2980번 도로와 신호등 (C++)알고리즘 문제풀이/백준 2021. 9. 19. 02:10
https://www.acmicpc.net/problem/2980 2980번: 도로와 신호등 상근이는 트럭을 가지고 긴 일직선 도로를 운전하고 있다. 도로에는 신호등이 설치되어 있다. 상근이는 각 신호등에 대해서 빨간 불이 지속되는 시간과 초록 불이 지속되는 시간을 미리 구해왔 www.acmicpc.net 현재 시간에서 빨간불이 지속되는 시간 + 파란불이 지속되는 시간을 나눈 나머지가 빨간불이 지속되는 시간보다 작다면 두 값을 빼줘서 시간에 더해줘야 한다. (이것이 빨간불을 기다리는 시간) 그외의 경우는 기다리지 않고 지나갈 수 있으므로 시간을 1씩 더해준다. #include #include #include using namespace std; int main(void) { ios_base::sync_w..
-
[백준/BOJ] 3048번 개미 (C++)알고리즘 문제풀이/백준 2021. 9. 18. 20:48
https://www.acmicpc.net/problem/3048 3048번: 개미 T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다. www.acmicpc.net 벡터를 pair형으로 선언해서 방향도 함께 담을수 있도록 했다. 0은 오른쪽, 1은 왼쪽을 의미한다. 전체 개미를 탐색하면서 현재 개미와 다음 개미의 방향을 비교한다. 서로 마주보는 방향이라면, swap해주고, 다음 비교를 위해 두칸을 이동한다. 아니라면 한칸만 이동하며 다시 위의 과정을 반복한다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(..
-
[백준/BOJ] 10798번 세로 읽기 (C++)알고리즘 문제풀이/백준 2021. 9. 14. 20:51
https://www.acmicpc.net/problem/10798 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); string str[5]; for(int i = 0; i > str[i]; } for(int i = 0; i < 15; i++) { for(int j = 0; j < 5; j++)..