일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
- 프로그래머스
- 완전탐색
- 머신러닝
- 그래프이론
- Coursera
- Fine-Tuning
- paper review
- LLM
- 파인튜닝
- 코딩테스트
- Study
- speaking
- Generative AI
- 데이터분석
- peft
- bfs/dfs
- 플로이드와샬
- Lora
- 최단경로
- English
- 이분탐색
- 알고리즘
- 파이썬
- Scaling Laws
- DP
- 판다스
- 코드트리
- Python
- 스터디
- 코딩테스트실력진단
- Today
- Total
목록Study/Algorithm (54)
생각하는 아져씨
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/Apq6Z/btr97oXFiXX/KLnLHwsLP7zLa4yoZkb6Jk/img.png)
2559번: 수열https://www.acmicpc.net/problem/2559문제 정의어떤 정수의 수열이 주어졌을 때, 연속적인 며칠 동안의 숫자의 합이 가장 큰 값이 무엇인지 알아보는 문제이다. 접근 방법Naive 한 방법온도 리스트를 순회하면서 K만큼 해당하는 부분 리스트의 합을 구한다. → 최대 O(N2)O(N^2)O(N2) 이다.그 합들 중에서 가장 큰 부분 합을 리턴한다. 최대 O(N) 이다.따라서 시간 초과 발생하므로, 누적합을 이용해 효율적으로 풀 수 있다. 누적합을 이용한 방법온도 리스트를 순회하면서 누적합을 구해서 prefix_sum 리스트에 저장한다.K만큼 해당하는 구간 리스트의 합은 누적합의 성질을 이용해서 구할 수 있는데, 예를 들어 (5, 6, 7, 8)의 합을 구하고 싶다면..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/CMXW4/btr94xnfJA1/KMG1df468DUONExuwS93nk/img.png)
10814번: 나이순 정렬https://www.acmicpc.net/problem/10814 문제 정의온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 접근 방법정렬 기준이 나이 → 가입순서 이므로, 나이가 젊은 것부터 해당되는 이름을 출력하면 된다.대신 가입순서도 따져야 하므로, 들어오는 순서 그대로 저장해야 한다. 딕셔너리를 활용해 나이를 key, 이름 리스트를 value로 설정했다.문제 해설들어오는 입력을 key를 나이로, value를 이름 리스트로 설정한다.나이 순으로 출력해야 하므로 딕셔너리의 key 리스트를 정렬하고,그 리스트를 순회하면서 해당되는 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cSWyoP/btr97nYKXVM/pXxYFzpj7BUjQNdMjVDnX1/img.png)
1717번: 집합의 표현https://www.acmicpc.net/problem/1717문제 정의초기에 n+1개의 집합 {0}, {1},… {n} 이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. 접근 방법0이면 두 원소를 합하고, 1이면 두 원소가 같은 집합인지 확인하므로, 유니온파인드 자료구조를 활용할 수 있다. 문제 해설집합의 각 원소에 대한 부모 노드를 초기화 한다. 처음에는 각 원소가 부모노드가 된다.입력에 따라 0이면 두 원소를 합한다. 이 때 부모의 노드를 찾아서 작은 쪽의 노드가 큰 쪽의 부모가 되게끔 부모노드를 업데이트 해주면 된다.1이면 두 원소의 부모노드를 찾아서 같다면 YES, 다르다면..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/crauqL/btr9RvJBKUQ/tzIUSfn5gERwaiO8vH7Kt0/img.png)
1912번: 연속합https://www.acmicpc.net/problem/1912 문제 정의n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 접근 방법다이나믹 프로그래밍 문제임을 알고 있어서 DP 테이블을 어떻게 정의해야 할까 고민했다.예제를 보면서 규칙을 찾으려고 했다. 연속합이므로 연속적인 숫자의 합이니까 이전의 값을 활용해야지 라는 생각으로 접근했는데, 생각보다 정의하기 어려웠다. 다이나믹 프로그래밍이 맞지만, ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/0NZ2T/btr9PeImNsd/SAHdPqmhcGfcneEIIFC7sk/img.png)
9461번: 파도반 수열https://www.acmicpc.net/problem/9461 문제 정의오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 접근 방법규칙을 찾고 점화식을 세우는 다이나믹 프로그래밍을 이용한다. 문제 해설규칙을 찾으면 N=6부터 점화식을 세울 수 있다.dp[i] ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bGq57x/btr9MpYxxRL/6PSWknXT9re3YzcH31Xjd1/img.png)
https://school.programmers.co.kr/learn/courses/30/lessons/42895 문제 정의어떤 숫자 N과 numbers가 주어질 때, N과 사칙연산만 사용해서 numbers를 표현해야 한다.이 때 N 사용횟수의 최솟값을 리턴해야 한다. 접근 방법다이나믹 프로그래밍 문제임을 알고 있어서 dp 테이블을 어떻게 정의해야 하는지 고민하다가 처음에는 다음과 같이 정의했다.dp[i]: i를 만드는데 필요한 N의 최소 개수 N = 5일 때, dp[0] = 0, dp[1] = 5/5 → 2, … dp[5] = 1 그리고 점화식으로는, dp[i] = min(1~(i-1) 중 더해서 i가 되는 조합의 숫자에 해당하는 인덱스의 dp 값) 즉, dp[7] = min(dp[1] + dp[6],..