TIL (31) 썸네일형 리스트형 99클럽 코테 스터디 31일차 TIL: 정렬 문제https://www.acmicpc.net/problem/1755풀이간단한 구현 및 정렬문제이다.Swift에 sort 메서드 안에서 클로저로 정렬하는 방법을 제시해 주는 방법으로 풀이하였다.숫자를 문자로 변환하는 것은 dictionary를 쓰거나 enum을 사용하거나 여러 방법으로 할 수 있지만 enum으로 풀었다.소스코드후기쉽게 풀 수 있는 문제였다. 99클럽 코테 스터디 30일차 TIL: LIS 문제https://www.acmicpc.net/problem/1965풀이LIS를 구하는 문제이전에 풀었던 문제와 동일하다.다만 이전에 풀었던 문제에서는 LIS를 구하라고 명확히 나와있는데,이 문제는 문제를 읽고 LIS를 구해야한다고 깨달아야? 하는 문제근데 LIS를 알고 보면 쉽게 도출할 수 있었다.소스코드후기LIS를 구하는 문제. N이 컸다면 이분탐색으로 구했을 것 같다. 99클럽 코테 스터디 29일차 TIL: DP 문제https://www.acmicpc.net/problem/9461풀이전형적인 dp 문제이다.초기값은 다음과 같다.$f(1) = 1, f(2) = 1, f(3) = 1$점화식은 다음과 같다.$f(n) = f(n-2)+f(n-3)$초기값과 점화식을 알면 DP 문제는 그냥 풀 수 있다.소스코드후기어제 그저께 풀었던 dp 문제보다는 훨씬 쉬웠던 문제 99클럽 코테 스터디 28일차 TIL: LIS 응용 문제https://www.acmicpc.net/problem/11055풀이어제 풀었던 문제에서 약간만 응용하면 쉽게 풀 수 있는 문제이다.dp값을 초기화 하는 것은 자기 자신의 값으로 초기화 해주자.=> 자기 자신도 부분수열이 될 수 있기 때문이중 for문을 돌면서 이전 원소보다 크다면 내 원소를 붙일 수 있는 것을 기억하자.코드는 어제 푼 것과 거의 동일하다.소스코드후기전날 풀었던 문제와 거의 유사해서 쉽게 풀 수 있었다. 99클럽 코테 스터디 27일차 TIL: LIS 문제https://www.acmicpc.net/problem/11722풀이이 문제는 LIS 라는 유명한 알고리즘이다.이미 알고있는 알고리즘이였는데 문제를 풀어본 건 엄청 오랜만이였다.dp로 구하는 방법이랑 이분탐색으로 구하는 방법이 있었던 것 정도만 기억이 났고..dp로 구하는 방식은 어렴풋이 기억이 나는데 이분탐색방식은 기억이 잘 나지 않았다.일단 dp로 풀어보고 이분탐색 방식을 학습하고자 했다.dp로 푸는 방법은 간단하다.먼저 dp 배열을 선언하고 dp[n]은 n까지의 수열 중에서 가장 긴 감소하는 부분 수열의 길이를 의미한다.일단, 첫 항은 $a1 = 1$ 이다. 왜냐하면 자기 자신의 원소도 부분 수열이기 때문이다.[3, 2, 4, 1] 라는 수열이 있을때를 한번 살펴보자dp[1]일 때, 즉 [3].. 99클럽 코테 스터디 26일차 TIL: 게임 문제https://www.acmicpc.net/problem/9655풀이알고리즘 분류중에 DP가 있다.일단 DP적으로 생각하지 말고 최선의 선택을 했을 때, 누가 이기는지 패턴을 살펴보았다.돌이 1개일 때, 바로 가저가면 되므로 상근이가 이긴다. SY2 일때, 상근이는 1개 가져가는 행위 밖에 못한다. 그러므로 나머지 1개 가져가는 행위를 하면 됨(돌이 1개일 때) CY3 일때, 상근이가 3개 가져가면 됨. SY4 일때, 상근이가 1개를 가져가든 3개를 가져가든 창영이가 이김 CY=> 여기서 상근이가 3개를 가져가는 행위를 통해 창영이는 돌이 1개일 때의 행위를 하면된다.=> 상근이가 1개를 가져가면 창영이는 돌이 3개일 때 행위를 하면 됨SY, CY가 반복된다. 홀수일 때는 SY 짝수일 때는 CY이다... 99클럽 코테 스터디 25일차 TIL: 완전 탐색 문제https://www.acmicpc.net/problem/2116풀이문제 이해하기가 살짝 어렵지만 어렵게 생각하지 말고 쉽게 생각하면 다음과 같다.첫 번째 주사위를 놓는 방법에 따른 최대값 구하기!처음 주사위를 놓는 방법은 딱 6개가 존재하기 때문에 각각 방법으로 놓아보고,그 외 주사위들의 상,하를 이전 주사위와 맞춰주어야 한다.맞춰주고, 상 하 값을 제외한 나머지 값들 중 가장 큰 값을 더해준다.왜냐하면 주사위 회전이 가능하기 때문이다.첫번째 주사위를 놓는 방법 (6가지) 중 가장 큰 값을 출력해주면 되는 문제소스코드후기머리가 조금 아팠지만 재밌는 문제였다. 99클럽 코테 스터디 24일차 TIL: 최대 힙 + 그리디 문제https://www.acmicpc.net/problem/1417풀이1번 기호가 나머지 기호보다 많은 투표수를 받도록 해주어야 한다.최소 표를 구해야 한다.나머지 후보들 중에서 가장 득표를 많이받은 후보의 표를 뺏어와야 하므로, 최대값을 뽑아야하는데최대힙을 구현하면 빠르게 최대값을 구현할 수 있다.최대힙에서 pop 연산을 하고, 뽑은 요소에 -1을 해주어 다시 최대 힙에 넣어주고1번 기호의 표를 + 1 해준다.이를 반복하며 1번 기호가 최대힙에서 뽑은 요소보다 득표수가 많다면 종료해주면 되는 문제소스코드후기작곡 레슨이 있어서 빠르게 비기너 문제를 풀이했다. 쉽게 풀 수 있었던 문제 이전 1 2 3 4 다음
