본문 바로가기

Probelm Solving42

그리디 (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.
BOJ1014 컨닝 1014번 컨닝 N*M크기의 직사각형 교실에서 컨닝을 방지하도록 앉힐 수 있는 최대 학생 수를 구한다. 현재 위치를 기준으로 동일 행의 좌우(←→), 윗 행 좌우 대각선(↖↗) 위치의 답지를 베낄 수 있다. 비트마스킹 + DP 학생이 앉은 상태, 앉을 수 없는 자리 등을 bit로 표현하고 i행에서 k의 상태로 앉을 수 있는 학생 수의 최댓값을 i-1행을 고려해 구한다. * 3줄 요약 cnt[ k ] 행의 상태가 k일 때 해당 행에 앉는 학생의 수 (= k를 이진수로 나타낼 때 1의 개수) dp[ i ][ k ] i행에 k의 상태로 앉을 때의 최대 학생 수 dp[ i ][ k ] = dp[ i-1 ][ up ] + cnt[ k ] (up은 i행의 상태가 k일 때 i-1의 상태로 가능한 것 중 dp값이 가장.. 2021. 5. 19.
2020 카카오 인턴십 문제 ② 2020 카카오 인턴십 #4 보석 쇼핑 map과 two pointer을 사용해 푸는 문제 i부터 j까지 구간에 모든 보석을 가지고 있는가를 판단할 때 map을 사용, 아니라면 j, 맞다면 i를 증가하여 왼쪽에서 오른쪽으로 이동하며 가장 짧은 구간을 구한다. 처음엔 구간 길이에 대한 이분탐색으로 접근했다. 시간초과 났음 더보기 비슷한 문제를 다른 코테에서 본 적 있다. 이 문제의 2차원 버전이었는데,,, 아쉽다 map M; vector solution(vector gems) { vector answer; int N=gems.size(); // Gems for(string g:gems){ auto iter=M.find(g); if(iter==M.end()) M.insert({g,0}); } int G=M.s.. 2021. 5. 10.
2019 카카오 개발자 겨울 인턴십 문제 ② 2019 카카오 개발자 겨울 인턴십 #4 징검다리 건너기 오래 고민하고 겨우 푼 다음 정확성 효율성 다 발리고 질문하기 참고해 이분탐색임을 깨달음...... 아효 이렇게 간단히 풀리는 것을 더보기 무려 스택을 이용해 풀어봤지만 효율성은 둘째치고 정확성이 해결되지 않앗음 흠 int l=1, r=INF; int mid=(l+r+1)>>1, cnt=0; while(l=mid) cnt=0; else { cnt++; if(cnt>=k) { ava=false; break; } } } if(ava) l=mid; else r=mid-1; mid=(l+r+1)>>1; } answer=mid; #5 호텔 방 배정 disjoint set으로 풀었는데 수의 범위때문에 hash한 번 해줬다. 처음엔 새로운 숫자에 대해 {인덱스.. 2021. 5. 5.
그리디 (1) BOJ14501 퇴사 N일간 잡힌 각 상담의 기간과 금액이 주어질 때 N일동안 상담으로 벌 수 있는 금액의 최댓값을 찾는다. 냅색 문제 같은 건데 N≤15라 단순히 시작/종료 시간 기준으로 최대 금액을 계산해 N²로 해결하면 된다. BOJ12904 A와 B A와 B로만 이루어진 문자열 S와 T가 주어질 때 S를 T로 바꿀 수 있는지의 여부를 구한다. 문자열 뒤에 A를 추가하거나, 문자열을 뒤집고 B를 추가하는 연산만 할 수 있다. 문자가 추가되는 위치는 A,B 관계없이 문자열의 가장 끝이므로 S→T로 생각하지 말고 T→S로 생각한다. BOJ8980 택배 N개의 마을과 마을 간 배송할 박스 정보 M개가 주어질 때 앞으로만 운행할 수 있고 용량이 C인 트럭으로 가장 많이 배송할 수 있는 박스 개수를 구한다... 2021. 5. 3.
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.
그래프 (2) 문제들 2593 Elevator BFS DP N층짜리 건물에서 주어진 수열의 층에서만 멈추는 엘레베이터가 M대 있을 때 A층에서 B층까지 가기 위해 최소한으로 갈아타는 엘레베이터의 수 & 내렸던 층을 구한다. 트래킹때문에 좀 복잡했던 문제같음.. 더보기 현재 층 curf에서 탈 수 있는 엘레베이터 cure cure에서 내릴 수 있는 다음 층 nxtf nxtf가 B와 같다면 종료 다르다면 nxtf를 큐에 넣고 다음 엘레베이터 nxte로 갈아타며 dp를 업데이트 // Initiate for (int e : f[A]) dp[A][e] = { 1,0 }; Q.push(A); // BFS and Get Ans bool arrived_at_B = false; while (!Q.empty()) { arrived_at_B =.. 2021. 4. 26.
BOJ3716 도로 네트워크 3716번 도로 네트워크 1부터 N까지의 도시를 연결하는 N-1개의 도로가 주어지고 서로 다른 두 도시 D, E가 주어지면 D와 E를 연결하는 도로 중 가장 짧은 것의 길이와 긴 것의 길이를 구한다. 이때 모든 서로 다른 두 도시간 경로는 한 개만 존재한다. ⇒ 주어진 그래프가 트리이다. LCA문제임은 빠르게 파악할 수 있었다. 다만 공통조상뿐 아니라 공통조상까지의 도로의 길이 중 최댓값/최솟값도 알아야 했고 여기저기 헷갈린 탓인지 여러 차례 틀려서 힘들었다ㅠ 1. Get P 먼저 각 도시의 1, 2, 4, 8, ...번째 조상을 조사한다. 1을 root로 하여 BFS로 탐색하고, 조상을 탐색하며 도로 길이의 최소/최대를 구한다. P[ i ][ k ] r = 도시 i의 $2^{\mathrm{k}}$번째 .. 2021. 4. 23.
BOJ1086 박성원 1086 박성원 길이 50 이하의 자연수가 N(≤15)개 주어질 때 주어진 모든 자연수를 한 번씩 사용하여 이어 붙여 만든 자연수가 100이하의 자연수 K로 나누어 떨어질 확률을 구한다. example. (A) N=3 K=27 { 104, 4, 90 } 104490 104904 410490 490104 901044 904104 여섯 개 중 세 개만 나누어 떨어지므로 1/2 출력 (B) N=3 K=13 { 12, 2, 2 } 1222 1222 2122 2212 2122 2212 여섯 개 중 두 개만 나누어 떨어지므로 1/3 출력 * s[0]="12", s[1]="2", s[2]="2"일 때, s[0]+s[1]+s[2]="1222"와 s[0]+s[2]+s[1]="1222"를 모두 세야 한다. (순열 방식이 .. 2021. 4. 21.
Euler phi function 오일러 피 함수 Euler phi function 오일러 피 함수 $\varphi \left ( n \right )$ = $n$ 이하 자연수 중 $n$ 과 서로소인 수의 개수 소수 $p$와 자연수 $a$에 대하여 다음을 만족한다. $\varphi \left ( p \right )=p-1$ $\varphi \left ( p^a \right )=p^a-p^{a-1}={p^a} \left ( 1-\frac{1}{p} \right ) $ 또한 $\left ( m,n \right )=1$ 인 두 자연수 $m$, $n$에 대하여 $\varphi \left ( mn \right )=\varphi \left ( m \right ) \varphi \left ( n \right ) $ 따라서 소수 $p$, $q$와 자연수 $a$, $b$.. 2021. 4. 16.

티스토리툴바