https://www.acmicpc.net/problem/14244 14244번: 트리 만들기 n과 m이 주어졌을 때, n개의 노드로 이루어져 있고, m개의 리프로 이루어져 있는 트리를 만드는 프로그램을 작성하시오. 항상 정답이 존재하는 경우만 입력으로 주어진다. 트리는 사이클이 없는 www.acmicpc.net 난이도는 쉽지 않아보이는데 의외로 쉽다. 알고리즘 분류에 나와있듯 트리를 이용한 구성적인 문제다. 트리가 어떻게 구성되는지 일반화 될 수 있는 규칙을 찾아 문제를 풀면 된다. 문제 조건에 의해 리프노드는 항상 최소 2개이고, 답이 항상 존재한다. 리프노드가 2개인 경우는 딱 한가지다. 모든 노드가 일직선으로 연결되면 된다. 리프노드가 3개 이상인 경우는 하나의 중심 노드에 대해 리프노드를 3개 ..
https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net class5 문제를 풀면서 만났던 생 수학 문제. 두 정수가 주어질 때, 두 정수를 포함하는 범위의 모든 정수를 이진수로 변환했을 경우 1의 개수를 모두 세는 문제이다. 곧이곧대로 구하면 수의 범위가 커서 시간초과를 받는다. 나는 다음과 같은 풀이를 떠올렸다. 1. 누적합 [a, b] 구간의 모든 정수의 이진수의 1의 개수를 직접 구하기보다 [1, a] 구간의 이진수의 1..
https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 이 문제는 겉보기에는 단순한 구현 / 시뮬레이션 문제이다. 상어 이동을 구현하고, 낚시만 하면 되는데, 이 상어 이동이 생각보다 까다롭다. 이동하다가 만나면 잡아먹는다는 점에서 구현하면서 윷놀이 문제 생각이 났다. 상어가 만나면 서로 잡아먹는다는 부분, 가장자리에 닿으면 방향이 반대로 바뀌는 부분을 구현하는게 힘들었다. 내가 이 문제를 풀면서 실수한 부분은 2가지였다. 1. 한..
https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net 같은 부분 문자열이 2개 이상 나타나는 가장 긴 부분 문자열의 길이를 찾는 문제이다. 나는 골드 3의 티어로 난이도를 낮게 매겼다. 나는 신촌 연합 알고리즘 캠프에서 배운 라빈 카프 알고리즘에 이분탐색을 더하여 풀었다. 이분탐색을 사용한 이유는 다음과 같다. 부분문자열의 길이가 n일 때 문제 조건을 만족한다면 이 해당 부분문자열의 부분문자열도 문제의 조건을 만..
https://www.acmicpc.net/problem/23059 23059번: 리그 오브 레게노 첫째 줄에는 백남이가 알고 있는 아이템 사이의 관계의 수 $N$(1 ≤ $N$ ≤ 200,000)를 입력받는다. $N$개의 줄에 걸쳐서 아이템 이름을 의미하는 문자열 2개 A B가 주어진다. 아이템 A는 아이템 B를 구 www.acmicpc.net 1. 아이템의 일부 구매 순서로 전체 구매 순서를 찾는다 => 위상정렬 2. 이때, 구매 과정이 현재 구매가능한 아이템을 모두 "찾기만 하고" 그 결과를 이름 순대로 구매한다. 이 점만 주의하면 된다. 나는 아이템은 맵으로 관리하고 우선순위큐와 위상정렬을 섞어서 풀었다. 맵에 저장한 아이템에 대해 위상정렬 한다. 현재 살 수 있는 아이템 리스트를 만든다. 만들면..
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 시뮬레이션, 구현, 브루트포스 유형의 문제이다. 생각보다 구현이 빡빡하다. (체감 난이도 골드4) 이 문제를 풀 때 내가 실수했던 부분은 하나였다. 감시구역이 겹치는 점을 고려하지 못한 것이다. 그래서 백트래킹으로 감시구역을 바꿀때, 다른 CCTV에 의해서도 감시되는 구역에 대해 감시를 풀어버린 것 때문에 틀렸었다. 그래서 숫자를 이용해 감시 카운트를 세도록 했다. 감시가 생길때마다 숫..
https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 쓸데없이 힘들게 푼 문제이다. 알고리즘 분류가 백트래킹에 브루트포스였는데, 그렇게 풀었으면 더 쉽게 풀었을 것 같다. 전체 경우의 수가 1023가지 밖에 되지 않아서, 그냥 모든 케이스를 순서대로 방문해보면 된다. 각 숫자가 중복으로 쓰일 수 없어서 비트마스킹을 활용한 풀이도 있었다. 나는 DP 에 역추적을 써서 풀었다. 정말 빙빙 돌아서 풀었다 ㅋㅋㅋ 내가 푼 풀이는 2차원 DP ..
https://www.acmicpc.net/problem/15778 15778번: Yut Nori 윷놀이는 한국의 전통놀이중 하나로 윷가락을 가지고 진행하는 놀이이다. 윷놀이는 윷가락 4개와, 내 말 4개, 상대편의 말 4개로 총 말 8개 그리고 윷판 하나를 가지고 진행한다. 윷판은 다음과 www.acmicpc.net 진짜 디버깅.. 너무 힘들었다. 내가 스스로 고안한 풀이 방법으로 풀 땐 죽어도 안풀리다가,,,, 다른 사람이 사용한 구현 아이디어를 활용하여 구현하니까 한번 틀렸는데, 다행히 틀린 부분이 예제 입력 2번으로 디버깅이 되서 바로 통과됐다. (그래서 자존심에 매우 큰 스크래치를 입은 상태이다..ㅡㅡ) https://swoon1.tistory.com/4?category=804646 [파이썬] ..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 나는 투포인터를 안쓰고 풀었는데, 정해가 투포인터라서 놀랐다. 확실히 '어떤 정렬된 것들중 일부의 연속' 은 투포인터를 쓰기 좋다. 일단 이 문제가 골드3이라서 당연히 DP부터 의심했는데, DP가 아닌 풀이가 떠올라서 바로 구현했다. 내가 푼 풀이와 투포인터 풀이를 모두 적어보겠다. 이분탐색을 이용한 풀이 소수의 리스트 2, 3, 5, 7, 11, 13, ,,,, 가 있다고 하고 소수의 누적합 배열을 s 라고 해보자. (누적합 배열은 0부터 시작한다고 하자) 최적해가 되는 구간은 어떤 소수로 시작할 것이다. 2로 시..
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 간만에 만난 진짜 너무 이해하기 어려웠던 문제이다. 이 문제를 풀고 이해하는데 3시간이 걸렸다 (이래야 골드1이지..) 이 문제의 핵심은 3가지다. 1. 최적해는 결국 사이클이기 때문에 어디에서 시작점을 잡아도 좋다. 2. 지금까지의 누적된 값에 내 값을 더해주는게 아니라, 누적될 값을 넘긴다. 3. 최소를 구할 때도 0을 조심하자. 1. 최적해는 결국 사이클..
