본문 바로가기
반응형

전체 글1054

BOJ 14501 : 퇴사 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/14501 모든 경우를 다 해봐야 최대 이익을 알 수 있다. 하지만 특정 일에 상담을 한다면, 해당 일 + T[i]일 부터 상담이 가능하다는 조건을 지켜야 한다. 모든 경우는 아래와 같다. 1일에 상담 -> 4일, 5일, 6일, 7일 상담 가능. 2일에 상담 -> 7일 상담 가능. ... 7일에 상담 -> 불가능. 따라서 DFS를 총 N번 실행한다. (N번째 일을 최초로 시작하는 상담) /* N일부터 상담 시작, 첫 보수는 0원 부터. */ for (int i = 1; i N) /* N + 1을 넘기면 상담 불가 */ { /* 상담을 시작한 날도 포함되므로, 이 .. 2021. 2. 15.
BOJ 14501, 15486 : 퇴사, 퇴사 2 알고리즘 문제 전체 링크 www.acmicpc.net/problem/14501 www.acmicpc.net/problem/15486 퇴사 1의 경우는 완전 탐색으로 풀 수 있지만, 퇴사 2는 N이 매우 크므로, 다이나믹 프로그래밍, 메모이제이션(memoization)으로 풀어야 한다. DP[i] = i일 전까지의 최대 이익 이라고 정의를 하자. i일에 일을 수행하지 않으면, DP[i + 1] = DP[i]와 기존 memoization의 값 중 큰 값이 된다. i일에 일을 수행한다면, i일 전까지의 최대 이익인 DP[i]와 i일에 받을 보수 P[i]를 더한 값 vs 기존 memoization의 값 중 큰 값. 즉, DP[i + T[i]] = DP[i] + P[i] 와 DP[i + T[i]] 중 큰 값을 선.. 2021. 2. 15.
BOJ 14500 : 테트로미노 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/14500 블럭은 5종류지만, 회전이나 대칭을 시켜도 되므로 총 19종류가 된다. 이 블럭을 실제로 4x4 배열로 만들면 아래의 모양이 된다. /* 19개 블럭을 4x4 배열로 선언 */ int BLOCK[19][4][4] = { { { 1, 1, 1, 1 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }, { { 1, 0, 0, 0 }, { 1, 0, 0, 0 }, { 1, 0, 0, 0 }, { 1, 0, 0, 0 } }, { { 1, 1, 0, 0 }, { 1, 1, 0, 0 }, { 0, 0, 0, 0 }, { 0.. 2021. 2. 15.
B형에 필요한 최적화 코드 (1) 삼성 B형 전체 링크 참고 - B형에 필요한 최적화 코드 (1) - B형에 필요한 최적화 코드 (2) - 함수의 매개변수와 배열의 register 속도 비교 - 삼성 B형 디버깅 Tip - 비주얼 스튜디오 output.txt 설정하기 - 삼성 SW 역량 시험 환경에서의 인라인 함수 - Visual Studio LNK1168: 쓰기용으로 열 수 없습니다 해결방법 1) ++i (전위 증가) vs i++ (후위 증가) 비교. 2) register 변수를 사용하자. 3) 전역 변수(global) 접근을 최소화 하자. 1) ++i (전위 증가) vs i++ (후위 증가) 비교. 전위 증가는 값을 먼저 증가 시키고 return한다. 후위 증가는 원래 값을 먼저 받고 나중에 증가한다. 하지만 후위 증가의 경우는 임시.. 2021. 2. 15.
삼성 SW 역량 테스트 B형 Reference 코드 삼성 B형 전체 링크 swexpertacademy.com/main/main.do 상단의 LEARN -> Visual Reference Code에 참조 코드가 있다. Data Structure, Algorithm에 대한 reference code가 실제 시험에도 제공된다.(문제 왼쪽 상단에 Reference 탭 제공)필요한 코드를 정리해보면. Data Structure1) Stack    - 배열로 간단히 만들 수 있다. 참조 코드처럼 만들면 느리다. (스택 예시 참고) 2) Queue     - 배열로 간단히 만들 수 있다. 참조 코드처럼 만들면 느리다. (큐 예시 참고) 3) Priority Queue    - B형 필수, 못 외우겠다면 참조 코드도 나쁘진 않지만, 자기만의 코드를 만들도록 하자.   .. 2021. 2. 15.
BOJ 14499 : 주사위 굴리기 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/14499  4방향으로 명령어대로 움직이면 되는 시뮬레이션 문제이다. 아래와 같은 주사위의 모양이 되도록,6면체를 가지는 구조체 DICE를 만들자.typedef struct st{ int up; int left; int top; int right; int down; int bottom;}DICE;DICE dice; /* map을 움직이는 dice는 전역으로 선언 */최대한 그림과 비슷하게 모양을 만들어 두면, 디버깅할 때 편하다. input 함수로 MAP과 command를 저장해두고, move 동/서/남/북을 .. 2021. 2. 15.
BOJ 13458 : 시험 감독 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/13458 먼저 총감독관은 1명이어야 하므로 각 응시자수에서 B만큼 뺀다.그리고 남은 응시자들을 감독할 부감독관을 계산하면 된다. 따라서 sum = 총감독관 (N명) + 부감독관 수가 된다.응시자 수가 적어서(A[i] 총감독관으로 모두 커버 가능하면 부감독관을 계산할 필요가 없다. 부감독관의 수는 (A[i] - 1) / C + 1이 되는데, 아래의 경우를 생각해보자. 부감독관이 감시 가능한 수가 3일 때, 남은 학생 수 1 => 1명 필요남은 학생 수 2 => 1명 필요남은 학생 수 3 => 1명 필요남은 학생 수 4 => 2명 필요... 즉 감시 가능한 수의 .. 2021. 2. 15.
BOJ 3190 : 뱀 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/3190 삼성 A형은 보통 DFS/BFS 1문제, 시뮬레이션 1문제로 나온다. 첫번째 시뮬레이션 문제 뱀을 풀어보자. 뱀은 Snake 게임을 구현하면 된다. (구글에서 스네이크 게임 검색) 만들어야 함수는 다음과 같다. 1) input 함수 및 디버깅을 위한 output 함수. 2) 충돌 체크 함수. MAP을 어떻게 설계하냐에 따라 푸는 방법이 조금 달라질 수 있다. NXN 정사각 보드에서, 상하좌우 끝에 벽이 있다고 했으므로, (0, 0) 부터 (N + 1, N + 1)을 모두 벽으로 만들고, (1,1) ~ (N, N)을 보드로 덮어씌우자. 그리고 X초 뒤의 명.. 2021. 2. 14.
BOJ 10866 : 덱 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10866 참고 - BOJ 10866 : 덱 with Linked List 큐 + 스택 문제를 조합해서 풀면 해결할 수 있다. 큐에서 push할 때는 wp++, pop은 rp++이고, 스택에서 push할 때는 sp++, pop은 --sp였다. 즉, 배열의 앞에서 pop할 때는 rp++, 뒤에서 pop할 때는 --wp를 하면 된다. 마찬가지로, 앞에서 push할 때는 --rp, 뒤에서 push wp++ 이 된다. 덱의 경우, 앞에서도 push가 가능하므로 rp : read pointer의 의미가 맞지 않다. 따라서, 혼동되지 않도록 rp → front, wp → back 으로 수정하였다. 메모리를 넉넉하게 잡고 메모리의 가운데 부터 시작점.. 2021. 2. 8.
반응형

티스토리툴바