본문 바로가기

알고리즘

BOJ 14500 · 테트로미노 알고리즘 분류 : 브루트 포스테트로미노를 N*M 종이 맵에 하나 두었을 때, 얻을 수 있는 합의 최대를 구해야 한다. 테트로미노란 정사각형 4개를 이어붙인 도형이다. 문제에 주어진 5개의 테트로미노는 각각 회전, 대칭이 가능하다. 회전, 대칭을 모두 고려하면, 서로 다른 모양의 도형을 총 19가지 만들 수 있다.19가지의 도형을 모두 만든다.각 도형에서 하나의 사각형을 중심으로 인덱스를 설정한다. (그림 참조)각 도형 중에..
BOJ 15686 · 치킨 배달 알고리즘 분류 : 브루트 포스집과 치킨집과의 거리를 각각 구해서 최소의 치킨 거리를 구하는 문제다. 여러 개의 치킨 집에서 M개의 치킨 집을 고른 후, 문제에 주어진 조건대로 치킨 거리를 구해서 답을 찾아야 한다.입력받을 때, 치킨집(2)의 개수와 집(1)의 개수를 세고, 각 좌표 (X, Y)를 리스트에 저장한다.치킨집의 총 개수를 K개라고 할 때, 재귀 함수를 통해 K개 중 M개를 골라야 한다. 조합 방식으로 고르면 된다.M개의 ..
BOJ 15684 · 사다리 조작 알고리즘 분류 : 브루트 포스, 백트래킹사다리를 적절히 만들어서 사다리 타기를 해야하는 문제다. 가로줄은 최대 3개까지 놓을 수 있고, 최솟값을 출력하면 된다. 출발한 사다리 번호(세로줄)와 도착한 사다리 번호가 모두 같아야 사다리를 제대로 탄 것이다. 가능한 사다리를 모두 만들면 시간 초과될 수 있으므로, 적절히 백트래킹을 하여 경우의 수를 줄여야 한다.주어진 입력을 통하여 H*N 사이즈의 사다리를 만든다.A번 세로줄과 A+1번 세로줄의 사이에 B..
삼성 SW 역량 테스트 기출 문제 및 정답 삼성 소프트웨어 역량 테스트란?삼성(삼성전자, 삼성 SDS 등) 채용 단계에서 S직군이 보는 오프라인 코딩 테스트(직무적성검사)이다.SW 개발 직무에 지원한다면, GSAT 대신 소프트웨어 역량테스트를 봐야 한다.SW 역량테스트 준비프로그래밍 언어를 익힌다. C/C++, Java, Python3 중 (C++ 추천)자료구조(큐, 스택, 덱, 그래프 등)와 알고리즘 이론(DFS, BFS, 힙 등)을 배운다.알고리즘 스킬(재귀 구..
BOJ 14890 · 경사로 알고리즘 분류 : 시뮬레이션경사로를 만들어서 지나갈 수 있는 길의 개수를 구하는 문제다. 문제에 주어진 조건에 따라 그대로 구현해야 한다.지나갈 수 있는 길을 확인하기 위해 가로 방향과 세로 방향을 구분해서 순차 탐색해야 한다.먼저 현재 칸의 높이 A와 다음 칸의 높이 B를 구하고, B-A를 D라고 하자.D가 0이라면, 길의 높이가 같은 경우이다.D가 1이라면, 올라가는 경사로가 필요한 경우이다.D가 -1이라면, 내려가는 경사로가 필요한 경..
BOJ 15662 · 톱니바퀴 (2) 알고리즘 분류 : 시뮬레이션T개의 톱니바퀴를 회전시키는 시뮬레이션 문제다. BOJ 14891번 '톱니바퀴'와 유사한 문제이다. 자세한 내용은 이전 문제 참조.톱니바퀴의 수는 T개이다. 최대 1,000개.정답은 12시 방향에 S극(1)이 몇 개 있는지만 세면 된다.C++ 소스코드#include <cstdio> int a[1000][8]; int t, k, ans; void rotate(int n, int d) { int t[8];..
BOJ 14891 · 톱니바퀴 알고리즘 분류 : 시뮬레이션톱니바퀴의 회전 동작을 시뮬레이션하는 문제다. 문제는 어렵지 않으나, 회전 방향이 헷갈려서 귀찮은 문제다.입력으로 주어지는 톱니바퀴를 기준으로 시작한다.톱니바퀴의 인덱스는 12시 방향부터 시계방향으로 [ 0 1 2 3 4 5 6 7 ] 로 둔다.1. 기준 톱니바퀴의 왼쪽에 톱니바퀴가 있다면, 기준 톱니바퀴의 왼쪽 톱니(인덱스 6)와 왼쪽 톱니바퀴의 오른쪽 톱니(인덱스 2)를 비교한다.2. 극이 다르다면, ..
BOJ 3190 · 뱀 알고리즘 분류 : 시뮬레이션주어진 조건을 그대로 구현하는 시뮬레이션 문제다. 뱀이 사과를 먹으면서 길이를 늘리는 게임을 구현해야 한다.뱀의 시작 위치는 (0, 0)이며 시작 방향은 오른쪽이다. 범위 (0, 0) ~ (N-1, M-1) 기준뱀의 이동 좌표를 저장하기 위해 Queue를 사용한다.매초, 뱀이 현재 방향으로 머리를 먼저 한 칸 앞으로 옮긴다. 머리 위치를 큐에 push 한다.이동한 칸에 사과(1)가 있을 경우, 꼬리를 줄이..
BOJ 14499 · 주사위 굴리기 알고리즘 분류 : 시뮬레이션문제에 주어진 조건에 따라 주사위를 굴리는 문제다.먼저 주사위의 숫자를 임의로 고정시킨다.동서남북 방향에 따라 바뀌는 주사위의 숫자를 설정한다.방향에 따라 시뮬레이션 한다.아래의 그림을 참조. 주사위 모양에서 0이 윗면이고, 5가 바닥면이다.C++ 소스코드#include <cstdio> int n, m, x, y, k; int a[20][20]; int dice[6], temp[6]; const int dire..
BOJ 13458 · 시험 감독 알고리즘 분류 : 구현문제에 주어진 조건 그대로 구현하면 된다.총 감독관은 항상 1명 존재하므로, 문제의 정답은 N명 이상이다.부 감독관은 각 시험장에 남아있는 응시자의 수를 부 감독관 수로 나눠서 구할 수 있다.C++ 소스코드#include <cstdio> int n, b, c; int a[1000000]; long ans; void solve() { for (int i=0; i<n; i++) { if (a..
BOJ 14502 · 연구소 알고리즘 분류 : 브루트 포스, DFS연구소에 벽을 3개 세워서 바이러스를 최대한 덜 퍼트리고, 안전 영역의 최대 크기를 구하는 문제다. N*M은 최대 64이므로, 벽을 두는 모든 경우의 수를 구해서 최대 크기를 확인해 볼 수 있다.우선 입력으로 받은 맵에 벽을 3개 세워야 한다.벽(1)은 빈 칸(0)에만 세울 수 있다. N*M을 순회하면서 빈 칸이라면 벽을 둔다.벽을 두는 함수는 재귀로 구현한다. 벽 카운트를 세면서 3이 되면, DFS를 ..
BOJ 2151 · 거울 설치 알고리즘 분류 : BFS문에서 다른 문까지 빛으로 연결하기 위해 필요한 거울의 최소 개수를 구하는 문제다. 빛은 거울에서만 꺾이고, 거울은 45도 각도로 설치할 수 있다. 거울을 적절히 설치해서 문에서 문으로 빛을 연결해야 한다.문('#')은 항상 2개만 주어지므로, 하나의 문을 시작점으로, 다른 하나의 문은 도착점으로 둔다.BFS 탐색을 하면서 다음 이동 좌표가 갈 수 있는 곳인지 확인한다.방문 체크와 거울 설치 횟수를 저장할 배열 dist를 3차..