알고리즘 썸네일형 리스트형 Lv2 문제(간단한거) 1. N개의 최소 공배수 구하기 - a,b의 최소공배수 : a * b // gcd(a,b) 2. [1260] dfs와 bfs (실버2) - bfs는 "함수 시작하자마자, start노드 큐에 넣기 전에3 + 탐색 후 다음 노드 큐에 넣을 때 visited[i] = True로 바꾸기. 큐에서 뽑을 때 true로 바꾸면 중복접근됨 - 두 함수의 결과를 각각 한 줄 단위로 출력하고 싶으면 함수 내에선 print( ~,end = " "), 하고 함수 사이에 print("")넣기 - 맨 처음에 d_visited = b_visited = [False] * (N+1)로 했더니 둘이 같은 메모리 공간을 공유함! 즉 이름만 다르고 같은 배열처럼 됨!! 다른 문제 풀 때도 조심할 것 !!!1 - 헷갈리는 것 : 변수는 a=.. 더보기 (kakao) 메뉴 리뉴얼(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 2. 구현 과정 1) 메뉴 개수를 나타내는 course값이 10 이하이고, 각 단품 메뉴를 나타내는 알파벳이 26개이다. 코스 요리의 메뉴 개수가 2개라 하면, 가능한 경우의 수는 26C2이고, 3개라 하면 가능한 경우의 수는 26C3이다. => 26C1, 26C2, 26C3, 26C4,.... 26C10 2) 26C1 + 26C2 + 26C3 + .... 더보기 [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만큼의 떡을 얻기위해 설정할 수 있는 높이의.. 더보기 이전 1 2 3 4 5 ··· 7 다음
