전체 글 (90) 썸네일형 리스트형 USACO 2023 December Contest - Bronze 풀이 & 후기 유사코문제셋으로 공부를 해본다해본다 하다가 드디어 처음으로 문제를 풀어보았다. 처음이니 가볍게 브론즈부터 시작해야지 라고 생각했는데 내 실력을 너무 과대 평가한것같다. 생각보다 엄청 어려웠다. 체감상 난이도는 Farmer John Actually Farms 못풀겠어서 중간에 에디토리얼을 봤다. A : Candy Cane Feast 구현자체는 쉽지만 시간복잡도때문에 쉽게 손이 가지않는 문제다. 하지만 나이브하게 처리해도 시간안에 돌아간다는 사실을 증명한다면 구현은 어렵지않다. 나이브한 방법에서는 O(N * M) 시간이 소요될 수 있으며, 이는 최대 4 * 10^10의 연산량으로 시간 초과가 발생할 수 있다. 따라서 이를 해결하기 위한 시간 최적화 방법을 고려해야 한다. 1. 각 소의 앞에 있는 소들이 자신.. 2024-09-07 ABC(AtCoder Beginner Contest 370) 후기 본격적으로 PS공부를 하기로 하고, 첫 CP여서인지 어려웠다.대회 당시에 A, B, C 문제는 쉽게 풀었다. A는 솔브닥 기준으로 브론즈 5 수준의 쉬운 문제였고, B도 브론즈 1 정도의 난이도였다. C는 문제를 처음엔 잘 이해하지 못했지만, 나이브하게 풀어도 풀렸다. 체감 난이도로는 실버 중위권 정도인 것 같다.> A 소스더보기#include int main(){ int a, b; scanf("%d %d", &a, &b); if(a == 1 && b == 0) printf("Yes"); else if(a == 0 && b == 1) printf("No"); else printf("Invalid"); return 0;}> B 소스더보기#include #include usi.. 백준 25682 : 체스판 다시 칠하기 2 문제 설명주어진 M×N 크기의 보드에서 K×K 크기의 체스판을 만들려고 한다. 체스판의 색상은 두 가지 패턴 중 하나를 따라야 하며, 검은색과 흰색이 번갈아야 한다. 주어진 보드에서 K×K 체스판을 잘라낸 후, 최소한으로 다시 칠해야 하는 정사각형의 수를 계산하는 문제이다, 이 문제는 백준의 "단계별 - 누적합" 단계에 속해있는 문제이다. 하지만 이런 형식의 문제를 처음 본다면 이 문제를 어떻게 누적합으로 풀어야할지 잘 모르겠는 경우가 있을 것이다. 어쨋든 이 문제는 2차원 누적합의 응용을 통해 풀 수 있다. 우선 sum[i][j] = "(1, 1) ~ (i, j)정사각형에서 Bst(반복되는 완성된 패턴을 미리 저장해둔 배열)과 map(입력된 배열)의 다른 패턴의 수"라 정의하자. 생각을 하다보면, 체스.. 백준 11066 : 파일 합치기 문제 설명각 장이 저장된 파일들을 하나의 파일로 합치는 과정에서, 두 파일을 합칠 때 발생하는 비용이 두 파일 크기의 합으로 주어진다. 이때, 모든 파일을 하나로 합치는 데 필요한 최소 비용을 계산하는 문제이다. dp[i][j]: 배열 arr의 i번째 파일부터 j번째 파일까지를 합치는 데 필요한 최소 비용이라 정의한다. 2중 for문을 이용해 모든 구간을 검사한다. 이때 구간의 시작을 "s", 끝을 "e"라 하자.m변수를 잡아 s~e 구간을 분할해 준다.(m = 분할지점) -이때 dp[s][e]는 dp[s][m] + dp[m + 1][e] + sum[e] - sum[s - 1]을 통해 갱신해준다. 구간 [s, e]를 두 부분으로 나누어 합치는 데 필요한 비용을 의미한다.이때 필요한 sum배열은 누적합 배.. 백준 11049 : 행렬 곱셈 순서 문제 설명행렬 곱셈의 연산 횟수는 곱셈 순서에 따라 달라진다. 행렬 N개의 크기가 주어졌을 때, 최적의 곱셈 순서를 찾아 최소 연산 횟수를 계산하는 문제이다. 이 문제는 2차원 동적 테이블을 이용해 풀면 되는 동적 계획법 문제이다. dp[i][j]는 행렬 i부터 j까지 곱하는데 필요한 최소 연산 횟수로 정의하자.-우선 dp[i][j]를 큰 값으로 초기화한다.-대각선 dp[i][i]는 자기 자신과의 곱셈이므로 0으로 초기화한다. 2차원 for문을 이용해 모든 경우의 범위를 탐색한다.이때 탐색범위의 시작점을 's', 끝점을 'e'라 하자.이때 k를 이용해 s~e까지를 탐색하며 s~e의 범위를 분할한다.(k = 분할지점)이때 dp[s][e]는 dp[s][k] + dp[k + 1][e] + (r[s] * c[.. 백준 1613 : 역사 문제 설명사건의 개수와 사건 간의 전후 관계가 주어진다. 이때 주어진 전후 관계를 바탕으로 다른 사건들 간의 전후 관계를 유추할 수 있는지 확인해야한다. 예측할 수 있는지 여부를 확인해 각각의 쿼리에 대해 답한다. 이 문제는 플로이드-워셜 알고리즘을 사용하는것이 편하다.(처음에 BFS로 풀어보려다 실패해 슬펐다)모든 사건 쌍에 대해 전후 관계를 효율적으로 계산할 수 있기 때문이다.그래프를 주어진 정방향으로 하나, 역방향으로 하나 총 2개를 만들어 이를 통해 사건의 전후관계를 파악할 수 있다.각각 주어진 쿼리에 대해 시작점과 끝점이정방향 그래프에서 이어져 있다면 "-1"역방향 그래프에서 이어져있다면 "1"둘다 이어져있지 않다면 "0"을 출력한다.소스 코드#include #include using name.. 백준 23330 : 거리의 합 2 문제 설명수직선에 n개의 점이 주어졌을 때, n * n개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하는 문제. 주어진 문제의 답을 구하기 위해선 모든 요소간의 차이의 2배를 출력하면 된다.예를 들어51 2 3 4 5와 같은 입력예가 있을 때, (1, 5)한번 (5, 1)한번으로 총 두번 계산되기 때문이다. 그렇다면 모든 요소간의 차이는 어떻게 구할까?먼저 주어진 배열을 정렬한다.(정렬이 안된상태로 주어진다.)오름차순 정렬이 되었다면, 현재 탐색중인 요소 전에는 현재의 요소보다 작은 수 밖에없다.예를 들어51 2 3 4 5와 같은 예시에서 5 이전에는 1, 2, 3, 4로, 5보다 작은 수 밖에 없다. 이를통해 5와 다른 수들의 차를 구할 수 있다.(5 - 4) + (5 - 3) + (.. 백준 1507 : 궁굼한 민호 문제 설명모든 도시 쌍 사이의 최소 이동 시간을 구한 표가 주어진다. 민호는 이 표를 기반으로 최소한의 도로 개수로 모든 도시를 연결하려고 한다. 이때 필요한 도로의 최소 개수와 총 시간을 구하는 프로그램을 작성해야 한다. 나는 이 문제를 그리디 + 플로이드를 이용하여 풀었다. 코드의 핵심은 플로이드-워셜 알고리즘과 그리디 방식의 도로 선택이다. 즉, 주어진 표를 {(출발점), (도착점), (가중치)}꼴로 바꾸어 모든 노드를 저장하고, 이를 가중치를 기준으로 오름차순 정렬을 한 뒤, 가장 작은 가중치를 갖는 노드부터 탐색해가며 그래프를 만들어주는 방식이다. 노드를 추가할 때마다 플로이드를 이용하여 현재까지 추가된 노드만을 이용한 그래프의 모든 도시쌍사이의 최소이동시간 표를 만들어준다. 모든노드를 돌고, .. 이전 1 2 3 4 5 6 ··· 12 다음 목록 더보기
