Algorithm

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 1. Logic 이 문제의 부분문제는 총 3가지로 나눌 수 있다. 1. 사자를 배치하지 않는 경우(항상) 2. 사자를 오른쪽에 배치하는 경우(이전에 사자를 왼쪽에 배치했을 때) 3. 사자를 왼쪽에 놓는경우 (이전에 사자를 오른쪽에 배치했을때) 이렇게 3가지 경우를 끊어서 해결해주면 된다. 아래 코드를 보면 이해가 될 것이다. 2. Code #include #include using namespace std; int n; int dp[100001][3]; int solve(int idx, int prev) { if(idx == n)..
https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 1. Logic dp배열이 의미하는 것은 배열에 해당하는 카드를 구매할때의 최댓값이다. dp[구매하는 카드 갯수] = 최댓값. 최댓값을 구하는 방법은 1개짜리 팩 + 카드 3개를 구매하는데 필요한 최댓값 2개짜리 팩 + 카드 2개를 구매하는데 필요한 최댓값 3개짜리 팩 + 카드 1개를 구매하는데 필요한 최댓값 4개짜리 팩 이렇게 경우의 수를 나눠볼 수 있다. 2. Code #include #include..
https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 1. Logic 우리는 가장 큰 정사각형의 크기를 구해야 한다. 그렇기 때문에 dp배열의 의미는 가장 큰 정사각형의 한변의 길이를 의미한다. 한 지점을 기준으로 정사각형이 되기위해 쪼개지는 부분문제는 총 3가지가 있다. 아래 대각선 오른쪽 이렇게 3방향으로 쪼개진다. 이 3개의 부분문제의 리턴값의 최솟값이 현재 위치에서의 최댓값이 된다. 2. Code #include #include #include using namespace std; int n, m; string ..
https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 1. Logic 두개의 수를 먼저 골라 합을 만들어 놓고 나머지 한개의 수를 골라 0이 되는 수를 카운트 하면 된다. 이 문제에서는 중복되는 수가 나올 수도 있기 때문에 원하는 수가 먼저 나오는 index(lower bound) 원하는 수가 나오는 가장 마지막 index(upper bound) 두개를 구해 빼주어 갯수만큼 구해줬다. 밑의 코드에서 tempSum에 -를 붙혀준 이유는 우리는 a+b+c=0..
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 1. Logic 전체 인원의 반을 나눠서 팀을 구성하기 때문에 기저조건을 N/2로 설정한 후 DFS를 진행한다. N/2까지 갔을 때 전체인원의 반은 check배열에 true로 표시되어있고 반은 false로 표시되어 있을 것이다. true로 선택된 번호는 스타트 팀에 배정을 하고 false인 인원은 링크 팀에 배정을 하여 DFS를 돌며 최소값을 구한다. 2. Code #include using namespace std;..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1. Logic 부분문제를 3가지로 나눌 수 있다. 포도주를 안마시는 경우 포도주를 1잔 연속해서 마시느 경우 포도주를 2잔 연속해서 마시는 경우 그래서 DP테이블을 정할 때 DP[현재 인덱스][선택 여부] 로 정의했다. 선택 여부 별 의미하는 바는 > 0:이전에 포도주 안마심, 1:이전에 한잔만 마심, 2:이전에 두잔 연속해서 마심 입력으로 받은 첫번째 수에서 선택할지 말지여부를 처리하는 것은, ..
https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 1. Logic 단순 다익스트라에 간단한 후처리를 요구하는 문제이다. 다익스트라로 첫 해킹을 당한 컴퓨터부터 시작해서 감염을 시키고 다익스트라 이후 dist배열 전체를 순회하여 INF가 아닌 배열들의 갯수를 세주면 감염되는 컴퓨터 수를 구할 수 있고 걸리는 시간은 전체 배열을 순회하며 가장 큰 배열의 값을 구하면 된다. 2. Code #include using namespace std; const i..
https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 1. Logic 불의 위치를 담은 queue fire과 지훈이의 위치를 담은 jihun queue 두개를 가지고 풀이했다. 불이 위치한 곳은 애초에 지훈이가 가지 못하고 지훈이가 움직이더라도 불이 오면 안되기 때문에 불을 먼저 BFS를 돌려 움직여줬다. 이후 불이 없는곳에 지훈이를 BFS를 돌려 움직여주면 불이 있는곳을 제외하고 대피할 수 있다. 처음에는 queue 4개를 사용하여..
https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. Logic 특정 지점에서 출발하는 것을 선택하지 못하고 선택하더라도 그 지점에서 최솟값이 나오리라고 장담할 수 없다. 그렇기 때문에 도착한 섬이 출발한 섬과 다른 섬인지를 구별하는 아이디어를 떠올려야 하는 문제이다. 문제에서는 섬을 1로 입력받지만 나는 처음에 -1로 받은 뒤 각 섬마다 섬 내부에서 BFS를 돌아서 각 섬에 숫자를 매겨줬다. 각 섬의 번호가 매겨지면 섬마다 BFS를 돌며 다른 섬까..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 1. Logic 문제에서 포인터를 기준으로 앞 뒤에 문자를 넣거나 삭제하기 때문에 문제를 보는 관점 자체를 아예 포인터 기준으로 나눠서 봤다. 포인터 기준으로 왼쪽에 있는 left deque 오른쪽에 있는 right deque를 선언하여 풀이했다. 2. Code #include using namespace std; int main() { ios_base::sync_with_stdio(false); ..
보글보글소다
'Algorithm' 카테고리의 글 목록 (13 Page)