기록창고

Gerd Altmann from Pixabay">Image by Gerd Altmann from Pixabay  링크  이 문제는 이전에 풀어본 문제인데 풀어본지 너무 오래되어 다시 풀어보았다. 아무튼 이 문제는 일련의 숫자들이 주어질 때, 각 순간의 중간값을 알아내는 문제이다. 이를 위해서는 숫자들을 정렬할 필요가 있어 보인다. 하지만 시간 제한도 그렇고, 숫자가 주어질 떄마다 정렬을 하는 것은 별로 좋은 방법이 아닌 것 같다. 그래서 이전에 제출한 코드를 통해, 일이 정렬하지 말고 중간값을 알아내기 위한 두 개의 힙 혹은 우선수위 큐를 이용하면 좋다는 힌트를 얻게 되었다.  예를 들어 특정 시점에서 주어진 숫자들이 1, 5, 4, 7, 2, 6, 3, 인 경우, 이를 1, 2, 3, 4, 5, 6, ..

Pixabay로부터 입수된 Lukas Kurth님의 이미지 입니다.">Pixabay로부터 입수된 Lukas Kurth님의 이미지 입니다. 1. 개요 이번에 배낭 문제(KnapSack Problem)를 포함한 DP 문제를 위주로 풀어보았다. 배낭 문제를 풀 때 중요한 점을 간단히 요약하자면 다음과 같다.만약 가방에 담을 수 있는 경우현재 물건 순서에서 현재 가방 용량에서 최대 만족도 = 현재 물건 안 담은 경우, 현재 물건 담은 경우 중 더 큰 값예: dp[물건 index][가방 용량] = max(dp[물건 index - 1][가방 용량], dp[물건 index - 1][가방 용량 - 현재 물건 무게] + 현재 물건 가치)만약 가방에 담을 수 없는 경우현재 물건 순서에서 현재 가방 용량에서 최대 만족도 =..

Pixabay로부터 입수된 eommina님의 이미지 입니다.">Pixabay로부터 입수된 eommina님의 이미지 입니다.  링크: https://www.acmicpc.net/problem/21736  이 문제는캠퍼스 지도의 가로, 세로 길이가 주어지고, 지도의 빈 공간과 벽 등이 문자 혹은 문자열로 주어진다. 그리고 'I'에서 시작해서 몇 명의 친구('P')를 찾을 수 있는지 알아내는 문제이다. 이 문제는 가장 기본적인 형태의 DFS(혹은 BFS) 문제이기에 아래의 절차대로 진행되게 코드를 작성하였다. N, M, N x M 크기의 캠퍼스 값을 입력 받는다. 캠퍼스에서 'I'의 위치를 저장한다.(n, m) 좌표를 인자로 받는 DFS 함수를, 2번 과정의 위치 좌표를 기준으로 실행한다.만약 (n, m)를 ..

1. 개요 오랜만에 알고리즘 문제를 풀려고 했는데 너무 많이 쉰 탓인지 예전에 풀었던 문제들도 너무 어렵게 느껴졌다. 그래서 쉬운 순열, 조합 문제부터 차근차근 문제를 다시 풀어 나가려고 한다. 우선, 순열과 조합을 간단히 말하자면 다음과 같다.순열 (Permutation): 순서를 고려해 n개의 원소 중 r개를 고르는 경우의 수. => 순서 O, 중복 X같은 원소더라도 순서가 다르면 다른 경우로 취급중복 순열 (Repetition Permutation): n개의 원소 중 r개를 중복을 허용하여 순서를 고려해 고르는 경우의 수. => 순서 O, 중복 O같은 원소를 여러 번 선택 가능하며, 순서를 다르게 하면 다른 경우로 취급조합 (Combination): 순서를 고려하지 않고 n개의 원소 중에서 r개를 ..

HTML 삽입 미리보기할 수 없는 소스 https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 이번 문제는 운동 일수 N, 운동 키트 개수 K, 그리고 K개의 (운동 키드 별) 중량 증가량이 주어졌을 때, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 구하는 문제이다. 이 문제의 알고리즘 분류에서도 확인할 수 있듯, 모든 경우를 검사해야 하는 문제이다. 그리고 예제의 그림(표)에서도 확인할 수 있듯, 만약 운동 키트가 3..

HTML 삽입 미리보기할 수 없는 소스 https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 이번 문제는 맵의 크기를 나타내는 R, C, 이동 거리 K, 그리고 전체 맵이 주어졌을 때 K를 충족하는 경우의 수를 구하는 문제이다. 문제의 예시에서도 알 수 있듯, 이 문제는 가능한 모든 경우를 검사하면 풀 수 있을 것이다. 그리고 문제의 시간 제한이 2초인데다 R과 C의 값이 최대 5이기에 시간초과를 걱정하지 않아..

HTML 삽입 미리보기할 수 없는 소스 https://school.programmers.co.kr/learn/courses/30/lessons/12973 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 문자열이 주어졌을 때, 같은 알파벳이 2개씩 붙어있는 것들을 제거해나갔을 때 모든 알파벳을 제거할 수 있는지 검사하는 문제이다. 처음에는 단순무식하게 주어진 문자열 s를 구성하는 문자들을 일일이 검사하게 구현하였다. #include #include using namespace std; int solution(string s) { // 만약 문자열..

HTML 삽입 미리보기할 수 없는 소스 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 이번 문제는 N과 NxN 크기의 복도 구조가 주어질 때, 장애물을 단 3개만 설치해서 모든 학생들이 감시당하지 않을 수 있는지를 알아내는 문제이다. 우선 장애물과 관련된 사항들을 살펴보자. 무조건 3개의 장애물을 설치해야 한다. 빈 칸('X')에만 장애물을 설치할 수 있다. 선생님은 장애물 뒤편은 감시할 수 없다. 장애물을 설치하는 데에 있어 특별히..