알고리즘 문제풀이
-
[백준/BOJ] 1107번 리모컨 (C++)알고리즘 문제풀이/백준 2020. 12. 7. 18:22
www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 브루트 포스(완전 탐색) 유형의 문제입니다. answer의 초기값을 '숫자 버튼을 누르지 않았을 경우', '+/- 버튼만을 누른 경우' 두가지를 고려하여 설정해주고, 0번 채널부터 1000000번 채널까지 차례대로 N번 채널로 가기 위해 숫자 버튼을 몇번 누르는지 확인합니다. 확인 후 고장난 버튼이 있으면 0을 리턴하고 고장난 버튼이 없으면 개수를 리턴합니다. '현재 채널 - N번 채널'의 절대..
-
[백준/BOJ] 11723번 집합 (C++)알고리즘 문제풀이/백준 2020. 12. 7. 16:22
www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 처음에 set을 이용하여 풀었는데 시간초과가 발생!. 문제를 자세히보니 메모리가 4MB로 제한되어 있었고, 입력값도 최대 3백만으로 꽤 컸기에 단순히 set을 이용해 푸는건 불가능하다는 것을 알게됨 bool형 배열을 하나두고 값이 있는지 없는지만 확인, toggle 연산 시 XOR 연산을 활용, 마지막으로 반복문에서 문자열이랑 숫자를 각각 입력받을 때 cin을 쓰면 뭔가 엉키는 것 같으므로 안전하게 scanf를 사용! #include #inclu..
-
[백준/BOJ] 6064번 카잉 달력 (C++)알고리즘 문제풀이/백준 2020. 12. 7. 13:48
www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net M = 5, N = 7, x = 3, y = 4 일 때 다음과 같이 카잉 달력을 나타낼 수 있습니다. 1 : 11 : 2 : 12 : 3 : 13 : 4 : 14 : 5 : 15 : 6: 16 : 7: 17 : 8 : 18 : 9 : 19 : 10 : 20 : 뭔가 위의 경우에서는 뭔가 규칙을 찾아내기 어렵습니다. 위에서 나타낸 카잉 달력의 값들을 전부 1씩 빼보면 어떨까요? 0 : 10 : 1 : 11 : 2 :..
-
[백준/BOJ] 10819번 차이를 최대로 (C++)알고리즘 문제풀이/백준 2020. 12. 5. 17:52
www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net next_permutation을 이용해 벡터의 순열을 구한 후, 0부터 v.size() - 1 만큼 연속된 두 원소의 절대값 차를 모두 구해 더한 값의 최대를 찾으면 됩니다. #include #include #include using namespace std; int n, answer = -1; vector v; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); ..
-
[백준/BOJ] 14891번 톱니바퀴 (C++)알고리즘 문제풀이/백준 2020. 12. 5. 17:40
www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 삼성 역량 테스트 기출 문제 : 시뮬레이션(구현) 특정 톱니바퀴를 움직였을 때 이에 인접해있는 톱니들이 움직이는지 안움직이는지, 움직인다면 어떤 방향으로 움직이는지를 처리하기가 어려웠던 문제였습니다. 이러한 체크를 먼저 하기 위해서 rotCheck 배열을 두어 특정 톱니바퀴를 움직일 때, 그 톱니바퀴의 왼쪽과 오른쪽을 각각 쭉 확인하여 왼쪽 톱니바퀴의 2번 인덱스와 오른쪽 톱니바퀴의 6번 인덱스가 같은지 ..
-
[백준/BOJ] 11559번 Puyo Puyo (C++)알고리즘 문제풀이/백준 2020. 12. 5. 15:15
www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net BFS + 시뮬레이션(구현) 문제 Puyo가 제거되고 난 후 중력 처리를 해주는 부분을 구현하는 데 애를 먹은 문제입니다. 제거 될 Puyo를 벡터에 저장한 후, 이를 열 기준 오름차순으로 정렬하고 열 마다 한 행씩 뒤에서 앞으로 값을 넣어주는 것이 문제 해결의 포인트입니다. #include #include #include #include #include using namespace std; char map[12][6]; bool visit[12][6]; int dx[4] = {1, 0, -1, ..
-
[백준/BOJ] 13335번 트럭 (C++)알고리즘 문제풀이/백준 2020. 12. 5. 11:58
www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 똑같은 문제 transferhwang.tistory.com/228 [프로그래머스/Level 2] 다리를 지나는 트럭 (C++) programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소..
-
[백준/BOJ] 1748번 수 이어 쓰기 1 (C++)알고리즘 문제풀이/백준 2020. 12. 4. 21:12
www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. www.acmicpc.net 입력값의 범위가 최대 1억이므로 일반적인 방법으로는 시간초과를 피할 수 없습니다. 따라서 다음과 같은 아이디어가 필요합니다. 예를들어 입력값이 120이라고 치면 1 ~ 9 : 9개, 길이 : 1 10 ~ 99 : 90개, 길이 : 2 100 ~ 120 : 21개, 길이 : 3 9*1 + 90*2 + 21*3 = 9 + 180 + 63 = 252 자리수마다 숫자 개수를 구하고, 그 길이를 곱해준 후 모두 더해주면 됩니다. #include using namespace std; int main(void) { ios_base::sync_with_..