티스토리

MG

검색하기

블로그 홈

MG

moogeun.tistory.com/m

안녕하세요. 열심히 살아보아요♬

구독자: 0

방명록 방문하기

주요 글 목록

[백준 / C++] 1932 - 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 한 숫자를 정했을 때 그 위의 두 경로 중 가장 최대값을 정하는 문제이다. 양 끝에 위치하는 숫자일 경우 바로 위 하나의 경로만 더하고 나머지 경우는 dp로 저장한 두 최대 경로 중 더 큰 값을 저장한다. #include #include #define MAX 501 using namespace std; vector v[MAX]; int dp[MAX][MAX]; int n, tmp, ans; int main() { ios::sync_with_stdio(0); cin.ti.. 공감수 0 댓글수 0 2022. 6. 1.
[백준 / C++] 1238 - 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 파티하는 집 x가 주어졌을때 각 집에서 x로 갔다오는 최단거리를 모두 구하고 그 중 최대값을 묻는 문제이다. 한 정점으로부터 모든 정점으로의 최단거리를 구하는 다익스트라를 이용하면 된다. 하지만 주의할 점으로 여기서는 i에서 x로 가고 x에서 i로 가는 두 방향에 대해서 최단거리를 구해야 한다는 것이다. 여기서 문제를 조금 바꿔 해석하면 쉽게 되는데 우선, x에서 모.. 공감수 0 댓글수 0 2022. 6. 1.
[백준 / C++] 1149 - RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 서로 이웃한 집과 같은 색이 아니면 된다. 그래서 n개의 집을 3가지 색으로 칠하는 dp[n][3]를 정의한다. 이를 0부터 n - 1까지 그리고 RGB 순으로 반복을 돌린다. k번째 집을 RGB 3종류로 칠한다고 각각 가정하고 이와 다른 색들로 칠해진 k - 1번째 집들 중 최소를 찾아 그 집을 칠할 때 드는 비용과 더해준다. 그리고 마지막에 최소값을 찾아 출력한다. #in.. 공감수 0 댓글수 0 2022. 5. 29.
[백준 / C++] 5557 - 1학년 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 다음 수를 더하고 빼는 경우의 수를 계속 세나가야 하는 DP 문제이다. dp[i][j]는 i번째 수까지 계산에 넣었을 때 그 합이 j가 되는 경우의 수이다. n번째 수를 계산에 넣기 전에 dp[n-1]를 0부터 20까지 돌려 n번째 수를 더하거나 뺐을 떄 0 이상 20 이하이면 경우의 수를 더해주면 된다. #include #define MAX 101 using namespace std; l.. 공감수 0 댓글수 0 2022. 5. 17.
[백준] 1043 - 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 이 문제의 요점은 같은 파티에 한 번이라도 속한 사람은 전부 통한다는 것이다. 예를 들어 1번이 진실을 알고 있고 2번이 한번이라도 1번과 같은 파티에 참석했으면 순서에 상관없이 다른 파티에서는 2번은 진실을 아는 사람처럼 행동하게 된다. 그렇기에 이 문제는 한 번이라도 같은 파티에 참석해봤냐 안 해봤냐 나누는 문제로 Union-Find 알고리즘을 사용하면 된다. 더 자세히 말하자면 각 파티당 참여하는 인원.. 공감수 0 댓글수 0 2022. 5. 16.
[백준] 2293 - 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 배낭문제와 유사한 풀이방식이다. dp[k]는 k원이 되는 동전의 구성 경우의 수이다. 이를 중복없이 계산하기 위해서 1번째 동전을 1~k원까지 채워넣고 그리고 2번째, 3번째 ... n번째 동전까지 경우의 수를 고려한다. 그렇게 되면 j번째 동전에서 그 전 동전이 이미 반영이 다 되고 더 이상 반영이 안되기에 중복이 안되게 된다. 그래서 dp[j]에 dp[j - arr[i]] 를 계속 더해주고 dp.. 공감수 0 댓글수 0 2022. 5. 10.
[백준] 2156 - 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 전형적인 dp문제이다. dp[i]는 i번째 포도주에 도달했을때 가장 많이 마신 양이다. 그렇다면 두 가지 방법으로 나뉠 수 있다. 첫번째로 i번째를 마셨을때이다. 이를 마셨다면 또 두가지로 나뉜다. 이전 포도주를 마셨냐 안 마셨냐이다. 마셨다면 3번 연속으로 못 마시기에 dp[i - 3]과 이전 포도주, 현재 포도주를 다 더해준다. 이전 포도주를 안 마셨다면 dp[i - 2]와 현재 포도주를 더해준.. 공감수 0 댓글수 0 2022. 5. 6.
[백준] 2407 - 조합 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 얼핏 보면 간단한 조합 구현 문제이지만 범위를 봐야합니다. 최대값인 100_C_50 는 long long int 의 범위를 거뜬히 넘어버려 계산식으로만 하면 틀립니다. 그렇기에 string으로 구현해 줍니다. 기본적으로 dp를 베이스로 nCm = n-1Cm-1 + n-1Cm 을 이용하여 재귀를 돌려줍니다. n = m or m = 0 일 때 1을 반환하고 이 전의 값이 있으면 그대로 반환해줍니다. 그리고 이 두 값을 더할 때 string의 첫째자리만 더해서 문자열로 추가하는 방식으로 정답을 string으로 반환합니.. 공감수 0 댓글수 0 2022. 5. 5.
[백준] 2294 - 동전 2 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 동전 k일때 동전의 최소 개수를 구하는 문제입니다. 저는 0원부터 k원까지 dp를 완성해서 푸는 방식으로 해결하였습니다. dp를 모두 INF로 초기화시키고 1원부터 k원까지 dp를 돌려줍니다. dp[i]를 초기화할때 동전 벡터를 전부 돌려가면서 dp[i]랑 dp[i - 동전] 을 비교해 더 작은 값을 저장합니다. 이때 i - 동전이 0 이상일때와 dp가 INF가 아닐.. 공감수 0 댓글수 0 2022. 5. 4.
[백준] 1629 - 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 얼핏 보면 간단해 보이지만 a, b, c의 범위와 시간 제한 때문에 조금 고민이 필요한 문제입니다. 그냥 a^b 를 c로 나누게 되면 b번 반복이 있기 때문에 시간초과가 나게 됩니다. 그렇기에 분할 정복으로 O(b) 를 O(logb) 로 만들어 줍니다. 지수법칙을 적용해 보면 a^b = a^(b/2) * a^(b/2) 로 표현되기 때문에 이를 이용해 재귀를 돌려서 풀어줍니다. 그리고 계산을 하기 전에 a를 미리 c로 나눈값을 대입해 long long 범위 초과가.. 공감수 0 댓글수 0 2022. 5. 4.
[백준] 1890 - 점프 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 간단한 DP 문제입니다. 배열에 각 칸의 숫자를 입력받고 dp를 long long으로 선언해줍니다. 그리고 각 칸마다 오른쪽, 아래로 점프했을때 게임 판을 넘어가지 않는다면 그 칸의 dp 만큼 점프한 칸에 더해줍니다. 마지막 칸에 도착하면 루프를 탈출해주고 출력합니다. #include #define MAX 101 using namespace std; typedef long long ll.. 공감수 0 댓글수 0 2022. 5. 2.
[백준] 2141 - 우체국 https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 처음에 고민을 많이 하다 수학으로 풀었었습니다. 우체국의 위치를 x 로 잡고 각 마을과의 거리와 인구를 곱하면 여러 절댓값으로 이루어진 그래프가 그려지고 그 그래프의 극소점이 답이 되었습니다. 하지만 알고리즘 분류에 그리디가 있는 것을 보고 다른 풀이를 참고하다 더 간단한 방법이 있다는 것을 알게 되었습니다. 아래 .. 공감수 0 댓글수 0 2022. 5. 1.
[백준] 2212 - 센서 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 센서 정보를 입력받고 이를 오름차순으로 정렬해 줍니다. 그러면 일직선상에 센서가 나열되고 이를 집중국의 개수 K 개의 집합으로 만드는데 이 길이의 최소값을 구하는 것이 목적입니다. 이를 계산하기 위해 인접한 센서끼리의 길이를 구해 주고 이를 오름차순으로 나열해줍니다. 그리고 이를 1번째부터 n - k 번째까지 더하면 답이 됩니다. 그 이유를 아래 그림으로 설명하자면 인접한.. 공감수 0 댓글수 0 2022. 4. 30.
[백준] 11727 - 2 x n 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2 x n 타일링 1 에 이은 시리즈 2입니다. 전 내용과 거의 비슷한데 2 x 2 타일 하나만 생겼습니다. 이에서 볼 수 있듯이 시리즈 1처럼 DP 를 활용하는 문제입니다. 아래 그림처럼 설계가 되고 프로그래밍하면 풀립니다. #include #define MAX 1001 using namespace std; int dp[MAX]; int n; int main() { ios::sync_with_stdio(0); cin.tie(.. 공감수 0 댓글수 0 2022. 4. 30.
[백준] 11653 - 소인수분해 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net n을 입력받고 이를 sqrt(n) 까지 소수로 나눠줍니다. 나눠줄 수 num을 2부터 시작해 나눠지지 않거나 소수가 아니면 1씩 더해줍니다. 그리고 소수판정 시에도 sqrt(num) 까지 해주고 소수로 판정되면 visit 배열로 체크해 다음부턴 판정하지 않도록 합니다. 마지막에 n이 1이면 다 나누어 떨어진 것이고 1이 아니면 마지막 소수가 되니 출력해 줍니다. #include #define MAX 3200 using namespace std; bool visit[MAX] = { false }; bool isPrim.. 공감수 0 댓글수 0 2022. 4. 28.
[백준] 1092 - 배 https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 전형적인 그리디 문제입니다. 크레인과 화물을 모두 벡터에 넣고 이를 내림차순으로 정렬합니다. 그리고 크레인을 앞에서부터 가져갈 수 있는 최대한 무거운 화물을 차례대로 가져가게 합니다. 한 번 사이클 돌 때마다 ans을 1씩 더하면 풀립니다. 그리고 예외로 제일 무거운 짐을 무게 제한이 제일 큰 크레인이 못 가져갈 경우 -1을 출력해줍니다. #include #include #incl.. 공감수 0 댓글수 0 2022. 4. 28.
[백준] 17626 - Four Squares https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 보자마자 dp 문제라 생각하였습니다. 자연수가 어떤 제곱수와 몇 번 더해서 만들어지게 되는데 그 자연수에 제곱수를 뺄 때마다 또 하나의 자연수가 나오기 때문입니다. 예를 들어 dp[26]은 dp[26 - 1^2] + 1, dp[26 - 2^2] + 1, ... dp[26 - 5^2] + 1 중 최소값입니다. 그래서 DP 함수를 선언해 재귀로 돌렸습니다. #inc.. 공감수 0 댓글수 0 2022. 4. 27.
[백준] 16953 - A → B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net A를 2배 혹은 오른쪽 끝에 1을 추가해 B를 찾는 간단한 문제입니다. 저는 queue에 계산중인 수와 계산 횟수를 저장해 bfs로 진행하였습니다. 이러면 빠지는 경우의 수 없이 2^n 만큼 전부 다 훑어볼 수 있습니다. #include #include using namespace std; typedef long long ll; queue q; ll a, b; void bfs() { q.push({a, 1}); while (!q.empty()) { ll x = q.front().first; int y = q.front().. 공감수 0 댓글수 0 2022. 4. 26.
[백준] 11726 - 2 x n 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 처음에 머리로만 풀려다 확률론까지 생각했다 난이도 보고 DP 문제일거라 직감했습니다. 그리고 아래와 같이 그리면서 규칙을 찾았고 해결했습니다. DP 문제는 직접 세거나 그림으로 도식화하기 전에는 DP 인지 판별이 어려워 많은 연습이 필요할 것 같습니다. #include #define MAX 1001 using namespace std; int dp[MAX]; int n; int main() { ios::sync_wit.. 공감수 0 댓글수 0 2022. 4. 25.
[백준] 20365 - 블로그2 https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 한 번에 B 또는 R 을 쭉 칠하고 나머지 색을 중간중간 칠하면 최소가 됩니다. 하지만 그 최소를 B, R 둘 다 해보아야 알기 때문에 연속되지 않은 B, R 수를 세고 둘 중 최소를 구해주면 됩니다. #include using namespace std; int n, b, r; string s; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >>.. 공감수 0 댓글수 0 2022. 4. 25.
알고리즘 PS C언어나 python 기초를 공부하고 코딩실력 상승을 위해 그리고 컴퓨터과학 기초를 다지기 위해 알고리즘을 공부합니다. 백준, SW 알고리즘 문제 등 알고리즘의 문제들을 풀고 해결법을 작성하려 합니다. 다양한 주제의 알고리즘 문제를 풀고 제가 따로 공부한 내용도 같이 첨부할 예정입니다. 문제는 이미 solved.ac의 class를 한 단계씩 풀거나 백준 문제를 분야별로 중요한 문제만 뽑아놓은 아래의 사이트에서 참고하여 난이도에 맞게 풀 예정입니다. https://github.com/tony9402/baekjoon 질문이나 다른 해결법이 있으면 댓글 달아주시면 감사하겠습니다. 제 백준 프로필입니다. https://www.acmicpc.net/user/pyu1405 공감수 0 댓글수 0 2022. 4. 24.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.