펭로그

문제링크 : https://koitp.org/problem/SDS_TEST_BIGINT [삼성 SDS 대학생 알고리즘 특강 사전 테스트 B Type 2번 문제]int형을 사용하면 시간 초과가 나는 문제였다. 입력의 조건이 -1,000,000 ~ 1,000,000 이기 때문에 잘 확인해야 한다.long int나 long, long long 어느 것으로 해도 상관없다.다만, Windows 환경에선 long int와 long 형은 64비트 컴파일러(VS 기준) 4바이트로 인식하기 때문에 long long을 써야한다.UNIX 64비트에선 long int와 long을 8바이트로 인식한다.KOITP를 비롯한 대부분이 gcc 컴파일러를 사용하기 때문에 익숙해질 필요가 있다. 1. 맨 첫 입력은 고정이다.2. 그 다음..

문제링크 : https://koitp.org/problem/SDS_TEST_TREASURE [삼성 SDS 대학생 알고리즘 특강 사전 테스트 B Type 1번 문제]DFS로 풀게되면 무조건 시간초과가 나게되서 BFS로 풀어야하는 문제이다.최단거리를 찾는 동시에 이동한 거리를 dist 배열을 따로 만들어서 별도로 저장했다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647// KOITP_SDS_Btype_01#include using namespace std; int main() { // freopen("../input.txt", "r", stdin); int T; cin >> T; for (int t =..

문제링크 : https://www.acmicpc.net/problem/10799 ( 은 쇠막대기의 시작점이고 ) 은 쇠막대기의 끝나는 부분이고 ( ) 은 레이저를 나타낸다.두 괄호 사이(쇠막대기)에는 반드시 ( ) 이 올 수밖에 없다. 1. 열린 괄호의 갯수는 닫힌 괄호의 갯수와 동일해야 한다.2. 열린 괄호가 증가하다가 감소하는 시점 ( ) 은 반드시 레이저이다.3. 레이저 ( )를 제외하고 레이저의 좌측 부분에 열린 괄호가 몇개인지를 세면 레이저를 기준으로 좌측의 잘린 쇠막대기의 판이 몇개인지 알 수 있다. 열린 괄호를 읽을 때 마다 카운트를 세면 될 것이다.4. 레이저 ( ) 우측 편부터 닫힌 괄호 ) 가 오면 쇠막대기 카운트를 하나씩 감소시킨다. 여기서 찾을 수 있는 규칙은 ( 의 경우 반드시 다..

문제링크 : https://koitp.org/problem/SDS_TEST_CONSULTING [삼성 SDS 대학생 알고리즘 특강 사전 테스트 A Type 4번 문제]최대 상담 고객의 수 : 최소 상담시간 조건을 충족해야 한다. 수진이의 근무시간을 최소 상담시간으로 나눈 몫을 취하면 된다.최소 상담 고객의 수 : 고객들이 원하는 상담시간 모두를 더하면 된다. 단, 수진이의 근무시간을 초과하기 전까지로 한다.최소 ~ 최대 사이의 값으로 loop를 돌려서 값을 구하면 된다. 1. 고객 당 10점씩 받을 수 있기 때문에 고객의 수 만큼 10점씩 누적시킨다.2. 모든 고객이 최소 시간만큼만 상담한다고 가정하고 수진이의 근무시간에서 최소 시간만큼만 뺀다.3. 남아있는 시간을 효율적으로 사용하려면 불만족 지수를 3..

문제링크 : https://koitp.org/problem/SDS_TEST_CLOCK [삼성 SDS 대학생 알고리즘 특강 사전 테스트 B Type 4번 문제]FND의 7-segment를 보자마자 bit 연산으로 풀어야겠다고 생각이 든 문제이다.0~9 까지의 모든 bit 순서를 저장한 배열을 만들고 각 숫자와 XOR 연산을 하게되면 어떤 부분이 다른지 여부가 체크된다.이 다른 부분의 bit 갯수가 4개의 segment 모두 합쳐 2개 이하가 되는 최소 값을 구하면 된다.4중 for문을 사용하여 코드가 매우 지저분하지만 for문이 각각 상수 횟수 만큼 실행되기 때문에 O(1)이다.탐색 조건은 반드시 00:00 ~ 23:59 범위 내로 한정해야 한다. 최소로 나올 수 있는 값이 32:00 이런식으로 되버리면 ..

문제링크 : https://koitp.org/problem/SDS_TEST_SURVIVOR [삼성 SDS 대학생 알고리즘 특강 사전 테스트 A Type 2번 문제]모든 배열을 하나 하나 탐색하여 풀었다. 배열의 각 원소를 중심으로 3*3 내에 불모지가 없고 물, 산, 초원이 모두 있는지를 구하면 된다.4중 for문이라 코드가 조금 지저분하긴하다.맵의 가장자리에 도달했을 경우의 예외 처리를 위하여 if(i==0 && a==-1) continue; 같은 구문을 4번이나 넣었는데....사실 맵의 크기를 상하좌우로 1씩 더 늘려서 만들었다면 굳이 넣지 않아도 되었을 코드이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424..

문제링크 : https://koitp.org/problem/SDS_TEST_SPACE [삼성 SDS 대학생 알고리즘 특강 사전 테스트 A Type 1번 문제]1. 맵의 끝부분에서 이동하게 되면 반대편으로 이동된다.2. X 성분의 값과 Y 성분의 값을 각각 구해서 계산하는 편이 수월하다.위 두가지 조건을 가지고 간단하게 시뮬레이션을 해보면 쉽게 풀리는 문제다.빨간색 화살표는 r1과 r2 사이의 거리를 의미하는 것으로 |r2 - r1| 을 abs(r2 - r1) 로 나타낼 수 있다.파란색 화살표는 맵의 끝에서 r1까지의 거리, 맵의 끝에서 r2까지의 거리를 더한 것으로 그냥 r1 > T; for (int t = 0; t > N >> M >> r1 >> c1 >> r2 >> c2; int result = 0;..

문제링크 : https://koitp.org/problem/SDS_TEST_PAGE [삼성 SDS 대학생 알고리즘 특강 사전 테스트 A Type 3번 문제]처음으로 읽은 페이지를 시작으로 하여 건너뛸 페이지수 + 1 만큼 더해가면서 푸는 방법도 좋지만 이렇게 할 경우 (전체페이지수 - 초기페이지) / (스킵페이지 + 1) 만큼 실행을 해야한다.어짜피 input으로 받은 값들은 모두 다 if 문으로 조건을 판별해야하기 때문에 이 방법이 훨씬 더 낫다.(쉬어가는 페이지 - 초기페이지)가 (스킵페이지 + 1)로 나누어 떨어지는가를 체크하면 더 쉽고 빠르게 풀 수 있다. 123456789101112131415161718192021222324252627282930313233// KOITP_SDS_Atype_03#..

문제링크 : https://www.acmicpc.net/problem/2839 1. 설탕은 3kg과 5kg 두가지 밖에 존재하지 않는다.2. 두 무게로 나누어 떨어지지 않으면 무조건 무시된다.3. 최적의 값을 구하려면 5kg이 최대한 많아야 한다.4. 3kg씩 빼가면서 5의 배수가 최초로 나오는 시점이 가장 최적의 답이 될 수 있다. 1234567891011121314151617181920212223242526// BOJ 2839 설탕배달#include using namespace std; int main() {// freopen("../input.txt", "r", stdin); int n; cin >> n; int a = 0; int ans = -1; while(n >= 0){ if(n % 5 == ..

문제링크 : https://www.hackerrank.com/challenges/torque-and-development 1234567891011121314151617181920212223242526#include using namespace std;vector p;int f(int a) { return p[a] == a ? a : p[a] = f(p[a]); }void u(int a, int b) { p[f(a)] = f(b); }int main() { int T; cin >> T; while (T--) { int N, M, a, b; long long c, d; cin >> N >> M >> c >> d; p.clear(); p.resize(N); iota(p.begin(), p.end(), 0); ..