분류 전체보기 (395) 썸네일형 리스트형 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번 기호가 최대힙에서 뽑은 요소보다 득표수가 많다면 종료해주면 되는 문제소스코드후기작곡 레슨이 있어서 빠르게 비기너 문제를 풀이했다. 쉽게 풀 수 있었던 문제 99클럽 코테 스터디 23일차 TIL: 완전탐색 + 백트래킹 문제https://www.acmicpc.net/problem/15686풀이치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력하는 문제치킨집을 고르는 것은 조합을 구하는 것을 의미한다.조합을 구하는 코드는 다음과 같이 짰다.func dfs(i: Int, selected: [(Int, Int)]) { if selected.count == m { result = min(result, getDistance(coord: selected)) return } for index in i..동일한 치킨집을 뽑으면 안되기 때문에 뽑은 치킨집 다음 치킨집 부터 탐색할 수 있도록 index 값을 파라미터로 받았다.치킨집을 뽑았으면, 특정집에서 가장 가까운 치킨집을 고르.. 99클럽 코테 스터디 22일차 TIL: 브루트포스 문제https://school.programmers.co.kr/learn/courses/30/lessons/87946풀이n이 최대 8이므로, 브루트포스로 풀 수 있는 문제이다.모든 순열을 구해 가장 많은 던전을 돌 수 있는 횟수를 구하면 된다.시간복잡도는 $O(n!)$ 으로 예상된다.예를들어 던전의 개수가 3이라면123, 132, 213, 231, 312, 321 총 6개 = 3! 이 도출된다.이는 첫번째 뽑을 수 있는 던전 수 (3), 두번째 뽑을 수 있는 던전의 수는 자기 자신을 제외한 (2) 개 .. 순으로 되기 때문이다.모든 순열을 구하는 것과 동일하다.재귀를 통하여 구해주었다.던전을 선택할 때 현재 피로도가 최소 피로도 보다 많아야 하고, 방문하지 않은 던전이여야 한다.여기서 백트래킹 기법을 사.. 99클럽 코테 스터디 21일차 TIL: 힙 응용 문제https://www.acmicpc.net/problem/19638풀이힙을 사용하여 풀 수 있는 문제이다.최대값을 계속해서 뽑아내야 하므로 최대힙을 사용하는 것이 시간복잡도 측에서 유리한 방법이다.최대힙으로 pop 연산을 하여 입력받은 h보다 작다면 YES 및 횟수 아니라면 NO 및 최대값을 출력해주면 된다.한가지 고려해야할 점으로는 1/2 연산을 하기도 전에 모든 거인의 키가 입력받은 h보다 작을 때를 고려해주어야한다.소스코드후기고려해야할 점을 몰랐다면 맞외틀이 나올만한 문제였다.. 99클럽 코테 스터디 20일차 TIL: 빠른입출력 문제https://www.acmicpc.net/problem/2075풀이Swift는 입출력이 느려 Fread 방식으로 구현된 빠른 입력을 사용해야 한다.빠른 입력만 사용해서 정렬해서 N번째 큰수를 구하는 방법도 있겠지만, Heap을 사용해서 풀이하는 방법이 있다.일반적으로 정렬은 $NlogN$의 시간복잡도를 띄는데, 힙의 pop연산은 $logN$이므로 우선순위 큐를 사용하는 편이 일반적으로 더 빠를 것이라고 생각했다.힙은 전날 풀이한 코드에 올려두어서 생략하고 동일한 코드를 사용하여 풀었다.소스코드후기빠른입력을 사용하면 쉽게 풀 수 있는 문제.백준에서 입력값이 크면 Swift 시간을 좀 늘려주면 좋겠다.. 이전 1 2 3 4 5 6 ··· 50 다음
