문제 https://www.acmicpc.net/problem/2170 풀이 시작하는 점을 1, 끝나는 점을 -1로 저장하고 스택을 이용해 겹치는 선분이 끝날 경우 길이를 구해줬습니다. 선분 A(1,3), 선분 B(4, 6) 을 예로 들면, 정점 1 스택에 push 정점 3 은 끝 점이므로 pop 하고 길이(3-1) 저장 정점 4 은 시작점이므로 push 정점 6 은 끝 점이므로 pop 하고 길이 (6,4) 저장 겹치는 경우도 손으로 해보면 올바르게 계산된다는 점을 알 수 있습니다. 소스코드 #include #include #include #include using namespace std; int n; vector points; int main(){ ios::sync_with_stdio(false..
문제 https://www.acmicpc.net/problem/7806 풀이 처음에는 n!을 기준으로 gcd(n,k) , gcd(n-1,k / gcd(n,k)) 이런 식으로 최대공약수를 구해나가려고 했습니다. 이런 식으로 구현하게 되면 시간초과가 발생합니다. 이 문제의 경우에는 K를 기준으로 소인수분해하고 해당 소수가 n!에 몇 개 존재하는 지 찾아내서 지수가 작은 수를 통해 최대공약수를 구하는 방식으로 구현해야 합니다. n! 을 소인수분해 할 때 일반적으로 사용되는 것처럼 소수로 계속 나누게 되면 엄청난 시간이 걸립니다. n! 을 소인수분해 할 때는 n / 소수^1 + n / 소수^2 + n / 소수^3 ... 하시면 n! 을 소인수분해 했을 때 소수 갯수를 구할 수 있습니다. 소스코드 #include..
문제 https://www.acmicpc.net/problem/14476 풀이 문제풀이를 완전탐색 알고리즘으로 생각을 해보면 1~N까지의 수를 하나씩 다 빼보고 그 중에 가장 큰 최대공약수를 가질 수 있는 수를 빼는 것입니다. 하지만 완전탐색의 경우 1~N까지 숫자를 빼는 것과 숫자를 뺀 나머지 수들의 최대공약수를 구하는 과정에 있어서 시간초과가 발생할 것이라고 생각 했습니다. 제 풀이는 1부터 N까지 모두 빼보는 것까지는 완전탐색과 똑같은 방법입니다. 다른 점은 Segement Tree 를 이용해서 1~N까지의 최대공약수를 미리 저장해놓는 것입니다. 현재 숫자를 빼고 Segement Tree를 Update 해주고 비교해주는 거라고 보시면 됩니다. 소스코드 #include #include using na..
문제 https://www.acmicpc.net/problem/6569 풀이 큰 직사각형의 상태를 0(빈 칸), 1(채운 칸) 으로 경우의 수를 계산해나갔습니다. 현재칸이 blockNum 일 때 너비 w만큼의 칸을 상태를 저장해놓고 상태에 따라 가능한 직사각형을 채운다고 생각하시면 됩니다. 예를 들어, 높이가 3 너비가 5이면 직사각형의 번호는 아래와 같습니다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0번째 칸에 높이 1, 너비 2 인 직사각형을 놓을 경우면 상태를 00011(10진수 3) 으로 표현하다고 생각하시면 됩니다. 소스코드 #include #include using namespace std; const int MAX_N = 11; long long gCache[(MAX_..
문제 https://www.acmicpc.net/problem/11727 풀이 취준생 때 이해하기 힘들어서 포기했던 문제다. 시간을 두고 천천히 그림을 그려가면서 생각해보면 점화식을 생각해낼 수 있습니다. 2x2 타일을 채우는 경우를 그림으로 그려보고, 2x3 을 채우는 방식을 생각해봅니다. 2x3은 앞 쪽에 2x1 타일을 채우고 나머지를 채우는 경우와 뒤 쪽에 2x1을 채우고 나머지를 채우는 경우로 생각 할 수 있습니다. 소스코드 // boj.kr/11727 // 2xn 타일링 #include using namespace std; #define MOD 10007 const int MAX_N = 1000; long long gCache[MAX_N+1]; int main(){ ios::sync_with_s..
문제 https://www.acmicpc.net/problem/1563 풀이 dynamic programming / recursion 을 통해 풀이 했습니다. gCache : day 에 출석, 지각, 결석 횟수 저장 recursion 함수를 통해 저장된 값이 있으면 활용하고 아닌 경우 다음날을 3가지 경우로 분기시켜 진행 시켰습니다. 출석하는 경우 (day + 1, attendance + 1, late, 0) ㄴ지각하는 경우 (day + 1, attendance, late +1, 0) 결석하는 경우 (day +1, attendance, late, absent+1) 소스코드 #include #include using namespace std; const int MAX_N = 1000 + 1; const i..
문제https://www.acmicpc.net/problem/15686풀이과정Dfs와 백트래킹을 통한 완전탐색으로 구현을 했습니다.M개의 치킨집을 골랐을 경우 최소거리의 합을 구하고 가장 작은 경우만 저장해서 출력했습니다.DFS와 백트래킹을 통한 완전탐색 문제를 풀어봤다면 푸실 수 있을 것 같습니다. 알고리즘 1(집), 2(치킨집) 일 경우 각각 person, chicken 벡터에 위치를 저장합니다. 재귀함수를 통해 M개의 치킨집을 선택합니다 person 벡터를 돌며 집과 선택된 치킨집의 거리 중 최소값만을 더합니다. 치킨집 M개를 뽑는 모든 경우를 탐색하고 최소거리의 합 중 가장 작은 값만 저장합니다. 소스코드#include #include #include using namespace std; #def..
문제https://www.acmicpc.net/problem/13460풀이Dfs를 통해서 기울이는 모든 방향을 탐색해야된다.이 때 주의할 점은 아래와 같다. 이전의 기울인 방향으로는 다시 기울이지 않는다.이전의 기울인 방향의 반대 방향으로도 기울이지 않는다 (원점이 되기 때문에) 원래는 2048 처럼 기울이는걸 구현하려고 했지만 빨간공과 파란공의 우선순위 비교까지 하려면 너무 복잡해져서 포기하고 답을 찾아봤다.여러 사람들이 빨간공 따로 파란공 따로 그냥 구현했고 위치가 똑같을 때만 우선순위를 비교해 다시 이동시키는걸 확인했다.삼성 기출문제 중에 가장 난이도가 높은 문제 같다.실제로 시험에서 이런 Dfs + 구현 문제가 나오면 풀지 못할 것 같다.소스코드#include #include using names..
문제https://www.acmicpc.net/problem/12100풀이제일 싫어하는 구현문제다. 중간에 큐 사용에 대한 오류가 떴는데 중단점을 이상한 곳으로 찍어놓고 디버깅을 돌려서 해결하는데 너무너무 오래걸렸다.위, 아래, 왼쪽, 오른쪽 모든 방향을 Dfs를 통해 완전탐색하면 되는 문제다.문제의 핵심은 주어진 조건에 맞게 한 쪽 방향으로 이동한 경우를 만드는 점이다. 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 이와 같은 조건 때문에 0이 아닌 수를 큐에 저장하는 순서는 아래와 같이 된다.방향이 위인 경우 (0,0) ~ (N-1,0) 방향이 아래인 경우 (N-1,0) ~ (0,0) 방향이 왼쪽인 경우 (0,0) ~ (N-1,0) 방향이 오른쪽인 경우 (N-1,0) ..
문제https://www.acmicpc.net/problem/14500풀이테트로미노의 종류는 총 5가지이지만 Dfs를 통해 탐색을 할 수 있는 경우는 4가지다.ㅗ모양은 Dfs로 탐색을 할 수 없기에 따로 탐색하는 함수를 만들었다.이 경우에는 인접한 칸을 모두 검사했을 경우 그 중에 가장 작은 값을 빼서 최대값을 구하는 방법으로 구현했다.처음에 접근을 테트로미노마다 다른 Dfs를 만들어서 각각 다른 회전을 써야되나 싶어서 어려워한 문제다.문제를 좀 더 쉽게 풀 수 있는 방법부터 생각해보는 게 좋을 것 같다.소스코드#include #include using namespace std; #define MAX_SIZE 501 #define MIN_INF -987654321 #define MAX_INF 987654..