boj,백준) 1039. 교환(C / C++)
1. 문제 링크 www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 2. 문제 개요 0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다. 1≤ i < j ≤ M 인 i와 j를 고른다. 그다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다. 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오. 3. 문제 힌트 그리디로 접근하려고 했으나..... 안 될 것 같다. 문제 유형을 보니 BFS..
boj, 백준) 20055. 컨베이어 벨트 위의 로봇 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 2. 문제 개요 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 1번 칸이 '올라가는 위치' N번칸이 있는 위치를 '내려가는 위치'라고 하자. 로봇은 '올라가는 위치'에서만 올라가고 '내려가는 위치'에서만 내려간다. 로봇이 올라가는 곳은(놓거나 걸어서) 내구도가 1 감소한다. 컨베이어 벨트를 이용해 로봇들을 건너편으로 옮..
boj, 백준) 20061. 모노미노도미노2 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 2. 문제 개요 및 풀이 kibbomi.tistory.com/172 boj, 백준) 19235. 모노미노도미노 ( C / C++ ) 1. 문제 링크 www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙 kibbomi.tistory..
boj, 백준) 19235. 모노미노도미노 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 2. 문제 개요 가로 칸, 세로 칸이 있다. 블록이 생성되고 블록을 이동시킨다. 4줄이 가득 차면 지우고 블록을 다시 내리고... 등등 색깔이 연한 칸에 블록이 있으면 밑에서부터 지우고.. 등등의 작업을 한다. 점수와 남은 블록의 개수를 출력하는 프로그램을 만들자. 3. 문제 힌트 하나 하나의 동작을 모듈화 시키자. 특별한 알고리즘은 필요 없다. 침착하게 블록들을 어떻게 표현할 수 있을까..
boj, 백준) 13023. ABCDE ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 2. 문제 개요 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 관계가 존재하는지 안 하는지 구하는 프로그램을 작성하시오. 오랜만에 DFS문제를 풀었는데 처음 생각을 잘못해서 10%쯤에서 계속 틀렸다.. 끙끙 앓다가 풀고 나니 허탈한 문제. 3. 문제 힌트 결국 문제의 의미는 4번 연속으로 연결되는, DFS를 할 때 깊이가 4인 것이 단 한 개라도 있으면 1을 출력하면 된다. 위의 가..
boj, 백준) 9426. 중앙값 찾기 ( C++ )
1. 문제 링크 www.acmicpc.net/problem/9426 9426번: 중앙값 측정 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 250,000, 1 ≤ K ≤ 5,000, K ≤ N) 둘째 줄부터 N개 줄에 측정한 온도가 순서대로 주어진다. 온도는 0보다 크거나 같고, 65535보다 작거나 같은 정수이다. www.acmicpc.net 2. 문제 개요 주어진 데이터의 부분 수열의 중앙값을 찾아 모두 합을 구하는 프로그램을 만드시오. 3. 문제 힌트 세그먼트 트리를 사용해보자. 매번 정렬하여 중간값을 꺼내는 방식이나, merge sort처럼 각 세그먼트 트리에 정렬된 값을 갖고 올라가는 것은 O(NK)로 시간이 아슬아슬할 것 같다. 뭔가,, 공간 복잡도를 희생해서 시간 복잡도를 줄일 수 있는 방..