USACO https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net N이 8만으로 크기 때문에 O(N^2) 시간복잡도를 가지는 프로그램으로는 이 문제를 해결할 수 없다. 풀이가 떠오르지 않아서, stack 자료구조를 사용한다는 힌트를 태그 분류를 통해 얻고 시작했다. 기존의 K번 빌딩에서 볼 수 있는 빌딩 옥상의 개수를 확인하려면, K보다 큰 인덱스에 대해 탐색을 해야 하는데, 문제를 거꾸로 뒤집어서 K번 빌딩"을" 볼 수 있는 빌딩들의 개수 로..
ㅂUSACO 문제풀이 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 힌트를 유심히 봐야할 필요가 있는 문제 얼핏 보기에는 매우 dfs/bfs 문제같이 생겨먹었지만 위 사진에서의 두번째 힌트에서 보듯 dfs/bfs로는 "Y" 자 탐색을 진행할 수 없기 때문에 다른 접근이 필요하다. 전체 판이 25칸으로 만들어져 있고, 이중에 '소문난 칠공주'의 7개 칸이 반드시 자리하고 있어야 하기 때문에, "브루트포스 알고리즘" 이라는 태그에 맞게 25개 칸 중..
오늘의 USACO(6) https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net [s,e] 구간의 합이 N이 되도록 하는 s,e 쌍의 갯수를 구하는 문제. 처음에 문제를 보고 들었던 생각은 누적합 배열 이었고, 그래서 구간을 편의상 (s,e] 로 조정한 다음, N의 범위 천만까지의 연속된 자연수의 합을 담아두는 prefix 배열을 만들어서 prefix[e] - prefix[s] 로 (s,e] 구간의 자연수의 합을 구하려는 생각을 했..
오늘의 USACO(5) https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net MST = 최소 스패닝 트리를 구하는 문제. N개의 정점을 N-1개의 간선만을 사용해서 가장 가중치가 적게 연결해내면 된다. 나는 크루스칼 알고리즘을 사용해서 문제를 해결했다. 크루스칼 알고리즘의 구현에 있어서 연결되었는지 연결되지 않았는지를 판별하는데 유니온 파인드 자료구조를 사용하니까 이 역시 미리 배워둬야 문제를 해결할 수 있다. 좌표쌍만 주..
USACO(4) https://www.acmicpc.net/problem/2089 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net 진수 변환 방법에 대해서 먼저 숙지해야 하는 문제. 10진수 >> 2진수 변환을 계산할수 없으신 분들이라면 이 문제를 잡기 전에 2진수 변환 먼저 배우고 오는 것이 좋다고 생각한다. 일반적인 2진수 변환은 2로 나눈 나머지를 저장하고 숫자를 2씩 나눠간 다음 저장한 값들을 뒤집어서 출..
USACO(3) https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 판의 크기가 작고, 탐색 깊이가 깊지 않아서 브루트포싱으로도 충분히 문제를 해결할 수 있다. 4방향^6회 * 25가지 좌표 대략 10만번쯤 탐색할거같다. 6번 탐색하기 때문에 6번을 탐색해 만들어진 가장 큰 숫자는 999999 이므로, int범위도 벗어나지 않고, 문자열으로 붙여서 관리하는게 아니라 그냥 int로 관리해도 문제가 없다. 나..