2JINISHAPPY 2JINISHAPPY

www.acmicpc.net/problem/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net www.acmicpc.net/problem/20182 20182번: 골목 대장 호석 - 효율성 1 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net www.acmicpc.net/problem/..

www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 오랜만에 풀어보는 투포인터 문제! 투포인터는 보통 최적의 해를 갖는 특정 구간을 찾아내는 문제에서 많이 사용한다 이 문제는 중복되지 않는 원소의 개수를 최대로 하는 k개의 연속된 구간을 찾아내는 문제이당 (+쿠폰 사용을 위해 쿠폰 번호 element 또한 포함되어 있는지 확인) 예제에서는 그림과 같이 [2, 7, 9, 25]에 보너스로 30까지 포함한 5가 정답이 된..

www.acmicpc.net/problem/17951 17951번: 흩날리는 시험지 속에서 내 평점이 느껴진거야 시험지를 12, 7, 19, 20과 17, 14, 9, 10 으로 나누면 맞은 문제 개수의 합의 최소는 50이다. www.acmicpc.net 스터디할 때 풀었던 문제인데 왜 답이 right일까?를 고민하다가 이제 이유를 알아냈다 이진탐색 및 매개변수 탐색의 진행에는 loop-invarient라는 성질이 적용된다. loop를 지속하게 하는 절대적인 조건이므로, loop가 시작되기 전 & loop 중 & loop 이후에도 정해진 loop-invarient는 유지되어야 한다. 이 문제(parametric search)에서는 parameter를 "각각의 그룹에 속한 시험지 점수의 합 S 중 최소값을..

programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 작년 카카오 공채 기출문제 출발지 S에서 목적지 A, B로 가는 최단거리를 계산하는 문제 라서 다..

www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 내가 기존에 못 하던 유형인 DP, 이진탐색을 연습할 필요성을 느껴서 간간히 풀어보려고 한다 대표적인 문제인 나무자르기 사실 옛날에는 봐도 감이 안 와서 몇번을 풀려고 트라이했지만 실패했었는데 스터디에 이진탐색 빡고수분의 지도를 몇 번 받아 이제 감이 슬슬 오고있따 이진탐색 문제는 left, right 변수를 설정하는 것이 가장 핵심인 것 같다. 처음부터 이진탐색 솔루션이..

www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 주어진 알파벳 string의 해석 경우의 수를 구하는 DP문제 수를 한 자리, 두 자리 씩 끊을 때 나올 수 없는 숫자의 범위가 있기 때문에 그 경우를 고려해주어야 한다. -2만큼 이전에 있는 인덱스를 참조하기 때문에 base case를 위해 앞에 dummy string을 추가해주었다. #include #include #define MOD 1000000 using namespace std; string str; int dp[50..

www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 스터디 문제 풀이용으로 급하게 서치한 문제인데 굉장히 유익한 것 같아서 포스팅 로봇의 시작 좌표 S가 주어지고, 열쇠의 좌표 K(여러 개)가 주어졌을 떄 모든 열쇠를 얻을 수 있는 최단거리 이동 경로를 구해야 한다. 이 때, 이동 경로에는 가중치가 없고(BFS를 이용한 최단거리 계산) 열쇠가 복사가 가능하기 때문(S에서만 K를 도달할 수 있는게 아닌, K에서 다른 K로도 이동 가능..

programmers.co.kr/learn/courses/30/lessons/17686# 코딩테스트 연습 - [3차] 파일명 정렬 파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램 programmers.co.kr 이때까지 외워서 사용했던 정렬 comparator에 대해 생각하게 해주는 문제 카카오 2018년 기출은 풀면서 배워가는게 많은 것 같다 파일명 정렬에서는 파일 이름 string을 HEAD, NUMBER, TAIL 세 파트로 나눈 뒤 각각의 order에 따라 정렬을 해주어야 한다. 문자열 토큰화가 크게 복잡하지 않았기 때문에 C++로 풀이했다. 처음 설계했던 풀이 ..