펭로그

삼성 SDS에서 대학생을 대상으로 알고리즘 교육을 무료로 시켜준다는 공고가 떴다!온라인으로 분반테스트 응시를 하고 선발된 인원에 한해서 알고리즘 교육이 진행되는 프로그램이다.알고리즘 교육을 받을 기회가 없어서 제대로 공부해보지도 못한 채로 알고리즘을 제대로 시작한지 2달 정도 밖에 안된 나에겐 아주 좋은 기회라 생각이 들어 바로 신청했다.하지만 신청자가 몰린 탓에 마감 기간이 27일까지였지만 실제 마감은 17일 경에 마감된 것 같다. 18일 쯤에 사전테스트 응시 안내 메일이 오고 22일 자정까지 응시할 수 있도록 안내 메일이 왔다.사전테스트 문제는 삼성SDS에서 운영하는 https://koitp.org 사이트에 공개되어 있다. 미라콤아이앤씨와 삼성 SDS의 사내 교육에 이용하는 사이트로 개설되어 있는 것..

문제링크 : https://koitp.org/problem/SDS_TEST_CALCULATOR [삼성 SDS 대학생 알고리즘 특강 사전 테스트 B Type 3번 문제]시간초과로 실패했던 문제이다. 1. 일단 정렬한다.2. 앞의 두 숫자(최소값)을 더하고 더한 숫자를 뒷쪽에 끼워놓는다.3. 반복 삭제와 삽입이 빈번하게 일어나기 때문에 STL vector를 사용하면 시간이 매우 오래걸리게 된다.또한, 매 loop 실행시마다 삽입의 적절한 위치를 찾기 위해 for문을 돌리기 때문에 O(N^2)이 되겠다.답은 맞은듯하나 시간초과로 실패하였다. 우선순위 큐를 사용하면 될 것 같기도 한데 아직 이것도 모르겠다.일반 배열과 vector를 제외한 다른 자료구조에 대한 학습이 부족하여 여기까지가 한계인듯하다.추후에 자료..

문제링크 : 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://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#..