전체 글
-
백준 2352(반도체 설계)전공/알고리즘 2020. 10. 7. 13:06
www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 문제를 잘 읽고 생각을 좀 하다보면 n번 포트를 꽂을 차례가 되었을 때, 그 전에 최종적으로 무슨 포트를 어디에 꽂았느냐를 가지고 이게 가능한지 아닌지를 판단할 수 있다. 따라서 가능한 경우에만 갯수를 하나씩 늘려나가면서 저장을 하면 dp로 풀수 있다는 것을 알 수 있다. 그렇게 dp로 풀 수 있다고 생각을 했지만 입력이 40000이므로 N^2의 전체 확인 알고리즘으로 풀면 시간초과가 난다...
-
백준 1759(암호 만들기)전공/알고리즘 2020. 10. 5. 16:05
www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 딱 봐도 브루트포스이다. 들어가고 안 들어가고, 총 15^2 의 시간복잡도가 소요된다. 따라서 잘 전처리하고, 들어갈때 안 들어갈 때를 구하면 된다. 전처리라고 함은 사전식 배열로 바꾸어 줘야 한다. 그냥 sort로 정렬을 하면 된다. 그러고 나서 재귀로 돌리는데 조건을 잘 짜주자. #include #include #include using namespace std; int L, C, mo, ja; vector v;..
-
백준 13424(비밀 모임)전공/알고리즘 2020. 10. 5. 15:25
www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 그래프로 최단 거리를 구하는 문제이다. 최단 거리 알고리즘은 대표적으로 다익스트라가 있는데 이 알고리즘은 1vsN이므로 이 문제에서 요구하는 NvsN과는 좀 맞지 않는다 그래서 NvsN의 최단거리 알고리즘인 플로이드 와샬을 사용한다. 그래프를 구현하고, 플로이드 와샬 이용, 원하는 값을 구한다. 주의해야 할 점은 본인과 본인의 거리는 0이다 #include #include using namespace std; ..
-
16494전공/알고리즘(생각 멈춘거) 2020. 10. 5. 14:43
https://xkdlaldfjtnl.tistory.com/194 22.03.15 풀이 백준 16494 가장 큰 값 https://www.acmicpc.net/problem/16494 16494번: 가장 큰 값 첫째 줄에 N과 M(1 ≤ M ≤ N ≤ 20)이 주어진다. 둘째 줄에는 수열에 속한 수가 주어진다. 수는 공백으로 구분되어져 있고, 절댓값이 100보다 작거나.. xkdlaldfjtnl.tistory.com 위 링크 보세요 ----------------------------------------------------------------------------------------------------------------------- ----------------------------------..
-
백준 15886(내 선물을 받아줘 2)전공/알고리즘 2020. 10. 5. 13:43
www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직 www.acmicpc.net 문제 좀 제대로 읽자 처음에 위치에 따라 움직이는 것이 정해진다고 이해를 못 하고 단순 그 방향대로 무조건 움직여야 된다고 생각을 했다. 하지만 지도의 위치에 따라 움직인다면 무조건 EW가 있는 곳으로 향하기 때문에 EW의 갯수를 정하면 된다. 그래프로도 풀 수 있는 것같은데 지금은 생각이 안난다. #include using namespace std; int before = '0'; int main..
-
백준 2885(초콜릿 식사)전공/알고리즘 2020. 10. 4. 23:15
www.acmicpc.net/problem/2885 2885번: 초콜릿 식사 학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, ... www.acmicpc.net 2^n개를 무조건 절반씩 쪼갤 수 있을때를 묻는 문제 이진수를 생각하면 된다. 구현도 쉽고 아이디어도 쉬운 문제 아 주의해야 할 점이 아래 코드에서 K==num이랑 K>num일때랑 따로 구분해서 설정해주어야한다. #include using namespace std; #define MAX 20 int main() { int K; cin >> K; int num = 1, min_n=-1, h..
-
백준 1309(동물원)전공/알고리즘 2020. 10. 4. 22:22
www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 500문제 달성 위해서 랜덤문제를 푸는 첫 문제. 그냥 점화식 찾는 문제이다. 점화식을 잘 찾아보자 근데 생각보다 점화식이 너무 어려웠다. dp[N] = dp[N-1]*2 + dp[N-2] #include using namespace std; #define MAX 100005 int dp[MAX]; int solve(int idx) { if (dp[idx]) return dp[idx]; int ret=0; ret = (solve(idx-1)*2 + solve(idx-2)) % 9901; return dp[idx] = ret; } int main..
-
브루트포스 168p clocksync전공/종만북 2020. 10. 3. 16:45
algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 �� algospot.com 먼저 규칙을 찾았었다. 어떤 스위치를 누르면 어떻게 되는지 좀 알아보다가 스위치는 10개 각각 4번씩 누르면 모든 경우의 수를 알 수 있는 문제였다. 그래서 계산을 해보니깐 시간적 여유가 있어서 그냥 브루트포스로 풀었다. 4^10 의 시간복잡도 사실 이것보다 더 오래걸릴것이다. 재귀로 구성했고, 각 재귀함수 호출마다 반복문도 들..