본문 바로가기

전체 글

[12847] 꿀 아르바이트(python) 1. 문제 https://www.acmicpc.net/problem/12847 12847번: 꿀 아르바이트 월세를 내기 바로 전 날 까지 인 n (0 < n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다. 그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000) www.acmicpc.net 2. 구현 과정 - 시간 제약이 1초이므로, O(N^2)만 되어도 안된다. N의 범위가 10만이므로, 최대 NlogN으로 풀어야 한다. - 누적합 함수인 accumulate를 사용해서 dp형식으로 푸는 방법과 투 포인터를 사용하는 방식 두 가지 방식으로 풀 수 있다. 개인적으로 투 포인터 문제는 익숙치 않아서, 후자 푸는 연습을 .. 더보기
[4485] 녹색 옷 입은 애가 젤다지?(python) 1. 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 2. 풀이 과정 - (0,0) 에서 (N-1,N-1)까지 갈 때 최소 루피(비용)을 출력하는 문제 - 처음엔 다익스트라로 풀려 했는데, BFS로 풀게 되었다. - 다익스트라는 "간선의 길이"가 중요한 문제, 즉 A번 -> C번 노드로 가는데 걸리는 "간선"의 비용이 어느정도인지가 주어지면 푸는 문제인데 해당 문제는 간선의 비용이 아니라 "특정 노드"에 도착했을 때 무조.. 더보기
최단 경로 1. 다익스트라 알고리즘 - 특정 노드 -> 다른 모든 노드를 가는 최단 경로를 구함 - '음의 간선'이 없을 때 사용 가능 (GPS SW 기본 알고리즘으로 사용) - 그리디 알고리즘 - 출발 노드를 설정한 후, 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택해가는 알고리즘 - 입력 시 sys.std.realine()으로 사용하는 것 추천! - 헷갈리지 말 것 : dist를 갱신하는 거랑 노드를 선택하는 과정을 별개로 생각하기! * 간단하지만 오래 걸리는 구현 방식 #DFS로 구현 #리스트 : 노드 개수 + 1 import sys input = sys.stdin.readline INF = int(le9) #무한대.10억 #입력받기 N,M = map(int,input().split() #노드개수.. 더보기
[Lv2] 뉴스 클러스터링(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/17677?language=python3 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 2. 풀이 과정 - 다른 분들의 풀이를 참고하여 푼 문제. 다중 집합의 개념을 알게 되었다! - 기존 집합 관련 문제는 set을 쓰기만 하면 되었었는데, 이번 문제는 set 자료구조의 기본 함수만을 사용할 수 없었기 때문에 버벅거렸다. set의 기본 구현 방식도 익혀야 할 것 같다! 3. 실수 한 것.. 더보기
DP 1. DP로 풀 수 있는 문제 조건 - 큰 문제를 작은 문제로 나눌 수 있다. - 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 2. 메모리제이션 - DP 구현 방법 중 하나. 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 저장한 결과를 가져오는 기법 ( caching 기법이라고도 함) - 이전에 계산된 결과를 일시적으로 기록하는 개념 - top-down방식에 사용되는 기법 ( 재귀함수를 사용하여 큰 문제를 해결하기 위해 작은 문제를 호출) 3. top-down / bottom-up - top-down : 재귀 함수 호출 - bottom-up : 반복문을 사용하여 작은 문제부터 값을 구해가는 방식. 이 때 결과를 저장하는 리스트를 dp 테이블이라 함 4. DP임을.. 더보기
[이것이코딩테스트] 떡볶이 떡 만들기 1. 문제 - 각 길이가 일정하지 않은 떡들을 자르기 위해, 절단기에 높이 H를 지정하면 줄지어진 떡들이 한번에 절단된다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 손님은 H 위 부분의 길이만큼 가져간다. 손님이 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하라 - 첫째 줄에 떡의 개수 N과 요청한 떡 길이 M이 주어지고, 둘째 줄에서는 떡의 개별 높이가 주어진다. ( N은 100만 이하, M은 20억 이하, H는 10억 이하) 2. 풀이 과정 - 읽다가 떡볶이 시킨 문제이다 - 구해야 할 것 : 최소 M만큼의 떡을 얻기 위해 필요한 절단기의 최대 높이 - 적어도 M만큼의 떡을 얻기위해 설정할 수 있는 높이의.. 더보기
[Lv2] 캐시(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/17680 도시들 간 순서가 있어야 함 & 자료구조의 사이즈를 알아야 함 - 초기 접근 방식 딕셔너리를 사용해서 key - 도시 이름, value - 해당 도시가 들어왔던 직전 순서를 저장. i번째 도시를 찾으려고 할 때, 이미 이전에 값이 들어온 적이 있으면 해당 value 값을 보고 value >= i - cacheSize + 1이면 cache hit으로 봤음 - 초기 접근 방식의 반례 cacheSize = 3, A B B B A 라 하면 , 마지막 A를 찾을 때 cache[A] = 0이 되어서 원래는 cache hit임에도 cache miss로 판정됨 => " 절대적인 순서가 필요한 게 아니라 캐시.. 더보기
[Lv2] 짝지어 제거하기(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12973?language=python3 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 2. 풀이 과정 - stack을 사용해서 stack의 top 문자와 s[i]가 같으면 stack.pop()하고 아니면 stack.append()를 해가다가 최종 stack이 빈 stack이면 1을 리턴. - "붙어있어야 한다 + 붙어있는게 사라졌을 때, 새로운 짝이 생긴다 (b aa b -> bb) " -> .. 더보기

티스토리툴바