티스토리

COMFORT

검색하기

블로그 홈

COMFORT

comfort-molkang.tistory.com/m

_MOLKANG 님의 블로그입니다.

구독자: 2

방명록 방문하기

주요 글 목록

코포 일기 : Codeforces Round 909 (Div. 3) https://codeforces.com/contest/1899 Dashboard - Codeforces Round 909 (Div. 3) - Codeforces codeforces.com 블로그에 글을 쓰는 것도 코포를 하는 것도 정말 오랜만에 한다. 재활훈련(?)을 하는 느낌으로 딥3에 참여했고, 나쁘지 않은 성적이 나왔다. 문제들은 전체적으로 지문이 길지만 풀이는 심플한 문제들로 이루어져 있었던 것 같다. A. Game with Integers 주어진 n에서 Vanya와 Vova가 번갈아 가면서 1을 더하거나 빼고, Vanya의 턴이 끝났을 때 3의 배수를 만들면 Vanya의 승리고, 10턴 안에 3의 배수를 만들 수 없다면 Vova의 승리라는 룰이다. $n \mod 3 = 0$인 경우 Vova가 .. 공감수 0 댓글수 0 2023. 11. 19.
[백준 1376] 민식우선탐색 : 세그먼트 트리의 활용 https://www.acmicpc.net/problem/1376 1376번: 민식우선탐색 첫째 줄에는 정점의 개수 N( 공감수 0 댓글수 0 2022. 5. 12.
[백준 17424] 2xN 타일링과 쿼리 : 세그먼트 트리의 활용 https://www.acmicpc.net/problem/17424 17424번: 2xN 타일링과 쿼리 첫째줄에 N과 쿼리의 수를 나타내는 정수 Q가 공백으로 구분하여 주어진다. (1 ≤ N ≤ 105, 1 ≤ Q ≤ 2 x 105) 둘째줄부터 Q줄에 걸쳐 2가지 종류의 쿼리가 주어진다. 각 쿼리는 t x y꼴로 주 www.acmicpc.net 처음으로 푼 solved.ac 다이아 문제기 때문에 풀이를 써 보려고 한다. 개요 먼저 문제를 이해해야 하는데, 평범한 2xN 타일링과는 다르게 해당 위치에 있는 칸을 없애거나 다시 만드는 쿼리가 계속해서 주어지고, 쿼리마다 타일링 경우의 수를 출력해야 한다. 계속해서 쿼리를 받으며 업데이트 해주는 형태이기 때문에 세그먼트 트리가 생각난다. 하지만 세그먼트.. 공감수 1 댓글수 0 2022. 4. 18.
코포 일기 : Codeforces Round #733 (Div. 2) 대회 결과 4솔로 저번 Codeforces Round #726 보다 레이팅이 더 많이 올라갔다. 전체적인 느낌은 풀이는 생각이 나는데 구현이 꽤 까다로웠다. E번도 case work를 해야 하는 느낌이 들기도 하고, 전체적으로 구현을 연습하기에 좋은 문제들이었다. 결과는 꽤 만족스러웠던 것 같다. A : Binary Decimal 각 자릿수중에 최댓값을 그대로 출력하면 된다. 자릿수별로 끊어서 생각하면 매우 쉽게 알 수 있다, B : Putting Plates (1,1)에서 시작해서 간격을 띄워 가며 접시를 설치하는 것을 생각하면 된다. 풀이는 매우 쉬우나 구현이 약간 더러웠다. C : Pursuit 내 점수 배열을 A, Ilya의 점수 배열을 B라고 할 때, A에는 100, B에는 0을 A의 점수 합 .. 공감수 0 댓글수 0 2021. 7. 18.
코포 일기 : Codeforces Round #726 (Div.2) 대회 결과 실시간에서는 5솔에 성공. 그러나 채점도중 채점 데이터에 의해 E1번이 터졌다. 확인해보니 등식 하나를 잘못 쓰는 어이 없는 실수였다. 이 코드로 대회 도중의 데이터를 통과한 게 신기했다. 어찌됐든 간에 지난번보다 훨씬 나은 결과였고, 나름대로 만족스럽다. A : Arithmetic Array 배열의 평균이 1이라는 것은 다르게 말하면 모든 원소의 합 = 원소의 갯수 라는 것이다. 그리고 0을 추가하면 원소의 갯수가 1 추가되므로 평균이 1보다 클때는 원소의 합 - 원소의 갯수만큼의 0을 추가해줘야 평균이 1이 된다. 평균이 1보다 작을 때는 항상 원소의 합 + x = 원소의 갯수 + 1 을 만족시키는 음이 아닌 정수 x가 항상 존재하므로 1개의 원소를 추가하며, 정확히 1일때는 추가할 필요가.. 공감수 0 댓글수 0 2021. 7. 18.
코포 일기 : Codeforces Round #722 (Div. 2) https://codeforces.com/ Codeforces codeforces.com 대회 결과 1솔밖에 못하고 90점이 떨어졌다. B번은 다 풀어놓고 사소한 반례를 못 찾았으며, C번은 그리디 + dfs로 삽질하다 그리디가 안된다는 걸 깨닫고 뒤늦게 tree dp를 구현하다가 시간이 끝났다. 대회가 어려웠던 건지 그냥 내가 못한건지 생각해보면 후자쪽에 가까운 것 같다. 여러모로 분발할 필요가 느껴졌다. A. Eshag Loves Big Arrays 최솟값과 그 다음으로 작은 값을 선택하고 연산하면 최솟값만 남고 다 지워진다. 그냥 최솟값의 갯수를 출력하는 문제 B. Sifid and Strange Subsequences 두 양수의 차의 절댓값은 항상 최댓값보다 작기 때문에 이상한 수열에 양수가 2개.. 공감수 0 댓글수 0 2021. 5. 25.
코포 일기 : Codeforces Round #721 (Div. 2) http://codeforces.com/contest/1527 Dashboard - Codeforces Round #721 (Div. 2) - Codeforces codeforces.com 최근들어 시간 제한이 있는 대회 환경과 시간 제한 없이 그냥 푸는 환경의 갭을 절실히 느끼게 되는 일이 있었다. 무엇보다도 대회 경험이 너무 부족하다고 느껴서 앞으로 최근 안 하던 코드포스를 꾸준히 하려고 마음먹었다. 또한 코포가 끝날 때마다 일기처럼 간략하게 경험을 기록해두면 좋을 것 같아서 글을 쓴다. 대회 결과 A와 B1을 빠르게 풀어 놓고 C에서 한참을 고민하다 결국 풀지 못하고 2솔로 마무리지었다. 오랜만에 해서 그런지 영 실망스러운 결과였다. A : And Then There Were K N이 주어졌을 때,.. 공감수 0 댓글수 0 2021. 5. 21.
알고리즘 동아리 활동#2 이분 탐색 연습문제 풀이 이분 탐색은 최대/최소 문제를 결정 문제 * logN으로 바꾸는 강력한 방법이다. 최적해가 존재하는 범위를 두고 매번 질문을 던지며 범위를 1/2씩 좁혀 나간다. 어떤 함수의 조건을 만족하는 값을 구하려고 할 때 이분 탐색을 적용하려면 이 함수는 단조 함수의 형태여야 한다. 백준 1654 : 랜선 자르기 www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net K개의 랜선의 길이가 각각 주어질 때, 각 랜선을 잘라 N개 이상의 랜선을 얻으.. 공감수 0 댓글수 0 2020. 11. 27.
알고리즘 동아리 활동#1 그리디 알고리즘 연습문제 풀이 그리디 알고리즘은 주어진 답을 구하기 위해 당장 답에 가까운 방향으로만 이동하는, 말 그대로 눈 앞의 이득만을 쫒는 문제 해결 방법이다. 상당히 무식한 방법 중 하나이며 이 방법으로 최적해가 나온다는 사실, 즉 정당성을 증명하는 것이 핵심이다. 백준 11047 : 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 그리디 알고리즘을 사용하는 대표적인 문제 중 하나이다. N개의.. 공감수 0 댓글수 0 2020. 11. 27.
constructive algorithms에 대하여 #1 https://codeforces.com/contest/1375 Dashboard - Codeforces Global Round 9 - Codeforces codeforces.com 지난번 코드포스 글로벌 라운드 9에서 꽤나 큰 충격을 받았다. 모든 문제가 사고력 위주의 풀이를 요구하며, 예제 입출력으로 말장난을 하는 등 나에겐 익숙하지 않았던 문제들로만 구성되어 있는 것이다. 결국 삽질 끝에 A번과 B번밖에 풀지 못 했으며, C번의 풀이를 보고 현자타임이 왔다. 나중에 알아보니 이러한 문제 유형을 constructive algorithms 라는 태그를 붙여 따로 분류를 하고 있었으며, 이런 문제가 나오면 삽질하지 않기 위해서라도 이런 유형에 대해 알아둬야 할 필요를 느꼈다. 먼저 constructive.. 공감수 0 댓글수 0 2020. 7. 11.
[백준 2618] 경찰차 : 동적 계획법 연습하기 백준 2618번 : 경찰차 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 �� www.acmicpc.net 문제를 잘 읽어보면 모든 사건들을 각 사건마다 1번, 2번 경찰차중에 어느 경찰차가 해당 사건을 처리해야 최적해가 나올 지 구하는 DP문제임을 알 수 있다. 일단 가장 직관적인 해답은 두 경찰차의 좌표를 매개변수로 받는 부분 문제를 만드는 것이다. DP[ind][x1][y1][x2][y2] : 지금 해결해야 하는 사건이 ind이고 경찰차1의 위치가 (x.. 공감수 0 댓글수 0 2020. 5. 25.
[백준 17613] 점프 : 수의 규칙성을 이용한 최적화 백준 17613번 : 점프 https://www.acmicpc.net/problem/17613 17613번: 점프 T개의 줄에 각각 하나의 정수를 출력한다. 각 줄에 출력되는 정수는 구간 [x, y]안의 수들의 점프넘버들 중 최댓값이다. 각 정수는 입력으로 주어지는 구간의 순서에 맞게 출력되어야 한다. 즉, 첫 번째 줄에 출력되는 정답은 첫 번째로 주어지는 구간에 대응되어야 한다. www.acmicpc.net solved.ac 플래티넘 2 등급을 받은 문제다. 어려워봐야 골드1 수준 정도의 문제만 풀던 내게 이 문제는 꽤 무모한 도전이었지만, 결국 스스로 풀어내서 굉장히 기분 좋았던 문제다. 일단 어떻게 풀지 생각해보자. 가장 단순무식한 방법은 주어진 범위 내의 점프 넘버를 일일히 구해서 최댓값을 찾는 .. 공감수 0 댓글수 0 2020. 4. 28.
[백준 1398] 동전 문제 : 수의 규칙성을 이용한 최적화 백준 1398번 : 동전 문제 1398번: 동전 문제 김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 식으로 나타내면 0보다 크거나 같은 모든 K에 대해서 10^K인 동전과 25*100^K인 동전이 있다. 이기훈은 이 나라에서 새로운 차를 한 대 사려고 한다. 이기훈은 차를 살 때, 가능하면 동전의 개수를 최소로 하려고 한다. 이기훈이 필요한 동전 개수의 최솟값을 www.acmicpc.net 이 문제는 처음 시도할 때 정말 막막했다. 일단 탐욕법으로 생각해보는 것은 바람직하지 않다. 일단 쉽게 생각해볼 수 있는 반례로 30이 있는데, 탐욕법으로 비싼 동전부터 쓰.. 공감수 1 댓글수 0 2020. 4. 27.

문의안내

티스토리
로그인
고객센터

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