본문 바로가기

stack3

그리디 (2) BOJ17420 깊콘이 넘쳐흘러 '특정일에 사용하기로 정한 기프티콘'이 '기한이 가장 적게 남은 기프티콘'이여야만 사용할 수 있을 때, 한 번 연장할 때 30일씩 연장되는 기프티콘을 모두 사용하기 위한 최소 연장 횟수를 구한다. 1. 계획한 사용일자가 적게 남은 순으로 기프티콘 정렬 2. 정렬된 기프티콘의 사용 기한이 증가수열이 되도록 연장 2-1. 이때 사용일자가 같은 기프티콘이 있음에 주의 BOJ1898 이전 수열은 어떤 수열일까 1부터 N까지의 수를 나열한 수열 {Sn}이 주어질 때 모든 i(1≤i≤N)에 대해 | Si-Ai | < 2 인 수열 중 오름차순으로 나열할 때 가장 앞에 오는 수열 {An}을 찾는다. N=8일 때, 4자리에는 3,4,5,가 배치될 수 있지만 8자리에는 7,8만 배치할 수 .. 2021. 5. 31.
2020 카카오 인턴십 문제 ① 2020 카카오 인턴십 문제 #1 키패드 누르기 조건을 헷갈리지 않고 구현하면 됨 각 숫자의 위치를 저장해두고 문자열을 구했다. 더보기 /* 1 2 3 1,4,7 => L n=0일 때 주의 4 5 6 3,6,9 => R 7 8 9 else => rdist,ldist 계산, hand 고려 * 0 # */ string solution(vector numbers, string hand) { string answer = ""; int pos[12][2]; pos[0][0]=3, pos[0][1]=1; pos[10][0]=3, pos[10][1]=0; pos[11][0]=3, pos[11][1]=2; int num=1; for(int r=0;r tmp) ? answer : tmp; } return answer; .. 2021. 5. 2.
SCC SCC : 강한 연결 요소 strongly connected components 그래프 내 vertex 중 서로 간의 경로가 양방향 모두 존재하는 vertex들의 집합 X⊂G s.t. ∀a, b∈X, ∃ paths both a→b, b→a DFS와 스택이 핵심이다. 방문 지점의 order(몇 번째로 방문했는지)를 이용한다. DFS함수의 리턴 값은 현재 노드에서 도달할 수 있는 지점 중 가장 먼저 방문한 지점의 방문 순서이다. DFS(cur) = par = cur에서 도달할 수 있는 지점의 ord 중 최솟값 ord[v] v 방문 순서 fin[v] v 방문 완료 여부 = v가 속하는 SCC를 찾았는지? 현재 방문한 지점을 cur, 다음에 방문할 지점을 nxt라 하자. nxt는 다음 세 가지 경우 중 하나에 .. 2021. 4. 13.

티스토리툴바