백준 문제풀이
-
SWEA 1244 : [S/W 문제해결 응용] 2일차 - 최대 상금백준 문제풀이/BRUTE FORCE 2020. 5. 20. 15:29
문제 문제 풀어보기 풀이 재귀를 돌면서 모든 경우를 탐색하는 것은 굉장히 기본적인 완전 탐색 방법입니다. 하지만 이상하게 교환횟수가 7개 정도만 넘어가면 계속해서 시간초과가 뜨더군요. 생각해봅시다. 주어지는 수는 최대 6자리의 숫자입니다. 여기서 두개의 인수를 교환해서 원하는 숫자를 얻기 위해서는 최대 몇번의 교환이 필요할까요? 카드게임을 예를 들어 봅시다. 도둑잡기, 원카드, 훌라 어떤 게임이든 상관없이 손에 6장의 카드가 있습니다. 우리는 이 카드를 정리하기 위해 한 카드 씩 원하는 위치에 가져다 놓습니다. 이 과정은 두 개의 위치를 교한 하는 것과 크게 다르지 않습니다. 그리고 우리는 정확히 카드의 개수만큼 교환할 수 있다면 어떤 순서의 배열이든 만들 수 있습니다. 그렇기 때문에 이 문제에서도 재귀..
-
SWEA 4168 : 삼성이의 쇼핑 ( 비트마스크 + 조합 연습 )백준 문제풀이/Dynamic Programming 2020. 5. 20. 14:00
문제 문제 풀어보기 (로그인 후 접속 가능) 풀이 냅색 문제에서 비트 마스크를 사용하여 선택한 물건들을 출력할 수 있도록 하였습니다. 냅색 알고리즘은 배낭문제에서 나온 기법인데 생각보다 자주 나오는 유형입니다. 최대의 만족도를 구하는 방법은 냅색을 이용해서 구하게 됩니다. 그리고 만족도를 인덱스로 하는 배열에 비트 마스크를 저장합니다. 출력 과정에서 정답이 되는 만족도에 있는 비트 마스크를 통해 어떤 옷을 선택했는지 출력합니다. 코드 #include #include #include #include using namespace std; int max(int a, int b) { if (a > b) return a; else return b; } int T; int ans; int n, m; int v[26..
-
BOJ 9663 : N-Queen백준 문제풀이/etc 2020. 5. 19. 12:50
문제 문제 풀어보기 풀이 퀸을 먼저 배치하고 가능한 경우인지 판단하는 알고리즘을 하면 시간 초과로 문제를 풀 수 없었습니다. 그래서 다른 분의 블로그를 참조해서 백트래킹을 사용했습니다. 간단히 설명하자면 퀸을 하나 넣고 퀸의 이동반경을 모두 덱에 넣습니다. 퀸이 들어갈수 있는 곳에 넣으면서 계속 덱에 넣다 보면 퀸의 수가 N 개 이면서 덱의 사이즈가 N * N 이 되는 경우가 생깁니다. 바로 이경우가 퀸을 N 개 위치시킨 경우가 됩니다. 코드 #include #include #include #define safe(x,y) x>=0&&x=0&&y < n using namespace std; int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,-1,..
-
BOJ 13023 : ABCDE백준 문제풀이/GRAPH 2020. 5. 15. 17:59
문제 문제 풀어보기 풀이 문제를 이해하는데 좀 오래 걸렸네요... 이 문제는 A -> B -> C -> D 처럼 친구의 친구의 꼬리를 4번 무는 경우를 찾는 겁니다. 그래서 DFS 를 사용해서 깊이가 4가 되는 경우를 찾으면 됩니다. 코드 #include #include #define max 2000 using namespace std; bool check[max + 1]; vector v[max + 1]; // max+1 개의 벡터 생성 int n, m; void dfs(int st, int index) { check[st] = true; // 깊이가 4인경우 종료 if (index == 4) { cout n >> m; for (int i = 0; i >..
-
BOJ 11727 : 2xn 타일링 2백준 문제풀이/Dynamic Programming 2020. 5. 15. 17:51
문제 문제 풀어보기 풀이 이거 하나만 확인하세요 !! 경우의 수를 계산하는 모든 과정에서 모듈러 연산을 하셨나요 ? ㅎㅎ 코드 #include #include using namespace std; int d[1001][3]; #define mod 10007 int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; d[1][1] = 1; d[2][0] = d[2][1] = d[2][2] = 1; for (int i = 3; i
-
BOJ 17140 : 이차원 배열과 연산백준 문제풀이/etc 2020. 5. 10. 22:17
문제 문제 풀어보기 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 저는 R 연산을 구현하고 C 연산에 복붙하고 행과 열만 바꿔서 풀었습니다. 처음엔 계산된 값을 어떻게 삽입을 할지 고민을 많이 했는데, 그냥 하드코딩으로 집어 넣어줘도 시간은 초과되지 않았습니다. 코드 #include #include #include #include #include #include using namespace std; int n = 3; int m = 3; vector arr(105, vect..
-
BOJ 17142 : 연구소 3백준 문제풀이/GRAPH 2020. 5. 10. 21:39
문제 문제 풀어보기 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 간단하게 설명하면 모든 경우에 대해서 BFS를 전부 돌려봐야 하는 문제입니다. 어떤 바이러스를 활성화할 것인지를 고르는 방법이 포인트인데, 조합을 써도 되고 방법은 여러가지 입니다. 저는 비트 마스크를 사용해서 풀었으니 참고하시면 좋을 것 같습니다. 코드 #include #include #include #include #include #include using namespace std; int dx[] = { 1,-1,0,0 }; int dy[] ..
-
BOJ 17143 : 낚시왕백준 문제풀이/etc 2020. 5. 4. 18:28
문제 문제 풀어보기 풀이 최근에 출제되는 삼성 기출문제는 거의 80% 가 시뮬레이션 문제입니다. 시뮬레이션은 순차적으로 진행되는 프로그램을 그대~로 구현하는 문제입니다. 이러한 문제들은 복잡한 알고리즘을 요구하지 않기 때문에 빠른 이해력과 정확한 설계만 한다면 대부분 푸실 수 있는 문제들입니다. 하지만 시뮬레이션에선 항상 시간 초과의 늪에 빠지게 됩니다. 이문제도 그랬는데요. 그러한 시간초과를 해결하는 방법이 바로 모듈러 연산입니다. 예를 들어 봅시다. 철이는 1초마다 숫자를 하나씩 증가하면서 말하고 있는데, 3의 배수일때마다 박수를 친다고 합니다. 그럼 1억초 이후에 철이는 몇 번 박수를 칠까요? 라는 문제를 풀때 저희는 1초 일때 박수를 치는지 안치는지 2초 일때 박수를 치는지 안치는지 3초 일때 박..