알고리즘 문제풀이/백준
-
[백준/BOJ] 11047번 동전 0 (C++)알고리즘 문제풀이/백준 2021. 9. 12. 17:11
https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전의 단위가 큰것부터 k를 나머지가 0이 될 때 까지 나누면 되는 문제이다. #include #include using namespace std; int coin[11]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n, k, answer = 0; cin >..
-
[백준/BOJ] 18428번 감시 피하기 (C++)알고리즘 문제풀이/백준 2021. 8. 31. 15:30
https://www.acmicpc.net/submit/18428/32818300 로그인 www.acmicpc.net 14502번 연구소와 비슷했던 문제, DFS와 구현력을 요구하는 문제였다. #include #include #include using namespace std; int N; char map[7][7]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; bool flag; vector teacher, blank; bool canWatch(int nx, int ny, int dir) { while(1) { nx += dx[dir], ny += dy[dir]; if(map[nx][ny] == 'O' || nx = N || ny ..
-
[백준/BOJ] 1439번 뒤집기 (C++)알고리즘 문제풀이/백준 2021. 8. 19. 15:53
https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 그리디 유형의 문제, 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우를 모두 구하여 횟수가 적은 경우를 출력한다. 이때 입력의 문자열이 전부 0 혹은 1인 경우는 바꿀 필요가 없으므로 예외처리를 해준다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); // 0과 ..
-
[백준/BOJ] 1766번 문제집 (C++)알고리즘 문제풀이/백준 2021. 8. 17. 16:14
https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상 정렬을 이용하는 문제, 그러나 '가능하면 쉬운 문제부터 풀어야 한다.' 라는 조건을 만족하기 위해서 큐 대신 우선순위 큐를 사용한다. #include #include #include #include using namespace std; int N, M; int degree[32001]; vector graph[32001]; void topol() { priori..
-
[백준/BOJ] 1436번 영화감독 숌 (C++)알고리즘 문제풀이/백준 2021. 4. 12. 15:57
www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 완전 탐색, 브루트 포스 문제였습니다. 해당 블로그를 참고하여 해결했습니다. 0. 665 1. 666 2. 1666 3. 2666 4. 4666 5. 5666 6. 6660 7. 6661 .... title 값을 665로 초기화하고, 이를 반복문에서 1씩 더한 값을 문자열로 변환하여 "666"을 포함할 때마다 cnt를 증가시켜 N과 같아질 때 종료하게끔 구현하면 되는 문제입니다. #include using n..
-
[백준/BOJ] 17070번 파이프 옮기기 (C++)알고리즘 문제풀이/백준 2021. 3. 28. 16:36
www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 삼성 A형 기출문제 : DFS 파이프는 오른쪽, 아래, 대각선 아래로 이동할 수 있고, 파이프가 놓여있는 경우에 따라 취할 수 있는 액션이 달라집니다. 파이프가 가로로 놓여있는 경우 오른쪽으로 이동 대각선 아래로 이동 파이프가 세로로 놓여있는 경우 아래로 이동 대각선 아래로 이동 파이프가 대각선으로 놓여있는 경우 오른쪽으로 이동 아래로 이동 대각선 아래로 이동 파이프의 움직임을 dx[]..
-
[백준/BOJ] 16637번 괄호 추가하기 (C++)알고리즘 문제풀이/백준 2021. 3. 21. 13:32
www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 삼성 A형 기출 문제 : 브루트 포스(완전 탐색) 입력된 수식이 3+8*7-9*2 라고 가정하고, 괄호를 형성할 수 있는 경우의 수를 따져봅시다. 괄호가 1개인 경우 (3+8)*7-9*2 3+(8*7)-9*2 3+8*(7-9)*2 3+8*7-(9*2) 괄호가 2개인 경우 (3+8)*(7-9)*2 (3+8)*7-(9*2) 3+(8*7)-(9*2) 괄호가 3개인 경우 (3+8)*(7-9)*2 => 괄호..
-
[LeetCode] Best Time to Buy and Sell Stock (C++)알고리즘 문제풀이/백준 2021. 3. 7. 17:38
leetcode.com/problems/best-time-to-buy-and-sell-stock/ Best Time to Buy and Sell Stock - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 그리디 유형의 문제, O(N^2) 풀이로는 입력값의 최대 크기가 10^5이므로 불가능합니다. 따라서 그리디 방식으로 접근하는데, 최소값을 갱신해가며 동시에 최대 이익을 갱신하는 것이 포인트입니다. class Solution { public: int maxPro..