기록창고

Jürgen from Pixabay">Image by Jürgen from Pixabay  https://www.acmicpc.net/problem/3197 1. 개요 이 문제는 2차원 배열의 호수가 주어진다. 호수의 각 요소는 물('.'), 얼음('X'), 백조('L') 중 하나이고 백조는 총 2마리가 존재한다. 그리고 물과 상하좌우 중 한 곳이라도 접촉한 얼음은 하루가 지나면 녹아서 물이 된다. 이 때, 상하좌우로만 이동할 수 있는 백조는 며칠 후 서로 만날 수 있는지를 구하는 문제이다. 이 문제의 알고리즘 분류에서도 알 수 있듯, 너비 우선 탐색(BFS)을 이용하여 문제를 풀었다. 처음에는 두 백조가 서로 만날 수 있는지 구하는 코드는 항상 하던 것처럼 큐를 이용하면 될 것이라 생각했다. 그리고 얼..

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][가방 용량 - 현재 물건 무게] + 현재 물건 가치)만약 가방에 담을 수 없는 경우현재 물건 순서에서 현재 가방 용량에서 최대 만족도 =..

1. 간단한 논리 연산 https://school.programmers.co.kr/learn/courses/30/lessons/181917 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr #include #include #include bool solution(bool x1, bool x2, bool x3, bool x4) { bool answer = true; answer = (x1 || x2) && (x3 || x4); return answer; } 문제의 주어진 식, (x1 ∨ x2) ∧ (x3 ∨ x4)에서 ∨가 ||, ∧가 &&이므로 그대로 적용하..

1. 마지막 두 원소 https://school.programmers.co.kr/learn/courses/30/lessons/181927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr #include #include using namespace std; vector solution(vector num_list) { vector answer; answer = num_list; int lastItem = num_list[num_list.size() - 1]; int befLastItem = num_list[num_list.size() - 2]; if (las..

1. 코드 처리하기 https://school.programmers.co.kr/learn/courses/30/lessons/181932 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr #include #include using namespace std; string solution(string code) { string answer = ""; int mode = 0; for (int i = 0; i < code.size(); ++i) { if (code[i] == '1') mode = !mode; else { if (mode == 0 && i % 2 == ..

HTML 삽입 미리보기할 수 없는 소스 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이번 문제는 주어진 조건에 따라 계단을 끝까지 올라갔을 때, 점수의 최대값을 구하는 문제이다. 이 문제는 2년 전에 처음 접했다가 다른 분의 풀이를 보고 그대로 적용했었던 문제라 다시 한 번 복습할 겸 풀어 보았다. 처음에는 재귀함수처럼 문제를 풀었지만 제대로 풀리지가 않았다. 그래서 다시 한 번 생각해보니 계단을 처음부터 올라가는 문제, 즉 처음부터 점진적으로 답을 찾..

HTML 삽입 미리보기할 수 없는 소스 다이나믹 프로그래밍 문제를 풀면서 느낀 것이 있다. 문제 풀이의 유형이 크게 재귀 함수를 이용하는 방법과 반복문을 이용하는 방법으로 나뉜다는 것이었다. 물론 모든 문제가 이런 것은 아니며, 또 문제를 푸는 사람에 따라 다른 방식을 이용할 수도 있을 것이다. 어쨌든 내가 문제를 풀 때에는 크게 두 가지 유형으로 나뉘는 느낌이었다. 그래서 이 두 유형의 차이점을 간단하게 기록하려고 한다. 1. 재귀함수 큰 문제를 작은 문제로 나누어 해결하는 방식 복잡한 문제에서 시작해 딱 필요한 하위 문제만을 해결하기 위함 스택 오버플로우같은 문제가 발생할 위험이 있음 피보나치 수열, 최소 편집 거리 등, 재귀적 구조가 명확한 문제에 적합 2. 반복문 작은 문제부터 시작해 점차 큰 문..