Still Young

A. Entertainment in MAC 접근 방식 연산 횟수와 string이 주어질 때, 두가지 연산 중 하나를 주어진 연산 횟수 만큼 하게 된다. 연산 1. 주어진 string과 주어진 string의 reverse 붙이기 연산 2. 현재까지 만들어진 string 뒤집기 이 때, 모든 연산이 완료된 후 사전 순으로 나열했을 가장 앞에 있을 string을 찾는 문제이다. 무작정 string을 붙이면 이전에 만들어진 문장보다 사전순으로 뒤로 가기 때문에 좋은 방식이 아니다. 만약 reverse한 string을 한번 붙이게 되면 해당 string은 palindrome이다. Solution 우선 현재 string과 reverse string을 각각 str1, str2라 명명해보자. str1 str2 우선 s..

A. Shuffle Party (링크) 접근 방식 { 1, 2, ... , n} 인 수열이 주어졌을 때, swap(i)를 i=1 to i =n을 했을 때, 1의 위치를 구하는 문제이다. 우선 swap(k)의 결과를 나열해보자. k = 5 까지 나열해보면 - swap(1) = None - swap(2) = 1 - swap(3) = 1 - swap(4) = 2 - swap(5) = 1 Solution 잘 보면 1은 swap(2)에 의해 2와 위치를 바꾸게 되고 이후에 swap(4)에 의해 4와 위치가 바뀌게 된다. 사실 여기서 감으로 1은 현재 위치 * 2를 계속 한다는 것을 알 수 있는데, 엄밀하게 한번 생각해보자. 어떤 수 swap(k) = 2^n 인 k의 최소 값이 2^(n+1)임을 확인하면 된다. x..

A. Too Min Too Max(링크) 접근 방법 수식적으로 증명하는 방법이 있으나, A인 만큼 빠르게 직관으로 접근해보았다. 4개의 숫자, a, b, c, d가 있다고 하자. 이 때, 차례로 이웃한 숫자와의 차이가 가장 크게 만들면 된다. 그렇다면 a, b, c, d를 가장 큰 수, 가장 작은 수를 반복해서 넣으면 된다는 생각으로 이어진다. Solution 수열을 정렬한 후 a, b, c, d를 차례로 (가장 큰 수) (가장 작은 수) (두번째로 큰 수) (두번째로 작은 수)로 하여 문제에서 말하는 수식을 풀면 된다. import sys input = sys.stdin.readline sys.setrecursionlimit(int(1e9)) T = int(input()) while T: T -= 1 ..

오늘 장병규 의장님께 내가 알고리즘 공부를 하면서 몰입하는 경험을 제대로 못하는 이유에 대해서 여쭤봤다. 의장님께서 가능성을 짚어주셨는데 내가 좋아하는 것이 아닐 수도 있다. 나에게 큰 의미가 없는 일 일수도 있다. 군대 안에 있다는 환경적 요인이 문제일 수도 있다. 우선, 내가 좋아하는 일은 확실하다. 문제를 풀지 못하고 잘 때에는 좀 더 풀다가 자고 싶은데 내일 근무 때문에, 혹은 취침시간 때문에 더 이상 풀지 못한다는 사실이 분통할 정도니까. 군대 안에 있다는 환경적 요인은 어느 정도 동의한다. 문제를 풀던 중 일과 때문에 불려 나가기도 하고 집중해서 공부할 수 있는 시간이 제한되기도 한다. 하지만, 내가 집중해서 보고 싶은 것은 2번째, 나에게 어떤 의미가 있는가이다. 내가 미래에 꼭 하고 싶은 ..

Level Bronze 문제 링크 [백준] https://www.acmicpc.net/problem/21822 [USACO] http://www.usaco.org/index.php?page=viewproblem2&cpid=1133 문제 요약 C, G, .로 이루어진 board에서 G와 바로 인접한 C가 2개 이상인 G의 최대 개수를 구하는 문제이다. 이때 같은 C쌍은 최대 한개의 G에만 영향을 줄 수 있다. [내 풀이] 해결 방법 이 문제를 통해서 나의 나쁜 습관을 찾았다. 최대/최소만 보면 DP를 떠올리는 습관이다. 하지만, 문제를 달리봐서 Greedy로 푸니 문제가 해결되었다. 이 문제의 어려운 점은 바로 같은 C쌍은 최대 한개의 G에만 영향을 줄 수 있다는 점이다. 아래 상황을 살펴보자. 묶는 방법..

Level Bronze 하.. 풀고 나니까 브론즈인 것 같은데 풀 때는 너무 안 풀려서 꽤나 고생했었다. 문제 링크 [백준] https://www.acmicpc.net/problem/21821 [USACO] http://www.usaco.org/index.php?page=viewproblem2&cpid=1132 문제 요약 N명의 사람 이름을 입력받는다. 이후에 K번 이름 sequence를 입력받는데 sequence 중간에 알파벳 순서가 뒤집힌 경우 앞에 있는 사람이 뒤에 있는 사람보다 서열이 낮다는 것을 의미한다. 주어진 K개의 sequence를 통해 사람 간의 우위를 출력하는 문제 [내 풀이] 해결 방법 우선 매번 이름을 비교하는 작업을 하게 되면 연산의 낭비가 있으므로 각 이름 간 알파벳 순서 상 누..

Level Bronze 문제 링크 [백준] https://www.acmicpc.net/problem/21820 [USACO] http://www.usaco.org/index.php?page=viewproblem2&cpid=1131 문제 요약 \(c\)배열의 일부 요소에 총 L을 더했을 때, 값이 h 이상인 요소가 h개 이상이라는 조건을 만족시키는 h의 최댓값 구하기 [내 풀이] 해결 방법 우선 \(c\)배열의 각 요소의 값이 몇 개씩 있는지를 저장하는 배열 \(d\)를 만든다. 이후에 \(d\)배열의 처음부터 끝까지 순회하며 문제에서 요구하는 대로 \(max_{i=0}^n(min(i,\sum_{i}^{n}d[i]))\) 를 구한다. 이 문제에서 한 가지 challenge가 있다면 L만큼 요소의 수를 더할..

문제 링크 [백준] https://www.acmicpc.net/problem/16940 문제 요약 Tree와 이 Tree를 순회하면서 방문한 노드의 순서가 주어질 때, 순회방법이 BFS인 지 알아보기 해결 방법 BFS에서는 현재 방문하는 node의 level 이 0이라면 node의 children의 level은 1, children의 children의 level은 2가 된다.쉽게 생각하면 level이 n인 노드의 children의 level은 n+1이된다. 또한, queue에 들어간 순서대로 방문하기 때문에level(u)> n; vectoradj(n+1); vectorlevel(n+1, -1); vectorparent(n+1, -1); for(int i=0; i+1> u >> v; adj[u].push_..

Level Bronze 문제 링크 [백준] https://www.acmicpc.net/problem/23880 [USACO] http://www.usaco.org/index.php?page=viewproblem2&cpid=1157 문제 요약 board에서 .은 갈 수 있는 길, H은 지나갈 수 없는 길이라고 할 때, 좌상단에서 우하단으로 가는 경로의 수 이때, 오른쪽으로 혹은 아래로만 갈 수 있는데 최대 k번 방향을 바꿀 수 있다. [내 풀이] 해결 방법 전형적인 경로의 방법 수를 찾는 dp문제라고 생각했다. dp[i][j][d]는 (i,j)으로 이동할 때 도달할 수 있는 경우의 수이다. d의 값은 0과 1인데 각각은 처음에 오른쪽으로 이동하는 경우와 아래로 이동하는 경우를 나타낸다. board[i][j..

Level Bronze 문제 링크 [백준] https://www.acmicpc.net/problem/23879 [USACO] http://www.usaco.org/index.php?page=viewproblem2&cpid=1156 문제 요약 배열의 연속된 요소들의 값을 한번 올리거나 내리는 경우를 연산 1번으로 볼 때, \(t\) 배열을 \(p\) 배열과 동일하게 만드는데 필요한 최소 연산 횟수 구하기 [내 풀이] 해결 방법 우선 \(d[i]=t[i]-p[i]\)를 통해 \(p\) 배열과 \(t\) 배열의 차이를 배열에 저장한다. 값을 올리거나 내리는 것보다 연속된 요소들의 값을 한 번에 올리거나 내리는 경우가 더 효율적이다. 하지만, 어떤 방식으로 범위를 설정할지가 문제이다. \(d[a]>0\), \(..