오늘의 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로 관리해도 문제가 없다. 나..

USACO(2) https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net dfs나 bfs를 사용해서 물통을 옮기는 모든 경우를 브루트포싱해주면 된다. 용량이 A고 a만큼 차있는 물통에서 (B,b) 물통으로 물을 옮기고자 할때, 1) A물통을 다 비울수 있는 경우 >> (0,a+b) 2) A물통을 다 비울수 없는 경우 >> (a+b-A, B) 이렇게 물을 옮길수 있는 경우의 수는 3P2 = 6이니까 6가지 모든 경우에 대해서 계산해주도..

USACO 문제 푸는중 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net flood-fill 문제에 해당한다 인접한 구역끼리 묶어서 가장 큰 크기의 구역을 찾는 문제. 플러드필 같은경우는 dfs로 구현해도 되고 bfs로 구현해도 되는데, 취향껏 구현하면 된다. 나는 bfs를 사용해서 구현해 보았다. 입력으로 배열이 주어지는게 아니라, 좌표값만 주어지니까 주어지는 좌표값을 이용해서 2차원 배열을 직접 만들어..

@WillKiss님의 추천으로 USACO를 천천히 밀어볼까 싶다. https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 예시로 나온 테스트케이스 a, t, c, i, s, w의 경우, i번 문자열을 선택하거나 / 선택하지 않거나 의 두가지 선택지로 나눠 브루트포싱을 진행하면 전체 경우의 수는 2^6이 된다 C=2 && c_mo >=1) return true; else return false; } void dfs(string s, int idx){ if(i..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 다익스트라 문제인데 아니 이걸 왜이렇게 오래 뇌절을 쳤는지 모르겠다 엉엉엉 시작점 S에서 이동하는 서커스 예술가가 갈 목적지 후보 중에서 G-H간 도로를 건너 이동해야 하는 경로를 구하는 문제. 즉, 목적지 후보를 K라 할때, S-K 로 이동하는 최단경로가 S-G-H-K 이거나 S-H-G-K 이면 가능한 경우에 해당하고, S-K로 이동하는 최단경로의 길이가 S-G-H-K 이거나 S-H-G-K..

https://www.acmicpc.net/problem/16900 16900번: 이름 정하기 첫째 줄에 S와 K가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. K는 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net fail 배열이 가지고 있는 값이 접두사와 접미사가 같아지는 최대 길이임을 이용하는 문제. 문자열 두개를 최대한 많이 겹쳐내면 전체 문자열의 길이가 가장 짧아지게 되기 때문에 가장 적극적으로 겹쳐내기 위해서 실패함수 값이 담긴 배열을 구해준다 가장 적극적으로 겹쳤을 때 전체 문자열의 길이는 (전혀 겹치지 않았을때의 최대 길이) - (겹쳐진 부분만큼의 길이) 이고 겹치지 않았을때의 최대 길이는 S.length() * K 로 ..

파이썬 스터디용으로 풀었던 문제. 파이썬어려워요 흑흑 https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 처음에는 입력값을 그대로 스택에 넣고 괄호쌍을 만날때 되돌아가는 방식으로 정답을 구했는데, 반례로 123(12)123(12) 와 같이 괄호쌍 두개가 떨어져있는 경우에는 제대로 계산을 못한다. val = input() st = [] ans = 0 for i in val : if i != ')' : st.append(i) else : whil..

언제나와같이 돌아온 KMP 아주 티어 올리는 맛이 달달한 태그다 https://www.acmicpc.net/problem/1893 1893번: 시저 암호 암호학에서, 시저 암호(또는 시프트 암호, 시저 코드, 시저 시프트)는 가장 간단하면서 많이 알려진 암호화 기술 중 하나이다. "시저 암호"라는 이름은 비밀 통신을 위해 이 방법을 개발한 율리 www.acmicpc.net 지문이 이해하기 그리 쉽지 않은 편인데 간단히 요약해보자면 알파벳 순서 표 A를 보고 원문 W를 X칸 이동시키면서 변환한 뒤에, 암호화된 문자열 S에서 변환된 W가 한번만 등장한다면 이때 가능한 모든 X를 찾는 문제이다. 문제를 나눠서 생각해보자. 1. 순서표 A를 보고 W를 한칸씩 이동시키기. 알파벳과 숫자를 매칭시켜 주는 unord..