Probelm Solving/Notes10 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. 그리디 (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. 그래프 (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. KMP DP 트리 그래프 기하학 최근 푼 문제 1701 Cubeditor KMP idx(0~N-1)부터 N까지의 부분문자열에 대해 Pi를 구한다. idx에 대하여 최대 Pi값 - idx = 두 번 이상 나오는 가장 긴 부분문자열의 길이 * Pi를 구하는 시작점의 인덱스가 0이 아님에 주의해서 풀면 됨 16900 이름 정하기 KMP 주어진 문자열 S가 최소 K번 부분문자열로 등장하는 새로운 문자열 길이의 최솟값을 구한다. Pi를 구해 문자열 S에서 K-1번 반복해줄 부분 문자열을 구한다. 아래는 예시 S ada 3 pi 001 => (3-2)+2*3 S abc 2 pi 000 => (3-3)+3*2 S rr 5 pi 01 => (2-1)+1*5 S abcabcabca 3 pi 0001231234 => (10-3)+3*3 1509 팰린드롬 분할 DP 주.. 2021. 4. 16. 구현 (2) 지난 주 푼 문제 10253 헨리 구현 수학 써져있는 대로 구현하기만 하면 되는 문제. 5577 RBY팡! 구현 시뮬레이션 나 진짜 멍청했던게 RRRBRR 처럼 가운데에 하나 낀 애들만 색깔 바꿀 생각해서 계속 틀렸었다. 그래서 RRRBB있으면 하나도 팡! 안했었음 ㅋㅎㅋ RRRRBB로 바꿔서 팡 할 수 있는데,,, 한 이틀 뒤에 깨달았다.. 한 번 막힌 사고는 다시 흐르기가 참 어렵다.. 14601 샤워실 바닥 깔기 (Large) 분할정복 구현 처음에는 대칭성을 이용해 풀려고 했는데,,, 너무 복잡해졌고 ㄱ자 모양은 정사각형에서 한 칸 뺀 거라는 사실을 이용해서 생각해내야 했다. 사분할한 각 정사각형이 모두 비어있을 때만 꼭짓점을 채워 ㄱ을 만드는 형식을 반복하면 된다. 솔직히 너무 씽크빅이었지만 이런 것도 풀 줄 아는.. 2021. 4. 5. 그래프 (1) 최근 푼 문제 아니,,블로그 정리를 어떻게 해야할지 모르겠다. 15559 내 선물을 받아줘 15886 내 선물을 받아줘2 2536 버스 갈아타기 5214 환승 15559 내 선물을 받아줘 → union find (Disjoint Set) 15886 내 선물을 받아줘2 → 문자열 내 EW의 개수 2536 버스 갈아타기 → BFS 가로/세로로 움직이는 버스를 나누어 갈아탈 수 있는 버스를 찾아내는 방법을 생각해낼 것 bfs 더보기 ver[N] ver[ i ] = x=i에서 세로로 움직이는 버스들 저장 hor[N] hor[ i ] = y=i에서 가로로 움직이는 버스들 저장 vis[N] vis[ i ] = i번째 버스를 타기까지 갈아탄 최소 횟수 int bfs() { // STEP 1. 시작점을 포함하는 버스 for (inf.. 2021. 3. 15. 기하학 (2) 계산 문제들 1207번 고층건물 - 기울기16190번 Rising Sun - 좌표, 기울기16115번 팬이에요 - 삼각함수1798번 원뿔좌표계상의 거리 - 좌표, 삼각함수1207번 고층 건물같은 간격으로 떨어져 있는 건물의 높이가 정수로 주어질 때각 건물의 옥상에서 보이는 다른 건물의 개수 중 최댓값 출력현재 건물과 보려고 하는 건물의 옥상을 이은 선분에 다른 건물이 교차하거나 만나면 안 된다. 즉, 현재 건물의 옥상을 점 A라 하고현재 건물에서 볼 수 있는 건물의 옥상을 왼쪽에서 오른쪽 순서로 각각 점 B1, B2, ...라 하면선분 AB1, AB2, ...의 기울기가 순서대로 증가해야 함 기울기가 같으면 안 됨. 8에서는 7만 보이고 6은 볼 수 없다. 높이가 극댓값인 건물만 보면 틀린다.낮은 건물에서 다른 건물.. 2021. 3. 15. 구현 (1) 18809번 Gaaaaaaaaaarden BFS BF 그래프 구현 시뮬레이션 14865번 곡선 자르기 구현 3954번 Brainf**k 인터프리터 자료구조 구현 스택 3678번 카탄의 개척자 구현 시뮬레이션 17472번 다리 만들기 2 BFS BF 그래프 구현 MST 16637번 괄호 추가하기 BF 17135번 캐슬 디펜스 BFS BF 그래프 구현 시뮬레이션 17406번 배열 돌리기 4 BF 구현 진짜 나는 좌표가 너무 헷갈린다. 공간지각능력이 좋은 사람은 아니라... 시각화가 너무나 중요하다. 과연 이 필기를 다시 꺼내볼 일이 있을 것인지,, 2021. 1. 29. 기하학 (1) 고등수학 재밌다. 더보기고민을 안하고 풀어도 됨 바깥 삼각형의 중심 벡터 열심히 계산해서 연립방정식 풀면 된다 너무 재밌따. 피자 배치 닮음비 계산하고 지수 늘려주면서 K번째 피자를 찾는다. 외계인의 침투 모의고사 18번 문제 느낌임 아니면 26번,, 대충 먼말인지 알지 Cows 다각형은 삼각형으로 나눌 수 있다. 삼각형의 넓이는 K-고등수학을 배웠다면 구할 수 있다. 여기선 다만 점을 정렬해줘야 하는데 이때 컨벡스헐 개념이 필요했던 것 같네컨벡스헐 솔직히 아직 완벽히 알지 못하는 상태라 다음에 정리해줘야겠다. 2021. 1. 19. 이전 1 다음