singun11

tony9402라는 분이 문제집을 잘 만들어두셔서, 그대로 첨부한다. www.acmicpc.net/workbook/view/2154 문제집: 1,2,3더하기 시리즈 (tony9402) www.acmicpc.net 문제들은 전반적으로 쉽다. 실버 문제들이니까? 주 문제 상황은 어떤 수 N을 1, 2, 3의 합으로 나타내는 경우의 수를 구하는 것이다. 주로 사용한 아이디어는 DP이다. 차례대로 풀이해보자. www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 그냥 D[i] = i를 1, 2, 3을 이용해 나타낸 경우의 수(순서 고려 O) 라고, 정의한다면 D[i] ..

[이것 또한,,, 풀고 있는 중 정리하면서 올리고 있습니다..] acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net www.acmicpc.net/problem/18236 18236번: 행렬 곱셈 순서 2 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 263-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 263-1보다 작거나 같 www.acmicpc.net www.acmicpc.net/..

트리와 쿼리 문제집을 풀면서 정리를 한 글입니다. 계속 업데이트 중.. (~2020-10-28) 트리와 쿼리 문제집이다. www.acmicpc.net/workbook/view/915 문제집: 트리와 쿼리 (baekjoon) www.acmicpc.net 보는데, 다이아 루비까지는 아니어도 플레까지의 문제라도 다 풀고 싶었다. 일단 트리와 쿼리 시리즈를 풀고는 싶지만, 전혀 트리와 친한 사람이 아니라서 검색부터 시작했다.. koosaga.com/135 트리와 쿼리 연습 [2016.11.02 초판] [2017.10.05 트리와 쿼리 7/11 추가] https://www.acmicpc.net/contest/scoreboard/195 시간이 남을때마다 하긴 했는데... 너무 힘든 연습이었다 ㅠㅠ 아주 간략하게 풀..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 간단한 DFS 문제, 배열 갱신 타이밍만 잘 잡으면 됨. https://www.acmicpc.net/problem/1806 1806번: 부분..

오늘은 무슨 알고리즘 문제들을 풀자! 라는 생각없이 그냥 백준 문제 목록들을 훑어보고 있었다. 근데, 이 문제가 눈에 띄었다. https://www.acmicpc.net/problem/17528 17528번: Two Machines 문제 스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 ti를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나를 선택할 수 있다. 작업 ti를 완료하기 위해 머신 A를 선택하면 ai시간이 걸리고 머신 B를 선택하면 bi 시간이 걸린다. 각 머신은 어느 순간에 최대 하나의 작업만 수행할 수 있으며, 한 작업이 시작되면 그 작 www.acmicpc..

ngd라는 닉을 사용하는 고등학교 후배가 있다. 분명히 몇 년전에는 코딩을 가르쳐줬던 후배인데, 기하에 미쳐가고 있는 것 같다. 계속 질문을 하는데, 난 기하 알고리즘을 공부한 적이 없어서, 공부를 시작하게 되었다.. ngd에게 감사의 말을 전한다..^^ 갑자기 기하를 시작하게 해줘서^^ 아무튼, Convex Hull이 대충 무슨 알고리즘인지는 알고있는 상황이었다. 그래서 바로, Convex Hull을 구현해보려고 했는데, 너무 비효율적인 코드가 잔뜩 쏟아졌고, 결국 구글링을 해가면서 여러 사람들의 Convex Hull 구현 코드들을 분석했다. 그 중에서, 이 분의 블로그 글이 제일 나은 것 같았다. https://www.crocus.co.kr/1288 컨벡스 헐 알고리즘(Convex Hull Algor..

아직 이해가 안된다...ㅠㅠㅠ 일단 관련 문제들 위키 링크부터 모아봤다.. 계속 수정해가면서 이해한 내용을 정리해보도록 하겠습니다. 위키 https://en.wikipedia.org/wiki/Zero-sum_problem Zero-sum problem - Wikipedia In number theory, zero-sum problems are certain kinds of combinatorial problems about the structure of a finite abelian group. Concretely, given a finite abelian group G and a positive integer n, one asks for the smallest value of k such that ev..

일단, 어떤 식이든 지금 잘하는 사람들의 발자취를 따라가보자라는 생각으로 공부하고 싶은, 공부해야 하는 내용들을 하나하나 적어놓으려 한다. 적어놓은 것은 다음과 같다. 1. 이론은 아는데 구현은 어떻게 하지..?라고 생각했던것 2. 이게 뭔데? 3. solve.ac 태그 분류에 있는데 자신이 없는 분야 언젠가는 할 수 있겠지. 하나 하나 공부해가면서, 이 카테고리에 공부한 내용을 남겨볼거다. 트리의 지름 이론만 접함. 구현 1도 안 해봄. 백준에 트리의 지름 문제부터 풀어보려함. LCA(Lowest Common Ancestor) 대충 이게 뭘하는지만 아는 상태 Convex Hull Trick 잘 모르겠음. 비트 필드를 활용한 동적 계획법 대충 뭔 의도인지는 아는데, 관련 문제를 풀어봐야 알듯. MST(효..

인턴으로 다닌 회사도 기간이 끝나 퇴사하고, 대학교 개강도 2주 연기되면서 학교 기숙사에서 딩굴거리고 있습니다 그러던 중에, 하루에 알고리즘 1개씩 다시 익히면 꽤 남는게 있지 않을까 싶어서 solved.ac에서 분류되어있는 알고리즘 중 오늘은 다익스트라 알고리즘을 살짝쿵 건드려봤습니다. 푼 문제들은 아래와 같습니다. 다익스트라 알고리즘을 딱 사용하고 적당히 활용하는 문제들이어서 비교적 쉽게? 푼 것 같습니다. 계속 조건만 바꿔가면서 코드를 제출했으니 말이죠. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한..