일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
- 알고리즘
- 완전탐색
- 파이썬
- DP
- English
- bfs/dfs
- speaking
- Python
- 플로이드와샬
- Coursera
- Lora
- Fine-Tuning
- 코딩테스트
- 판다스
- 머신러닝
- Generative AI
- paper review
- 데이터분석
- 파인튜닝
- 코드트리
- peft
- Study
- 스터디
- 그래프이론
- Scaling Laws
- 프로그래머스
- LLM
- 이분탐색
- 코딩테스트실력진단
- 최단경로
- Today
- Total
목록Study/Algorithm (54)
생각하는 아져씨
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bcrWVQ/btrNYTMiKAj/lrttIkYAlErGTrvHGAMKc0/img.png)
문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 🚦 문제 유형 자료 구조 정렬 우선순위 큐 ✏️ Solution 파이썬의 heapq 라이브러리를 사용하여 우선순위 큐를 통해 문제를 풀 수 있다. N이 최대 1500이고 최대 2,250,000개의 값을 가질 수 있는데, 그 중 N번째 큰 수를 찾기위해 순차탐색을 하는 것은 시간초과가 뜰 것이다. 최댓값 또는 최솟값을 찾을 때 힙 자료구조를 활용하면 쉽게 구할 수 있다. N번째 큰 수를 찾는 방법은 모든 원소를 힙에 넣고 max_heap 구조에서 N번 heapq.h..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/xvgAq/btrMozVrWcY/SByInqJjDMkQIdsML66Bg0/img.png)
문제 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 🚦 문제 유형 자료구조 스택 연결 리스트 ✏️ Solution 이 문제는 시간제한이 0.3초로 매우 짧아서 시간복잡도를 생각하면서 풀어야 한다. 풀이 방법은 3가지를 생각해 볼 수 있다. 입력 문자열 리스트에 커서를 추가해서 명령어 대로 수행 스택 사용 - 커서를 따로 추가하지 않고 2개의 스택으로 명령어 수행 덱 사용 - 커서를 따로 추가하지 않고 1개의 리스트와 1개의 덱으로 명령어 수행 1. 입력 문자열 리스트에 커서를 추가해서 명령어 대로 수행 입력 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/blsLQC/btrLFzp2SWG/L7oDh3PWRKoP5HhkBLxhR1/img.png)
문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 식의 계산은 연산자 우선..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bTOCSB/btrLFHfQPWR/BJ5zcmgs9cQ33fMiuUw4k1/img.jpg)
문제 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다. 입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단..
문제 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자. 입력 첫째 줄에 배열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231−1보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 최소 회의실 개수를 출력한다...
문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 10^9) 출력 강의실의 개수를 출력하라. 🚦 문제 유형 Greedy 알고리즘 ✏️ Solution 문제 속 빨간색으로 표시된 부분에서 풀이방법에 대한 힌트를 얻을 수 있다. 먼저, 최소의..