개발 블로그

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 예전에 풀기도 했었고, 보자마자 DP가 떠올랐습니다. 상담으로 얻을 수 있는 최대 수익을 출력해야 하는데, 이전에 벌어들인 수익을 누적시켜야 하기 때문에 DP를 이용했습니다. 기본 로직은 상담을 하는 것과 하지 않는 것으로 나누고, 상담을 했을 때는 max(상담을 했을 때의 누적값, 그날 상담으로 얻을 수 있는 비용)이고, 상담을 하지 않은 경우에는 max..

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 이 문제는 오른쪽, 아래쪽, 대각선으로 이동하여 가져올 수 있는 사탕의 개수의 최댓값을 구하는 문제입니다. 다양한 방식으로 풀 수 있는데, 저는 Top-down 방식(재귀)보다 Bottom-Up 방식이 익숙해서 Bottom-up으로 풀었습니다. 기본 로직은 이러합니다. dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 이 문제는 최대힙(priority_queue), 최소힙(priority_queue)를 이용하여 풀 수 있습니다. 힙이 무엇인지 설명드리겠습니다. 힙의 특성에 대해 설명드리겠습니다. 최대힙은 부모 노드는 자식 노드에 들어있는 값보다 커야하고, 최소힙은 부모 노드는 자식 노드에 들어있는 값보다 작아야 합니다. 힙은 완전 이진 트리(Complete Binary Tree)이기 때문에, N..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 이 문제는 DFS, Union Find 등 다양한 알고리즘을 통해 해결할 수 있는 문제입니다. 저는 Union Find로 풀었는데, 이 자료구조를 통해 어떻게 해결했는지 설명드리겠습니다. Union Find란 ? 상호 배타적 집합(Disjoint-set)들의 부분 집합들로 나눠진 원소들에 대한 자료구조 2가지 연산으로 이루어져 있다. Find : x가 어떤 집합에 포함되어 있는지 찾는 연산(루트를 찾는..

https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 이 문제는 N명이 한 줄로 서있을 때 서로 마주칠 수 있는 쌍의 수를 구하는 문제입니다. 비교적 어려운 문제는 아니지만, 키가 같은 경우 때문에 고려사항이 많은 문제입니다. 테스트 케이스로 설명 드리겠습니다. case 1 : 7 2 4 1 2 2 5 1 다음과 같이 키가 2 4 1 2 2 5 1 일 경우에는 서로 마주할 수 있는 쌍은 (1 2), (2,3), (2,4), (..

https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net DFS + Bruteforce 문제입니다. 중복 값을 제거해주는 Set를 선언해줍니다. 그리고 길이가 6이 될 때 까지 값을 하나씩 추가해줘야하는데, 예시를 들어 값이 112에서 1을 추가한다면 112(기존 값) * 10 + 1(새로운 값)이 되어야 합니다. 그래서 함수 세 번째 파라미터에서 함수 num * 10 + a[nx][ny]를 호출해주었습니다. ..

https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net 이 문제는 A, B, C의 각각의 친구의 수의 최솟값을 구하는 문제입니다. 우선적으로 A, B가 친구 관계인지 check해주고, A, B가 친구인 경우에 C가 친구인 경우를 구한다면, 시간 복잡도를 O(N^3)에서 O(N^2 + MN)으로 최소화할 수 있게 됩니다. #include using namespace std; int a[4001][4001]; i..

https://www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 www.acmicpc.net 주어지는 입력값은 아이스크림의 종류와 조합해서 안 되는 아이스크림의 종류 개수입니다. 예시를 들어 조합해서는 안 되는 아이스크림이 1번, 3번이면 check[3][1], check[1][3]을 true로 바꿔줘야 합니다. 왜냐하면 1번, 3번이나 3번, 1번이나 같은 의미이기 때문입니다. 만약 검사를 하고 check변수가 false이면 개수를 하나씩 늘려주면 ..

https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 이 문제는 c++에 내장되어 있는 next_permutation을 사용하면 간단하게 풀 수 있는 문제입니다. A, B를 입력받고, A의 순서를 뒤바꿔서 C보다 작은 최대 수를 구하는 문제입니다. 우선적으로 A를 문자열로 입력받습니다. 그리고 next_permutation을 이용하여 순열을 하나씩 구하고 stoi함수를 통해 숫자로 파싱 시켜주고 B와 비교해서 작으면 값을 지속..

https://www.acmicpc.net/problem/16924 16924번: 십자가 찾기 십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크 www.acmicpc.net 이 문제는 해당 격자판에서 다음과 같은 십자가를 몇 개 만들 수 있는지 물어보는 문제입니다. 해당 인덱스에서 상하좌우 비교해서 *가 된다면 해당 부분과 크기를 push 해주면 되는 간단한 문제지면 예외의 경우가 존재합니다. 예외 케이스 * *** * * 다음과 같은 부분은 제일 아래쪽 *이 크기가 1인 십자가에 속하지 않기에, -1을 출력 해줘야 합니다. 이러한 경우를 방지하기 위해 ch..