Henzee's Archive

백준 11053번 - 가장 긴 증가하는 부분 수열 (실버 2)     문제 분석수열 A가 주어졌을 때, 가장 긴 증가하는 부분 순열의 길이를 구하는 문제이다.예를 들어, 수열 A = { 10, 20, 10, 30, 20, 50 } 인 경우에 가장 긴 증가하는 부분 수열은 A = { 10, 20, 10, 30, 20, 50 } 이고, 길이는 4이다.  문제 풀이핵심 아이디어는 DP를 이용해서 해당 수까지의 최대 길이를 저장해주고, 최대 길이를 구하는 것이다.예를 들어, 수열 A = { 10, 20, 30, 25, 10, 30, 40, 50 } 가 있다고 하자. 첫 번째 10보다 작은 숫자가 없었으므로 최대 길이는 1이 된다.두 번째 20보다 작은 숫자인 10의 최대 길이가 1이므로 +1을 한 2가 최대 길..

백준 1003번 - 피보나치 함수 (실버 3)     문제 이해N번째 피보나치 수를 구할 때 0과  1이 각각 몇 번 출력되는지 구하는 문제이다.  문제 해결 방법시간 제한이 0.25초라서 재귀 함수로 풀게 되면 시간 복잡도가 O(2ⁿ)이 되므로 시간 초과가 난다.동적 프로그래밍 (DP)을 사용하면 dp 배열을 한 번만 채우면 되므로 시간 복잡도가 O(N)이 된다.따라서 DP를 이용해서 문제를 풀면 된다. 먼저, 점화식을 사용해서 0과 1이 출력된 횟수를 구해준 다음 N일 때 값을 출력하면 된다.1. dp[0][n] = fibonacci(n)을 호출했을 때 0이 호출된 횟수, dp[1][n] = fibonacci(n)을 호출했을 때 1이 호출된 횟수2. 점화식 dp[0][n] = dp[0][n - 1] ..

백준 1946번 - 신입 사원 (실버 1)     문제 분석채용에 선발되기 위해서는 다른 모든 지원자보다 서류 순위나 면접 순위가 적어도 하나는 높아야 한다.예를 들어, 지원자들의 서류/면접 순위가 아래와 같다면[3, 2] [1, 4] [4, 1] [2, 3] [5, 5][5, 5] 순위를 가진 지원자는 서류 순위와 면접 순위 모두 다른 지원자들 보다 낮기 때문에 선발될 수 없어서 선발 인원은 4명이 된다.  처음 시도처음 생각해낸 아이디어는 아래와 같다.1) 서류 순위를 오름차순 정렬한다.2) 두 번째 지원자부터 자기 앞에 있는 모든 지원자와 비교하여 면접 순위를 비교한다.3) 해당 지원자의 면접 순위가 앞에 있는 지원자들 보다 면접 순위가 낮다면 선발한다. 아이디어대로 구현했더니, 시간 초과가 났다...

백준 17503번 - 맥주 축제 (실버 1)      문제 설명K종류의 맥주가 있고, N일동안 하루에 1병씩만 맥주를 마실 수 있다. 각 맥주 별로 선호도와 도수 레벨이 존재하는데 N일 동안 마시는 N개의 맥주의 선호도 합이 M 이상이어야 하며 그 조건을 만족하는 맥주 중 도수 레벨이 가장 큰 것을 출력하면 되는 문제이다.    쉽게 생각하고 접근했다가, 푸는데 시간이 너무 오래 걸렸던 문제이다.    처음 접근했던 방식은 K개 중 N개를 골라서 선호도의 합이 M 이상이 되도록 하는 도수 레벨의 최솟값을 구하는 것이었다.즉, 조합을 사용해 N개를 고르고 그 때의 선호도 합이 M 이상이 되는지 확인하고 넘으면 고른 맥주 중에서 도수 레벨이 가장 큰 값을 출력하는 방법이다. 그러나, 조합을 하는 과정에서 모..

백준 1759번 - 암호 만들기 (골드 5)     문제 분석알파벳 C개가 주어지고, 그 중 서로 다른 L개의 알파벳으로 구성된 암호를 모두 출력하는 문제이다. (3 ≤ L ≤ C ≤ 15)주어진 조건은 3가지가 있다.모음(a, e, i, o, u)은 1개 이상 포함할 것자음은 2개 이상 포함할 것알파벳 순서 상 오름차순으로 정렬할 것 처음 시도알파벳이 오름차순으로 정렬된 상태여야 한다는 조건을 보고, 조합이 아닌 순열을 떠올렸다.순열을 사용해서 모든 경우의 수를 만들고 난 뒤 자모 개수를 체크하는 방식으로 풀었더니 시간 초과가 났다😹😹#include #include #include #include using namespace std;int L, C;vector alphabet;vector selec..

백준 2615번 - 오목 (실버 1)    조건19 × 19 크기의 바둑판연속된 5개의 돌이 있으면 승리 (가로, 세로, 대각선 방향)6개 이상 연속되면 승리 아님이긴 돌의 색과 가장 왼쪽에 있는 바둑알의 위치 출력 (세로 방향이면 가장 위쪽)  문제 자체는 기존에 알던 오목과 똑같아서 이해하는데 어렵지 않았다. 구현하는데 있어서 조건이 까다롭다고 생각해서 아이디어를 정리하고 바로 구현을 시작했다.   처음 생각한 아이디어는검은돌 혹은 흰돌을 발견한 시작점에서 8방 탐색을 진행한다.탐색 시 같은 색의 돌이 존재하면 그 방향으로 쭉 내려가며 돌의 개수를 카운트한다.돌의 개수가 5개가 되면 그 다음 방향에 돌이 있는지 확인하고 없으면 시작점의 위치와 돌의 색을 출력하고 종료한다.돌의 개수가 6개 이상이면 다..

백준 2529번 - 부등호 (실버 1)     문제 분석모든 부등호 관계를 만족하는 K+1 자리의 정수 중 최대값과 최소값을 구하는 문제이다.부등호 관계를 만족하는 각 숫자는 0~9 범위의 숫자이고, 중복이 되지 않게 사용해야 하는 조건이 있다. 알고리즘0부터 9까지 10개의 숫자 중에서 K+1개를 고른다. → 순열 사용 (백트래킹)고른 숫자가 부등호 사이에 들어갈 수 있는지 확인한다.유효하지 않다면, 탐색을 종료한다. 유효하다면, 최대값과 최소값을 갱신한다.모든 탐색을 마친 뒤, 최소값이 0으로 시작한다면 맨 앞자리에 0을 추가하고 정답을 출력한다.  최종 제출 코드※ 주의할 점최대값과 최소값은 최대 9자리의 숫자이므로 long long 타입의 변수로 값을 저장한다.int 타입인 K+1과 size_t ..

백준 1051번 - 숫자 정사각형 (실버 3)     문제 분석꼭짓점의 수가 모두 같은 정사각형의 최대 크기를 구하는 문제이다.N과 M의 크기가 최대 50이라는 조건을 보고 완전 탐색을 해도 시간 초과가 안나겠구나 생각했다. 알고리즘정사각형의 최소 크기는 1이다.꼭짓점의 수가 모두 같은 정사각형이 될 수 있는 최대 변의 길이부터 변의 길이가 2가 될 때까지 탐색하며 꼭짓점의 수가 모두 같은 경우 해당 길이를 이용해 크기를 구해주면 답이 된다.예를 들어, 5 X 6 크기의 직사각형인 경우 최대 변의 길이는 5가 된다. 최대 변의 길이가 5일 때 조건을 만족하는 정사각형이 있는지 확인하고, 있다면 넓이(변의 길이 X 변의 길이)를 구해준 뒤  출력하고 종료한다.만약, 해당 조건을 만족하는 정사각형이 없다면 ..

백준 1018번 - 체스판 다시 칠하기 (실버 4)     문제 분석주어진 입력을 보고 8×8 체스판을 만들기 위해 칠해져 있는 색을 바꿔야하는 최소 개수를 출력하는 문제이다. 처음 시도체스판은 흰색으로 시작하거나 검은색으로 시작하는 두 가지 경우가 있으므로, 2차원 벡터에 두 가지 경우의 체스판을 저장하고 입력된 값과 비교하며 바꿔야하는 색의 개수를 카운트해서 최소값을 구해야겠다고 생각했다.중간 점검을 해보니, 테스트 케이스 일부는 맞고 일부는 틀리길래 breakpoint를 사용해 디버깅하며 알고리즘 오류를 찾아냈다.#include #include #include using namespace std;const vector> chess_white = { {'W', 'B', 'W', 'B', 'W', 'B..

백준 2573번 - 빙산 (골드 4)     문제 분석주어진 빙산의 높이 정보를 가지고 매 년마다 빙산이 녹으면 몇년 후 최초로 빙산이 2개 이상으로 분리되는지 찾는 문제이다. 만약, 모두 다 녹을 때까지 분리되지 않으면 0을 출력한다.먼저 큰 로직 두 개를 세우고 구현했다.첫 번째, 빙산을 녹이는 작업 : DFS로 구현두 번째, 빙산이 분리됐는지 확인하는 작업 : DFS로 구현 처음 시도코드를 작성하면서도 반복문을 실행할 때마다 방문 배열을 초기화해주는 것이 비효율적이라고 생각했다. 그리고 DFS() 메서드에서 종료 조건이 어떤 것인지 몰라서 x == M && y == N으로 해주었는데, 이 부분도 미심쩍었다. 아니나 다를까 틀렸습니다...#include #include using namespace s..