분류 전체보기
-
[백준/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++)..
-
[백준/BOJ] 11000번 강의실 배정 (C++)알고리즘 문제풀이/백준 2021. 9. 14. 18:56
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 강의실을 적게 사용하기 위해서 시작 시간과 끝 시간의 간격을 최대한 좁혀야 한다. 그러므로 시작 시간을 기준으로 오름차순 정렬하였다. 그리고 우선순위 큐를 이용하여 수업 끝 시간을 넣어준다. 현재 수업의 시작 시간이 우선순위 큐에 들어있는 top의 값보다 크거나 같으면 강의실을 같이 쓸 수 있으므로, pop한 후 우선순위 큐에 현재 수업의 끝 시간을 넣어준다. 반대의 경우에는 pop없이 push만 해준다. 그러면 우선순위 큐에 남은 원소의 수가..
-
[백준/BOJ] 1969번 DNA (C++)알고리즘 문제풀이/백준 2021. 9. 13. 18:52
https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 각 열마다 A, C, G, T가 몇번 나오는지 저장할 수 있는 2차원 배열을 선언한다. 합이 가장 작은 DNA은 결국 한 열을 기준으로 각 행마다 빈도수가 많이 나온 것들로 구성하면 된다. TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT -------------- TAAGATAC 해밍 디스턴스는 n에서 각 행마다의 빈도수..
-
[백준/BOJ] 1931번 회의실 배정 (C++)알고리즘 문제풀이/백준 2021. 9. 13. 18:07
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 해결의 아이디어는 가장 끝나는 시간이 작은 회의실을 시작으로, 가능한 한 끝나는 시간 작은 회의실을 계속 고르면 되는 문제이다. 따라서 입력을 끝나는 시간을 기준으로 오름차순 정렬한다. (끝나는 시간이 혹시 같다면 시작 시간을 기준으로 오름차순) 그리고 반목문을 통해 현재 선택한 회의실의 끝나는 시간과 다음 회의실의 시작시간을 비교해가며 회의실을 선택하면 된다. #include #include using namespace std; int cmp(pair a, pair b) { if(a.second == b...