본문 바로가기

반응형

오블완

(21)
99클럽 코테 스터디 15일차 TIL: 스택 문제https://school.programmers.co.kr/learn/courses/30/lessons/12906풀이Stack을 사용해서 연속된 element를 제거하면 되는 문제이다.새로 드러올 요소가 TOP과 같은지 비교하면 되는 문제소스코드후기쉽게 풀 수 있는 문제였다. 시간이 없어서 비기너 문제를 풀었따.
99클럽 코테 스터디 14일차 TIL: DP 문제https://www.acmicpc.net/problem/14916풀이DP로 쉽게 풀 수 있는 문제이다.Bottom-Up 방식으로 풀이하였고, 메모이제이션 하기 위한 1차원 Int 배열을 선언하고, 값을 큰 값(INF)으로 초기화해주었다.먼저 2원과 5원만 존재하기 때문에 다음과 같이 기본값을 셋팅했다.dp[2] = 1dp[4] = 2dp[5] = 1이제 6부터 N의 최대값인 10만까지 반복문을 돌려야겠다고 생각했다.6원을 만드는 경우의 수는 4원에서 2원을 더하는 것과 1원에서 5원을 더하는 두가지 방법잉있다.하지만 1원을 만드는 방법은 없어서 4원에서 2원을 더하는 것이 최소 횟수이다.초기값: $f(2) = 1, f(4) = 2, f(5) = 1$다음과 같은 점화식을 유추할 수 있다.$if\ (..
99클럽 코테 스터디 13일차 TIL: 수학 문제https://www.acmicpc.net/problem/27961풀이이 문제는 최소 행동으로 정확히 N 마리의 고양이를 만드는 문제이다.문제를 읽어보면 눈치채겠지만, 생성마법 보다 복제마법이 무조건 유리하다.이는 그리디 알고리즘이라고 할 수 있을 것 같다.0 -> 1 -> 2 -> 4 -> 8 -> 16 ...고양이를 최소행동으로 많이 생성하려면 2의 제곱형태로 복제하는 것이 가장 빠르다.여기서 한가지 패턴을 발견할 수 있다.현재 고양이가 4마리가 있다고 가정해보자.4마리에서 7마리를 만드는거나, 8마리를 만드는거나 동일한 횟수 (복제마법) 이 필요하다는 것을 알 수 있다.4...8, 8...16, 16...32 해당 범위 안으로 고양이를 만드는 것은 동일하다.수학적으로 보면 $log_{2}N$ 임..
99클럽 코테 스터디 12일차 TIL: 3차원 그래프 문제https://www.acmicpc.net/problem/7576풀이토마토 문제와 비슷한 문제이다.조금 다른점이 하나 있는데 높이가 추가되었다는 점이다.기존에 상하좌우로 퍼졌던 토마토가, 상하좌우 위아래(?) 두 방향이 추가되었다.나는 이런 문제를 풀 때, 기존에 방향을 설정해줄 변수로 dy, dx을 다음과 같이 정의하였다.let dy = [1, 0, -1, 0]let dx = [0, 1, 0, -1]북동남서 방향으로 시계방향으로 정의하였었는데, 이제 추가로 z축도 필요하다고 생각했다.그래서 방향을 다음과 같이 정의했다.let dz = [0, 0, 0, 0, 1, -1]let dy = [1, 0, -1, 0, 0, 0]let dx = [0, -1, 0, 1, 0, 0]여기까지 이해했다면 반은 풀었다고..
99클럽 코테 스터디 11일차 TIL: DFS 문제https://www.acmicpc.net/problem/25195풀이문제 이해하는데 시간이 조금 걸렸던 문제이다.이 문제를 간단히 설명하면, 1번 노드에서 팬클럽 곰곰이를 거치지 않고 간선이 없는 노드로 도착이 가능한지를 찾는 문제이다.DFS, BFS로 풀이할 수 있을 것이라고 생각했다.DFS로 풀었는데 (요즘 맨날 BFS로만 푸는 것 같아서..)다음 노드를 탐색할 때, 해당 노드가 팬클럽 곰곰이가 있는 노드라면 탐색을 진행하지 않았다.그 이외에는 탐색을 진행하면서, 현재 노드로 부터 간선이 없는 노드라면, 팬클럽 곰곰이를 거치지 않고 여행을 한 것으로 판단해주어서 풀었다.소스코드후기문제 자체는 어렵지 않았는데 이해하는 것이 어려웠다.. 독해력을 길러야겠다고 느꼈다.

반응형