본문 바로가기

C 알고리즘

백준 17510 : Bigger Sokoban 40k https://www.acmicpc.net/problem/17510 17510번: Bigger Sokoban 40k Sokoban is a famous puzzle game, where the player moves around in the $N \times M$-size grid, and pushes $1 \times 1$-size boxes to $1 \times 1$-size storage locations. Bigger Sokoban is a possible variation of Sokoban, but the size of boxes and storage www.acmicpc.net 현재 이 문제의 답은 인터넷 상에 나와있지 않다. 는 사실이 아니고, 한 달 전에 심심풀이 겸 찾아봤는데, 놀랍게.. 더보기
코드업 3764 : 최장 경로의 수 codeup.kr/problem.php?id=3764 최장 경로의 수 인성이와 정훈이는 친한 친구이다. 인성이는 학교에서 자신이 수학을 잘한다고 자랑을 하고 다닌다. 정훈이는 인성이의 코를 납작하게 눌러주기 위해서 어려운 문제를 준비해 왔다. '내가 좌표 codeup.kr 푼 사람 수에 비해 쉬운 문제이다. 이 문제 제작자가 직접 한 말에 따르면 "쉽게 생각하면 코포 Div.2 기준 B, 어렵게 생각하면 C 또는 D까지 될 수 있다."라고 했다. 그래서 쉽다는 생각으로 관찰을 잘 해보면, n이 하나 늘어날 때마다 새로 생긴 공간에 한해 새로운 경로는 두 가지씩 탄생한다는 것을 알 수 있다. 어떻게 해서 두 가지가 생기는지는 각자 찾아보도록 하고, n=1일때는 답이 2인 것을 참고해 문제를 맞추도록 하자. 더보기
BOJ 6588 : 골드바흐의 추측 솔브드 기준 실1 문제. 에라토스테네스의 체를 이용하면 쉽게 풀린다. 시간초과가 날 수 있으니 벡터 v에다가 소수의 목록을 적어놓자. 더보기
BOJ 1262 : 두 번째로 작은 스패닝 트리 www.acmicpc.net/problem/1626 1626번: 두 번째로 작은 스패닝 트리 첫째 줄에 그래프의 정점의 수 V(1 ≤ V ≤ 50,000)와 간선의 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 간선으로 연결된 두 정점과 그 간선의 가중치가 주어진다. 가중치는 100, www.acmicpc.net solved.ac 기준으로 다5 문제다. 상급 알고리즘을 요구하므로 어려운 문제였다. 풀이는 다음과 같다. MST를 구한다. MST를 이루지 않는 간선을 찾는다. MST를 이루지 않는 간선을 간선 AB라고 하자. 이 때, AB를 이으면 LCA(A,B) ~ A ~ B ~ LCA(A,B) 의 싸이클이 생긴다. 그런데 이 싸이클 중 한 개의 간선만 제거해도 다시 .. 더보기
코드업 3290 : 최소 비용 신장 트리 문제링크 최소 비용 신장 트리 첫째 줄에 $N$과 $M$이 입력된다.($1Minimum Cost Spanning Tree)의 약자이다. 이를 실제 상황에 예를 들어 설명하자면, 톨게이트 A~E가 있다. 또한 톨게이트 A~E는 서로를 잇는 도로 여러개가 있고, 그에 따른 비용(가중치)도 있다. 이 때, 톨게이트 A~E를 모두 잇되(트리로 만든다) 비용이 가장 적게 드는 방향으로 잇는다(가중치의 합이 최소로 되게). (단, 여기서 거리는 상관하지 않는다.) 위 그림에는 도로(간선) 5개가 있는데 이 중 톨게이트 갯수-1(n-1)개의 도로(간선)를 '잘' 선택해서 어느 톨게이트에서 출발하더라도 어느 톨게이트에 도착할 수 있게 도로를 만들되 드는 비용이 가장 적어야한다. 이제 그 '잘' 을 해야 된다. 먼저 말.. 더보기
코드업 3410 : 금고 열기 문제 링크 금고 열기 모든 버튼을 누를 수 있는 한 개의 버튼의 좌표를 출력한다.(행, 열 순서로 출력한다.) 답이 없거나 여러 개인 경우는 주어지지 않는다. codeup.kr 이 문제는 문제 난이도에 비해 푼 사람이 적다. 이 문제가 쉬운 이유는, 완전탐색 문제이기 때문이다. 풀이 주어진 16칸이 있을 때, 각 칸에서부터 시작했을 때 답이 맞는지 아닌지 본다. 분명 문제에서 답이 없거나 여러개인 경우는 없다고 했으니, 답을 찾으면 그것이 유일한 답인 것이다. (x,y)에서 출발했을 때, 모든 칸을 한번씩 방문하면서 모두 방문한다면 답인 것이다. 이 작업을 답을 찾을 때까지 최대 4*4번만 해주면 된다. 이 문제는 방문체크 배열을 만들고, x,y 변수를 만들어 a[x][y]의 값에 따라 x 또는 y를 잘.. 더보기
코드업 5012 : 메시지 전달 문제링크 메시지 전달 입력 도움말: 5마리의 소가 있다. 1번째 소는 메시지를 전달하지 않고, 2번째 소는 4번째 소한테 메시지를 전달 하고, 같은 방식으로 진행된다. 출력 도움말: 1번째 소는 메시지를 전달 하지 않으�� codeup.kr 이 문제는 백준에는 없는 듯하다. 그래서 코드업 얘기를 하자면, 이 문제를 통과한 유저는 100명이 채 되지 않는다! (당시기준) 맞춘 유저가 100명이면 코드업 중에서는 주로 조금 어려운 문제에 속하지만, 이 문제는 생각만 잘하면 쉽게 풀리는 문제이다! 풀이 핵심은 이것이다. 확정할 수 있는 'loopy' 하지 않은 소가 메시지를 전달해야 하는 소는 없다. 또한 'loopy'한 소에게 메시지를 전달하는 소도 'loppy'하다. 예를 들어, 5 0 4 1 5 4 와 .. 더보기
코드업 1615 : 셀프 넘버(Self-Number) 문제링크 셀프 넘버(Self-Number) 1부터 10사이의 셀프 넘버는 1, 3, 5, 7, 9이다. 따라서 합은 25 codeup.kr 이 문제는 각 수의 제네레이터를 찾는 방식으로 접근하면 힘들어진다. 풀이 '이 수는 어떤 수의 제네레이터인가'를 찾는 방식으로 푼다. 예를 들어서 1은 1+1로, 2의 제네레이터이다. 그렇다면 2는 제네레이터가 있기 때문에 셀프넘버가 아니다. 이어서, 2는 2+2로, 4의 제네레이터이다. 그렇다면 4는 셀프넘버가 아닌 것이다. 이런 방법으로 셀프넘버가 아닌 수들을 찾아내면 된다. 또한 어떤수가 각 자릿수와 그 수를 더해서 나온 수의 제네레이터인 점을 생각해보면, A는 B의 제네레이터라고 할 때, A 보다 항상 B가 크다. (A가 자연수일 때) 따라서 시작 값(a)과 .. 더보기

티스토리툴바