본문 바로가기

반응형

전체

[BOJ 12920] 평범한 배낭 2 [문제] : https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 � www.acmicpc.net [필요 개념] - DP , 배낭 문제 (Knap-sack) - 비트마스크 [풀이] 전형적인 배낭문제 (Knapsack)처럼 보이나, 이 문제에서는 특별하게 고려해줘야 하는 부분이 있다. 바로 같은 종류의 물건의 개수가 2개 이상일 수 있다는 것이다. 원래 배낭문제에서는 각 물건이 하나씩 있어, 해당 물건을 넣거나 빼는 두가지 경우만 있었는데..
2020.05.15 ~ 2020.06.14 공부 일지 [푼 문제] 1. BOJ : 78문제 (현재까지 411문제 solved) 2. Codeforces 5회 참여 (Rating 1434 -> 1517) - Round #644 (Div. 3) / Round #645 (Div. 2) / Round #646 (Div. 2) / Educational Round 89 / Round #649 (Div. 2) [공부한 개념] 1. Dynamic Programming) 2. Network Flow (최대 유량, 최소 컷) 3. 이분 탐색 4. Offline Query (오프라인 쿼리) 5. 기하 (Convex Hull, CCW) 공부한 지 얼마나 되었다고, 벌써 슬럼프가 오기 시작했다..... 사실 슬럼프라기 보단 뭔가 시작할 때의 의욕보다 떨어진 기분이다. 첫 달에는 ..
멋쟁이사자처럼 7기 후기 멋쟁이 사자처럼 at 서강대학교 7기 활동을 잘 마치고 수료하였다. 수료한 지 오래되었지만, 뒤늦게나마 후기를 써보려고 한다. (화질이 나쁜 사진은 모자이크 한 사진입니다.)멋쟁이 사자처럼 이라는 동아리를 처음 들어본 건 2학년 때였다. 학교 선배님들이 진행한 컴퓨터공학 복수전공 또는 비전공자 대상자를 위한 설명회(?)에서 얼핏 들었다. 당시에는 이러한 좋은 동아리가 있다는 식으로 잠깐 언급해서 기억에 크게 남지는 않았는데, 나중에 찾아보니 그때 말한 동아리가 바로 멋쟁이 사자처럼 이었다. 그동안 학회나 학생회 등은 했어도 동아리는 한 번도 가입해본 적이 없어서 4학년이 되어서야 처음 동아리에 지원하게 되었는데, 컴공 복수전공을 3학년까지 하면서도 내 진로의 방향성을 전혀 정하지 못해서 다양한 경험도 하..
소수 판별법 - 에라토스테네스의 체, 밀러-라빈(Miller-Rabin) 소수판별법 어떠한 자연수 N이 소수인지를 판별하는 방법은 여러 가지 방법이 있다. 그중에서 너무 난도 높은 것은 제외하고 충분히 PS에서 쓸만한 방법을 알아보자. 우선, N이 소수인지를 판별하는 경우와 N이하의 소수가 몇개있는지, N이하의 소수를 모두 구하는 경우 두가지로 보통 나뉜다. 1. N을 2부터 N-1까지 모두 나누기 소수는 1또는 자기 자신으로만 나누어지기 때문에 위의 방법으로 N이 나누어 떨어지지 않는다면 N은 소수라고 할 수 있다. 만약, N이 어떤 두 수로 나누어진다고 한다면, N = p*q의 형태가 되고, p와 q 둘 중 하나는 반드시 $ \sqrt{N} $의 값 이하일 것이다. 따라서 N-1까지 나눌 필요는 없고, $ \sqrt{N} $까지만 나눠도 소수인지 판별이 가능하다. 물론, 이 방법을 ..
2020.04.15 ~ 2020.05.14 공부 일지 [푼 문제] 1. BOJ (백준) : 87문제 2. Codeforces 4회 참여 - Round #638 (Div. 2) , Round #640 (Div. 4) , Round #641 (Div. 2) , Round #642 (Div. 3) [공부한 개념] 1. STL (stack, vector, sort, lower_bound) 2. LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) 3. Segment Tree & Segment Tree with Lazy Propagation (세그먼트 트리) 4. Miller-Rabin Primality Test (소수 판별법) 5. Fast exponentiation (빠른 거듭제곱) 6. Knap-sack (배낭 문제) 알고리..
2019 Sogang Programming Contest (Champion) 풀이 작년에 시행된 서강대 프로그래밍 대회 (Champion 부문) 문제 풀이다. 휴학 상태라 대회를 나가지 못해서 많이 아쉬웠는데, 지금이나마 문제를 한번 풀어보게 되었다. A. solved.ac (BOJ 18110번) 문제 : https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net n개의 정수를 받아서 그중 상위 15%, 하위 15%를 제외한 나머지 값들의 평균을 구하는 문제이다. n이 30만 이하이기 때문에 sort함수를 ..
Codeforces Round #640 (Div. 4) 풀이 및 후기 https://codeforces.com/contest/1352 Dashboard - Codeforces Round #640 (Div. 4) - Codeforces codeforces.com [후기] Programming contest 후기로는 첫 게시물이다. contest라고 하기엔 너무 자주 있긴 하지만, 그래도 시간 재고 스코어보드도 볼 수 있는 기회이니 앞으로도 꾸준히 많이 참여하는 것이 목표이다. codeforces contest를 많이 참여해보진 않았지만, 난이도는 Div.2와 비교했을 때 매우 쉬운 편이었다고 생각한다. (최상위권은 7문제를 20~30분만에 다 풀었더라.... 정말 대단..) 문제 풀면서 받은 느낌은, 뭔가 알고리즘을 이용하는 느낌은 많이 들지는 않았고, 특히 예시로 보여준 ..
알고리즘 공부를 체계화 하자,,, 처음 쓰는 일기(?)인데, 일기보단 사실 반성문에 가까운 느낌이다. 종종 보면서 마음을 다잡을 수 있는 글이 되길... 그동안 특정 알고리즘을 공부하고, 해당 알고리즘 유형의 문제를 푸는 방식으로 공부를 해오다가, 만약 실제 테스트나 대회에서 이 문제를 보면 알고리즘을 떠올릴 수 있을까? 하는 생각이 문득 들었다. 물론 지금은 어떤 알고리즘이 있는지 공부하는 단계니까 이 공부방법이 맞을 수도 있겠지만, 위의 생각을 좀 해결하고자 무작정 해오던 알고리즘 공부를 좀 더 체계화해야겠다는 필요성을 느꼈다. 실제로 문제 유형을 안 보고 풀면 훨씬 더 못 풀게 되더라,,, 우선 첫번째로는, 주 1회는 반드시 하나의 problem set을 문제 유형을 보지 않고 풀어보는 것이다. codeforce나 다른 open c..