알고리즘

[백준 17406: 배열 돌리기 4] (C++)

삼성 A형 기출 문제 https://www.acmicpc.net/workbook/view/2771 ㄴ배열 돌리기 4 https://www.acmicpc.net/problem/17406 l 문제 1. 크기 NXM인 배열 ( 3 ≤ N, M ≤ 50 ) 2. 배열 A의 값은 각 행에 있는 모든 수의 합 중 최소값 3. 회전 연산 세 정수 (r, c, s)로 이루어져있다. ( 1 K; ans = 987654321; A.resize(N + 1, vector(M + 1)); register int i, j; for (i = 1; i A[i][j]; for (i = 1; i > rot_data[i].r >> rot_data[i].c >> rot_data[i].s; seq.push_back(i); } // 1. 돌리..

[백준 17837: 새로운 게임 2] (C++)

삼성 SW역량 테스트 https://www.acmicpc.net/workbook/view/2771 ㄴ새로운 게임 https://www.acmicpc.net/problem/17780 풀이: https://11001.tistory.com/26 ㄴ새로운 게임 2 https://www.acmicpc.net/problem/17837 l 문제 [백준 17780: 새로운 게임] 과 다른 점 가장 아래에 있는 말이 아니여도 이동 할 수 있다. 이동할 땐 마찬가지로 위에 쌓여있는 말과 같이 이동한다. 1 3 5 2 4 순으로 쌓여 있을 때 1 : 1 3 5 2 4 이동 2 : 2 4 이동 3 : 3 5 이동 4 : 4 이동 5 : 5 이동 이렇게 된다. l 풀이 매 턴 마다 1 ~ K 번 말을 차례로 이동시키면 됩니다...

[백준 17281: 야구] (C++)

삼성 A형 기출 문제 https://www.acmicpc.net/workbook/view/2771 ㄴ야구⚾ https://www.acmicpc.net/problem/17281 l 문제 1. 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임 한 야구팀의 감독 아인타는 가장 많은 득점을 찾는 타순을 찾아서 그 때의 득점을 구하려고 한다. 2. 선수 1번 부터 9번까지의 선수가 있다. 3. 타자 실제로 타석에 올라가서 공을 치는 선수이다. 어떤 선수가 몇 번째 타자인지 정하는 것을 타순을 정한다고 한다. 타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다. 1: 안타: 타자와 모든 주자가 한 루씩 진루한다. 2: 2루타: 타자와 모든 주자가 두 루씩 진루한다. 3..

[백준 17780: 새로운 게임] (C++)

삼성 SW역량 테스트 https://www.acmicpc.net/workbook/view/2771 ㄴ새로운 게임 https://www.acmicpc.net/problem/17780 l 문제 1. 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 2. 체스판 크기는 N×N 각 칸은 힌색, 빨간색, 파란색 중 하나로 색칠되어있다. 3. 말 사용하는 말의 개수는 K개( 1번 부터 K번 까지 번호 매겨짐 ) 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판 위에 말 K개를 놓고 시작 4. 턴 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 이동시키는 차례의 말이 가장 아래에 위치한다면 이동이 가능하다. 5. 이동 이동하려는 칸의 색에 따라서 다음의 행동을 한다. 흰색 그..

[백준 17825: 주사위 윷놀이] (C++)

삼성 SW 역량 테스트 https://www.acmicpc.net/workbook/view/1152 ㄴ주사위 윷놀이 https://www.acmicpc.net/problem/17825 l 문제 1. 주사위를 굴려서 나온 수 만큼 말을 이동시키는 윷놀이 게임이다. 일반적인 윷놀이 게임과 규칙은 동일하지만 첫 번째 코너를 밟고나서 중앙을 밟지 않아도 무조건 도착 지점으로 꺾는다. ( 원래 윷놀이는 중앙을 밟지 않으면 그대로 직진 ) 2. 말 처음 시작 지점에 말 4개가 있다. 말은 순서와 상관 없이 아무 말이나 이동시킬 수 있고 이동하려는 칸에 이미 말이 있으면 이동할 수 없다. ( 시작, 도착 칸 제외 ) 도착 지점 넘어가면 도착 지점에서 이동을 마치며, 도착한 말은 더 이상 이동할 수 없다. 말이 이동을..

[백준 17822: 원판 돌리기] (C++)

삼성 SW 역량 테스트 https://www.acmicpc.net/workbook/view/1152 ㄴ원판 돌리기 https://www.acmicpc.net/problem/17822 l 문제 1. 중심이 같은 원판들을 주어진 조건에 따라 회전시킨다. 2. 원판 원판은 반지름이 1부터 N까지 크기 순서대로 놓여있다. ( 1이 가장 위 ) 3. 원판의 숫자 각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. ( x, y )는 ( x + 1, y ), ( x - 1, y ), ( x, y -1 ) ,( x, y + 1) 과 인접하다. 간단하게 동서남북 4방향으로 생각하면 된다. 주의할 점 y = 0 일 때 y - 1 위치는 -1이 아닌 M-1로 y = M-1..

[백준 17779: 게리맨더링 2] (C++)

삼성 SW 역량테스트 기출 문제 https://www.acmicpc.net/workbook/view/1152 ㄴ게리맨더링 2 https://www.acmicpc.net/problem/17779 l 문제 1. 재현시의 시장 구재현은 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 2. 재현시 는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 3. 선거구, 구역 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있..

C++ 정렬 알고리즘 (버블정렬, 삽입정렬, 선택정렬, 합병정렬, 퀵정렬, 힙정렬, 셀정렬, 기수정렬)

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. 업데이트 중입니다. 버블 정렬( Bubble Sort ) 삽입 정렬( Insertion Sort ) 선택 정렬( Selection Sort ) 합병 정렬( Merge Sort ) 퀵 정렬( Quick Sort ) 힙 정렬( Heap Sort ) 셸 정렬( Shell Sort ) 기수 정렬 ( Radix Sort ) ◾ 제자리 정렬 정렬에 추가적인 메모리 공간이 들지 않는다. 아예 안 드는 것은 아니고 거의 무시할 정도의 메모리를 사용한다. • Insertion, Bubble, Selection, Quick • Tip : 최악이 O(n^2)인 것들이라고 기억 ◾ 안정 정렬 ( Stable Sort ) 정렬 전의 순서를 유지하고 정렬된다. • In..

[백준 17136: 색종이 붙이기] (C++)

삼성 A형 기출 문제 https://www.acmicpc.net/workbook/view/2771 ㄴ색종이 붙이기 https://www.acmicpc.net/problem/17136 l 문제 1. 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 2. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 3. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이..

[백준 17135: 캐슬 디펜스] (C++)

삼성 A형 기출 문제 https://www.acmicpc.net/workbook/view/2771 ㄴ캐슬 디펜스 https://www.acmicpc.net/problem/17135 l 문제 1. 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임 2. 게임이 진행되는 곳은 크기가 N×M인 격자판 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다. 3. 성을 적에게서 지키기 위해 궁수 3명을 배치 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 4. 궁수를 배치한 이후의 게임 진행 l 게임 진행 순서 1. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고,..