프로그래밍/알고리즘

    BOJ 1012 · 유기농 배추

    알고리즘 분류 : DFS 배추 밭에 놓아야 하는 배추흰지렁이의 마릿수를 구해야 한다. 배추흰지렁이는 하나의 배추 그룹에 한 마리만 놓으면, 최소 마릿수가 된다. 즉, 이 문제는 배추 그룹의 수를 세는 플러드 필 문제이다. 배추가 인접한 상하좌우로 연결되면, 이것은 하나의 배추 그룹이 된다. 우선 N*M 사이즈의 배열 A를 만들고 모든 좌표를 0으로 둔다.입력으로 주어지는 배추의 좌표 (X, Y)를 배열 A에 1로 둔다.N*M 사이즈의 맵을 DFS를 통해 모든 곳을 방문할 때까지 완전 탐색한다.DFS로 다음 좌표를 이동할 때, 배추(1)로만 이동한다.테스트케이스가 여러 개 주어지므로, 초기화가 매번 필요하다. C++ 소스코드 #include #include int m, n, k, ans; int a[51]..

    BOJ 17070 · 파이프 옮기기 1

    알고리즘 분류 : 백트래킹 파이프를 옮겨서 한쪽 끝을 (N, N)으로 이동시키는 방법의 개수를 구해야 한다. 파이프는 2칸을 차지하지만, 파이프의 끝만 고려하면 된다. 파이프의 상태는 3가지로 나눌 수 있다. 1. 가로로 놓여있는 상태 (0) : 가로(0) → 가로(0) 또는 대각선(2)2. 세로로 놓여있는 상태 (1) : 세로(1) → 세로(1) 또는 대각선(2)3. 대각선으로 놓여있는 상태 (2) : 대각선(2) → 가로(0) 또는 세로(1) 또는 대각선(2)가로(0)에서 세로(1)로 곧바로 이동할 수 없고, 세로(1)에서 가로(0)로 곧바로 이동할 수 없다. 재귀 함수의 인자는 (X 좌표, Y 좌표, 파이프 상태) 이다.현재 파이프 상태에 따라서 다음 이동의 파이프 상태를 위의 3가지 조건에 따라 ..

    BOJ 2156 · 포도주 시식

    알고리즘 분류 : 다이나믹 프로그래밍 N개의 포도주 잔이 있을 때, 최대로 마실 수 있는 포도주의 양을 구해야 한다. DP를 이용하여 포도주 마시는 규칙에 따라 구현하면 된다. 포도주는 연속으로 3잔 이상 마실 수 없다. 즉, 연속하여 마실 수 있는 포도주는 최대 2잔이다.D[N] : N 번째 잔의 포도주를 마셨을 때, 최대로 마실 수 있는 포도주의 양 D[N]은 3가지 경우의 수로 나눌 수 있으며, 3가지 값 중 가장 큰 값이 D[N]이 된다.1. N 번째 잔을 마시지 않은 경우 : D[N-1]2. N 번째 잔이 연속 1잔째 마신 경우 : D[N-2] + P[N] (N-1 번째 잔은 마시지 않아야 한다.)3. N 번째 잔이 연속 2잔째 마신 경우 : D[N-3] + P[N-1] + P[N-1] (N-2..

    BOJ 17135 · 캐슬 디펜스

    알고리즘 분류 : 브루트 포스, 시뮬레이션 궁수를 성에 적절히 배치하여 적을 최대한 많이 죽이도록 구현하는 문제다. 가능한 궁수의 배치를 모두 만들고, 각 배치에서 적을 얼마나 쏴 죽일 수 있는지 카운트하면 된다. N*M 사이즈의 맵에서 궁수는 N+1번째 줄에 3명이 배치된다.궁수가 서로 겹치지 않도록, 3중 for문 또는 재귀를 통해 각각 배치한다. 조합 방식으로 구현하면 된다.그리고 배치한 위치의 인덱스를 별도로 저장한다. 아래의 코드에서는 archer 배열에 Y좌표(열 인덱스)가 저장되어 있다.각 배치에서 궁수로부터 적이 얼마나 떨어져 있는지 계산하고, 각 적을 죽여야 한다. 1. 궁수의 위치를 (N, K)라고 하고, 적의 위치를 (i, j)라고 하자. 단, (0≤i<N, 0≤j<M) 이다.2. 궁..

    BOJ 9465 · 스티커

    알고리즘 분류 : 다이나믹 프로그래밍 스티커를 떼어내어 얻을 수 있는 최대 점수를 DP를 이용하여 구해야 한다. D[N][M] : N번째 열에서 스티커를 M했을 때, 2xN 개의 스티커에서 얻을 수 있는 최대 점수M = 0 (위쪽 스티커를 뜯음), M = 1 (아래쪽 스티커를 뜯음), M = 2 (둘 다 뜯지 않음)D[1][0] = P[1][0], D[1][1] = P[1][1], D[1][2] = 0D[N][0] : N번째 열에서 위쪽 스티커를 뜯어서 얻은 최대 점수D[N][1] : N번째 열에서 아래쪽 스티커를 뜯어서 얻은 최대 점수D[N][2] : N번째 열에서 둘 다 뜯지 않고 얻은 최대 점수 C++ 소스코드 #include #include using namespace std; int n, d[1..

    BOJ 2193 · 이친수

    알고리즘 분류 : 다이나믹 프로그래밍 N자리 이친수를 DP를 통해 만들어야 한다. D[N] : N자리 이친수의 개수D[1] = 1, D[2] = 1D[N] = 0으로 끝나는 N-1자리 이친수 + 01로 끝나는 N-2자리 이친수 C++ 소스코드 #include int n; long long int d[91]; void solve() { d[1] = d[2] = 1; for (int i=3; i

    BOJ 11057 · 오르막 수

    알고리즘 분류 : 다이나믹 프로그래밍 오르막 수를 DP로 구현하는 문제다. 오르막 수란 각 자리의 수가 오름차순을 이루는 숫자를 말한다. 0으로 시작할 수 있으며, 인접한 자리의 숫자가 같아도 오르막 수이다. D[N][M] : M으로 끝나는 N자리 오르막 수D[1][0] = 1, D[1][1] = 1, ‥‥ , D[1][9] = 1D[N][0] = D[N-1][0] : 0으로 끝나는 N자리 오르막 수D[N][1] = D[N-1][0] + D[N-1][1]D[N][2] = D[N-1][0] + D[N-1][1] + D[N-1][2]‥‥D[N][9] = D[N-1][0] + D[N-1][1] + ‥‥ + D[N-1][9] C++ 소스코드 #include int n, ans; int d[1001][10]; c..

    삼성 SW 역량 테스트 문제 리스트

    + 삼성 소프트웨어 역량 테스트란? 삼성(삼성전자, 삼성 SDS 등) 채용 단계에서 S직군이 보는 오프라인 코딩 테스트(직무적성검사)이다.SW 개발 직무에 지원한다면, GSAT 대신 소프트웨어 역량테스트를 봐야 한다. + SW 역량테스트 준비 프로그래밍 언어를 익힌다. C/C++, Java, Python3 중 (C++ 추천)자료구조(큐, 스택, 덱, 그래프 등)와 알고리즘 이론(DFS, BFS, 힙, 백트래킹 등)을 배운다.알고리즘 스킬(재귀 구현, 비트 연산, STL 사용법 등)을 익힌다.백준 온라인 저지와 SW Expert Academy에서 알고리즘 문제를 풀면서 연습한다.역대 기출은 시뮬레이션, BFS, DFS, 브루트 포스 등의 문제로 출제되었으므로, 이러한 유형을 집중적으로 푼다.SWEA에서 모..