본문 바로가기

분류 전체보기52

BOJ3830 교수님은 기다리지 않는다 3830번 교수님은 기다리지 않는다 1번부터 N번까지의 샘플에 대해 두 샘플의 무게 차이 정보가 주어질 때 교수님이 요구한 두 샘플의 무게 차를 구할 수 있으면 출력하고 구할 수 없으면 UNKNOWN을 출력한다 Disjoint Set Union & Find를 이용하는 문제인데 edge에 cost가 있다. 분리집합 문제는 여러 개 풀었었는데 가중치가 있는 건 처음 풀어봐서 꽤 헷갈리고 오래 걸렸다. scanf,printf보다 cin,cout이 훨씬 빠르고 편했다. par[N] N개 샘플의 부모 (set number) w[N] N개 샘플의 set 내 무게 (부모 무게를 0으로 했을 때의 무게) ! a b c : b가 a보다 c그램 무겁다. a와 b를 union한다. 1. a,b의 부모 para,parb를 구.. 2021. 6. 19.
BOJ1949 우수 마을 1949번 우수 마을 N개의 마을로 이루어진 트리 형태의 나라에서 우수 마을인 두 마을이 인접하지 않고 우수 마을이 아닌 마을은 적어도 한 우수 마을과 인접해야 할 때 우수 마을로 선정된 마을 주민 수의 최댓값을 구한다. Tree + DP 2535번과 비슷하다. 다만 2535번에서는 v가 선택될 때/아닐 때 두 가지만 고려하면 됐는데 여기서는 v의 자식노드까지 생각해야 한다. 좀 더 상위버전인 듯. 우수마을을 선정하는 조건을 파악하자 1. 우수 마을인 두 마을이 인접하지 않는다. v가 우수마을이면 v의 모든 자식 노드는 우수 마을이 될 수 없다. 2. 우수마을이 아닌 마을은 적어도 한 우수 마을과 인접하다. v가 우수마을이 아니라면 v의 자식 노드 중 하나가 우수 마을이거나, v의 부모 노드가 우수 마을.. 2021. 6. 10.
DP (1) Dynamic Programming 다이나믹 프로그래밍 BOJ1028 다이아몬드 광산 R*C 크기로 주어진 광산에서 가장 큰 ◇ 모양의 다이아몬드의 크기(한 변의 길이)를 구한다. ↖,↗ 방향으로 연속한 1의 개수를 구하고 다이아몬드의 아래 꼭짓점을 기준으로 최대 다이아몬드 크기를 구한다. dp[ i ][ j ][ 0 ] ( i , j )기준 ↖방향으로 연속한 1의 개수 dp[ i ][ j ][ 1 ] ( i , j )기준 ↗방향으로 "" 이때 아래 꼭짓점이 ( i , j )이고 크기가 k+1인 다이아몬드가 존재하려면 아래 조건을 만족해야 한다. dp[ i ][ j ][ 0 ] > k dp[ i ][ j ][ 1 ] > k dp[ i-k ][ j-k ][ 1 ] > k dp[ i-k ][ j+k ][ 0.. 2021. 6. 10.
그리디 (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.

티스토리툴바