알고리즘
-
[Python] 백준 15961, 2531 회전 초밥알고리즘/문제풀이 2021. 7. 17. 21:27
1. 문제 링크 https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmi..
-
[Python] Programmers 순위 검색알고리즘/문제풀이 2021. 7. 17. 21:23
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/72412 총 16가지 종류 for i in info: i = i.split() case = get_combinations(i) for c in case: all_info[c].append(int(i[-1])) # 2. dict에 있는 리스트 점수를 이분 탐색해서 구하기 위해 sorting for k in all_info.keys(): all_info[k].sort() # 3. 쿼리 하나씩 돌려 해당 조건에 있는 dict를 찾아 이분탐색으로 점수에 맞는 사람 찾기 for q in query: q = q.replace("and","").split() score = int(q.pop()) q = ""...
-
[Python] Programmers 광고 삽입알고리즘/문제풀이 2021. 7. 17. 21:17
1. 문제 링크 코딩테스트 연습 - 광고 삽입 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 2. 문제 요약 시청자들의 누적 재생시간이 가장 많은 곳 찾기 ⇒ 누적합으로 구하기 [입력값] play_time: 동영상 끝나는 시간 adv_time: 공익광고 재생 시간 logs: 시청자들 시청하는 구간 [리턴 값] 광고 삽입할 시작 시간 - HH:MM:SS (str) 3. 아이디어 정리 누적합으로 해당 구간에 몇 명이 시청하는지 구한다. 초 ..
-
[Python] 백준 2206 벽 부수고 이동하기알고리즘/문제풀이 2021. 7. 17. 21:12
1. 문제 링크 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 문제 요약 최단 경로 구하기 문제 → bfs 탐색 벽을 1개까지만 부수고 이동 가능 → 최단경로에서 이 조건으로 어려워짐. 3. 아이디어 정리 아이디어 1. 벽을 모두 부수면서 모든 경우의 수를 확인 ⇒ 시간 초과 아이디어 2. 벽을 부순 상태와 부수지 않은 상태의 visit 값을 분리하기 벽을 부순 상태와 부수지 않은 상태 분리 visit_0 = [..
-
[Python] 백준 3151 합이 0알고리즘/문제풀이 2021. 7. 17. 21:04
1. 문제 링크 https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 2. 문제 요약 세 팀원 코딩 실력이 0이 되는 경우의 수 구한다. 3. 아이디어 정리 3명인데 투포인터를 진행해야 한다. -> 한 명씩 기준으로 잡고 그 안에서 투 포인터를 진행한다. 1. 합이 0이 되는 경우, left값과 right 값이 같은 경우 해당 범위를 더한다. ⇒ 0이되는 right 학생수 얻어서 더하기 left값과 right 값이 다른 경우 right에 해당되는 점수를 ..
-
[Python] 백준 15565 귀여운 라이언알고리즘/문제풀이 2021. 7. 17. 20:57
1. 문제 링크 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 2. 문제 요약 k개 이상 라이언이 포함된 가장 작은 연속된 인형들의 집합 크기 구하기 ⇒ 투 포인터 3. 아이디어 정리 투 포인터를 이용해서 이동 k개의 라이언이 존재하는 구간에서 결과 저장 left + 1 k개 이하의 라이언이 존재하는 경우, right + 1 4. 문제 풀이 4-1. 내 풀이 import sys n, k = map(int, sys.stdin.readlin..
-
[Python] 스타트 링크 5014 - bfs 그래프 탐색알고리즘/문제풀이 2021. 7. 3. 19:35
1. 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 문제 요약 S > G로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 찾는 문제 → 탐색 문제 3. 아이디어 정리 BFS로 그래프 탐색을 진행하여 최솟값을 찾아본다. S를 큐에 넣어 탐색을 시작한다. 위로 올라가는 경우: 방문을 안 했다면 큐에 넣고, 버튼 누른 수 저장 아래로 내려가는 경우: 방문을 안 했다면 큐에 넣고, 버튼 누른 수 저장 4. 문제 풀이 4-1. 내 풀이 import sys..
-
[Python] 백준 한 줄로 서기 1138 - 구현 문제알고리즘/문제풀이 2021. 7. 3. 19:30
1. 문제 https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 2. 문제 요약 자기보다 큰 사람이 왼쪽에 몇 명인지 알 수 있다. 줄을 선 순서대로 출력한다. 3. 아이디어 정리 키가 작은 학생부터 왼쪽에 나보다 키가 큰 사람 수만큼 자리를 비우고 맞는 순서에 배치한다. 예제 입력을 통해 직접 순서를 구현해보면 아래와 같다. 4. 문제 풀이 4-1. 내 풀이 """ 단순 구현 - 작은 사람부터 차례대로 채우기 """ import sys n ..