본문 바로가기
반응형

알고리즘288

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.
BOJ 10845, 18258 : 큐, 큐2 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10845 www.acmicpc.net/problem/18258 큐, 큐2 문제는 같지만 명령의 수가 다르다. 큐는 N이 작아서 적당히 풀어도 통과할 수 있다. 큐2 기준으로 풀려면 모든 명령어를 O(1)이 되도록 풀어야 한다. 큐도 메모리만 넉넉하게 잡으면 스택처럼 배열로만 풀 수 있다. 스택과 다른 점은 pointer가 2개 필요하다. 큐에서 push할 때 write pointer를 증가시키고, pop할 때는 read pointer를 증가시키면 큐가 된다. 그리고 read와 write의 차이가 queue의 사이즈가 된다. 현재 queue의 뒤에 값을 저장해야 하므로 wp에 값을 저장하고 증가시킨다. queue[wp] = input, .. 2021. 2. 7.
BOJ 12100 : 2048 Easy (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/12100 2048 게임을 구현하는 문제, 구슬 탈출 2와 마찬가지로 4방향으로 움직이며, 총 5회까지 가능하다. 즉 45=1024번 의 경우의 수 중 가장 큰 값을 구하면 된다. 만들어야 함수는 다음과 같다. 1) input 함수 및 디버깅을 위한 output 함수. 2) Map에서 가장 큰 값을 찾는 함수. 3) 2차원 배열 초기화 함수, copy 함수. 4) move 함수. (Left, Up, Right, Down) 1) ~ 3) 함수는 취향대로 만들자. A형에서는 라이브러리를 사용해도 되므로 memset, memcpy를 익혀두는 것도 괜찮다. (하지만 B형.. 2021. 2. 7.
BOJ 9012 : 괄호 알고리즘 문제 전체 링크 www.acmicpc.net/problem/9012 올바른 괄호인지 체크하는 문제이다. 실제로 작성하는 cpp 코드를 생각하면 쉽다. 코드를 작성할 때, 열린 괄호 '('를 썼다면 반드시 닫힌 괄호 ')'를 써야한다. 즉, 열린 괄호를 +1, 닫힌 괄호를 -1이라고 생각한다면 마지막에는 반드시 0이 되어야 한다. 열린 괄호 뒤에는 다시 열린 괄호 또는 닫힌 괄호가 와야한다. 그러므로, 괄호가 완전히 닫히기 전에 닫힌 괄호가 열린 괄호보다 많아서는 안된다. #include int main(void) { int T; scanf("%d", &T); for (int tc = 0; tc < T;tc++) { int i, flag, sp; char str[50 + 5]; flag = sp .. 2021. 2. 7.
BOJ 13460 : 구슬 탈출 2 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/13460 BOJ 삼성 SW 기출문제 중 첫번째 문제이다. 예전엔 삼성 S 직군도 GSAT으로 입사했다가 SW 역량 테스트로 변경된 걸로 안다. 첫 번째 시험 치곤 난이도가 높은 편인 듯... 고려해야할 사항이 많고 디버깅도 쉽지 않다. 특히 2차원 맵 디버깅은 맵 전체를 printf로 찍어줘야하는 경우가 대부분이다. 이럴 때는 output.txt로 출력하는 설정을 해두는게 편하다. 1) 구슬이 1칸 움직이는 것이 아니라 멈출 때까지 움직여야 한다. 2) 최대 10번까지 도달하는 지만 검사하면 된다. 3) 빨간 구슬은 들어가고, 파란 구슬은 들어가면 안된다. 최소.. 2021. 2. 6.
백준에서 삼성 SW 기출 문제 보는 방법 삼성 A형 전체 링크 문제집 -> 삼성 SW 역량 테스트 기출 문제 아래 링크, 스샷 참고. www.acmicpc.net/workbook/top 인기 문제집 - 1 페이지 www.acmicpc.net 2021. 2. 6.
삼성 SW 역량 테스트 A형 모의검정 문제 위치 삼성 A형 전체 링크 상단의 "신입 SW 역량 테스트란?"을 클릭 -> 모의검정 문제 예시 풀어보기 2021. 2. 6.
BOJ 10773 : 제로 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10773 스택 기본 구현 문제 BOJ 10828과 같은 문제이다. BOJ 10828보다 쉬운 점은, push, pop만 구현하면 된다. 정수가 "0"일 경우 지울 수 있는 수를 보장하므로 pop할때 stack pointer를 검사할 필요가 없다. 마지막에 더하는 경우는 stack에 들어있는 모든 값을 더하면 되므로, 0 ~ sp 까지 for문을 돌면 된다. #include int K; int stack[100100]; int sp; int main() { int sum; scanf("%d", &K); for (int i = 0; i < K; i++) { int in; scanf("%d", &in); if (in) stack[sp++] .. 2021. 2. 6.
BOJ 10828 : 스택 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10828 스택 기본 구현 문제이다. push, pop, size, empty, top을 구현해야 한다. 명령의 수가 최대 10000이므로 10000보다 큰 배열을 잡고, index 하나만 추가하면 stack이 완성된다. 즉 push할 때는 index = stack pointer = sp를 증가 시키고, pop할 때는 sp를 감소시킨다. 배열에 값을 넣고, sp를 증가시키면 들어오는 순서대로 값을 저장할 수 있다. stack[sp] = input, sp++; → stack[sp++] = input; 값을 입력하고 sp를 증가시켰기 때문에 바로 이전 값은 sp - 1에 있다. output = stack[sp - 1], sp--; → out.. 2021. 2. 5.
반응형

티스토리툴바