본문 바로가기

분류 전체보기

(234)
[문제해결기법] 11. 동적 계획법 동적 계획법 (DP) 최적화 문제, 분할 정복 한 문제를 똑같은 문제이면서 크기만 작은 것으로 바꿀 수 있을지 생각해본다. 금화 모으기 문제 D[i][j] : (i, j)까지 오는 동안 모을 수 있는 금화의 최댓값 D[i][j] = max( D[i-1],[j] , D[i][j-1] ) + map[i][j]; 최대 공백 정사각형 (흰색으로만 이루어진 가장 큰 정사각형) mm 크기의 정사각형이 있다면, 4개의 (m-1)(m-1) 크기 정사각형이 있어야 한다는 점에서 착안한다. D[x][y]는 (x,y)가 가장 오른쪽 아래 꼭지점인 정사각형의 최대 크기라고 가정한다. (x,y)가 검은색이면, D[x][y] = 0 흰색이면, x==1 && y==1 : D[x][y] = 1 else : D[x][y] = min(..
[문제해결기법] 10. 계산 기하 계산 기하 2, 3차원 공간상에서 점, 선, 도형 간의 관계를 다루는 문제 기본 가정 : 2차원 공간, 정수좌표만 고려함. 실수 연산은 지양 polygon : 선분들로 이뤄진 닫힌 도형. 두 선분이 만나는 점은 하나뿐이다. 모든 점을 지나는 경로 n개의 점이 주어지면, 이 점들을 모두 지나고 시작점으로 돌아오는 경로를 구하시오. 단, 교차하지 않게 풀이 방법 y좌표가 가장 낮은 점을 기준점으로 잡음. O(n) 이 점을 지나는 직선과 다른 점들을 잇는 직선을 모두 구하고, 각의 크기에 따라 정렬한다. O(n log n). 그리고 이 순서대로 방문하면 됨 각의 계산 : arctan 함수와 비슷한 성질을 가지고, 분모가 0인 경우가 없도록 하는 함수를 직접 만들어서 계산한다. 점과 폴리건의 포함 관계 점의 좌..
[문제해결기법] 9. Flow Networks Flow Networks 가중그래프 G (모든 가중치는 양수) 에지의 가중치 = c(e) 시작점 s에는 들어오는 에지 없고, 도착점 t에는 나가는 에지가 없다 Flow : 이용가능한 용량을 기반으로, 간선을 따라 이동하는 값 모든 에지에 대해서, 0 ≤ f(e) ≤ c(e) flow 값 ( |f| )은 s에서 나가는 플로우 총량 = t로 들어오는 플로우 총량 최대 플로우 = 최소 cut 컷(cut) 주어진 노드 V를 두 집합으로 분할 컷 X에 대해서, f(X)는 X를 지나는 flow 총량 c(X)는 X를 지나는 에지의 c값 총량 최대 플로우 구하기 Ford-Fulkerson algorithm s→t 경로를 찾는다. BFS 진행 각 경로의 c(e) 최솟값을 m이라고 하자 각 경로의 에지마다, c(e) -=..
[문제해결기법] 8. 서로소인 집합의 표현 (Disjoint Sets) 서로소인 집합의 표현 (Disjoint Sets) 서로소인 집합 : 전체집합의 부분집합들 중, 둘을 고르면 교집합=공집합, 전체 합집합=U U의 두 원소가 같은 부분집합의 원소인지 아닌지 어떻게 알 수 있을까? 신장트리 : 그래프 G의 노드를 모두 포함하는, E에 속하는 에지로 만든 트리 최소신장트리 : 트리에 속한 가중치의 합이 가장 작은 신장 트리. 최소 신장 트리 (MST) 만들기 Prim’s algorithm : 현재 집합(노드들)과 연결된 에지 중 가중치가 최소인 것을 MST 집합에 포함시킴. 구현법에 따라 시간복잡도가 차이남 다익스트라 알고리즘 = 특정 시작노드부터 다른 노드들까지의 최단거리를 구함. 유/무향 그래프 프림 알고리즘 = 모든 노드들을 최소비용으로 연결 / 두 노드사이의 거리는 최..
2023 교내 해커톤 기획운영팀 활동 후기💙_SO-HOT 해커톤🔥 #0. 교내 해커톤 기획 참여 계기 이전에 교내 해커톤과 교외 해커톤(SW중심대학 해커톤 본선) 경험과 수상 경험이 있었고, 교내 직원분의 제안을 받아 기획운영팀에 참여하게 되었다! 다른 학원생 선배님 한 분이랑 일 잘하는 후배 하나, 이렇게 세명이서 열일 시작함 🔥 (내가 팀장이었음) 교내 해커톤은 본선 진출자를 선발하는 "예선"이다보니 대회의 규모도 작고 이전에는 홍보도 제대로 진행하지 않았는데, 올해는 대회 규모를 늘려서 예선(교내 해커톤)을 학교의 공식 대회로 픽스해버리자는 목적을 가지고 시작했다. #1. 일정 조정 및 스태프 선발 가장 급한게 일정 수립이었다. 첫 회의가 4월 초였고, 해커톤 일정은 늦어도 5월 중순이어야 했으므로 최대한 서둘러서 진행했다. 먼저 기존의 1박 2일 일정이었던 예선..
[C++/PGS] Lv.0 : 옹알이 (1) (구현) https://school.programmers.co.kr/learn/courses/30/lessons/120956 문제 설명 머쓱이는 태어난 지 6개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음을 최대 한 번씩 사용해 조합한(이어 붙인) 발음밖에 하지 못합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ babbling의 길이 ≤ 100 1 ≤ babbling[i]의 길이 ≤ 15 babbling의 각 문자열에서 "aya", "ye", "woo", "ma"는 각각 최대 한 번씩만 등장합니다. 즉, 각 문자열의 가능한 모..
[C++/PGS] Lv.0 : 겹치는 선분의 길이 (구현) https://school.programmers.co.kr/learn/courses/30/lessons/120876 문제 설명 선분 3개가 평행하게 놓여 있습니다. 세 선분의 시작과 끝 좌표가 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를 return 하도록 solution 함수를 완성해보세요. lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다. 선분이 두 개 이상 겹친 곳은 [-2, -1], [0, 1]로 길이 2만큼 겹쳐있습니다. 제한사항 lines의 길이 = 3 lines의 원소의 길이 = 2 모든 선분은 길이가..
[C++/PGS] Lv.0 : 연속된 수의 합 (구현) https://school.programmers.co.kr/learn/courses/30/lessons/120923# 문제 설명 연속된 세 개의 정수를 더해 12가 되는 경우는 3, 4, 5입니다. 두 정수 num과 total이 주어집니다. 연속된 수 num개를 더한 값이 total이 될 때, 정수 배열을 오름차순으로 담아 return하도록 solution함수를 완성해보세요. 제한사항 1 ≤ num ≤ 100 0 ≤ total ≤ 1000 num개의 연속된 수를 더하여 total이 될 수 없는 테스트 케이스는 없습니다. 코딩테스트 입문 문제 중에 정답률이 낮은 문제들 중 하나이다. 테스트케이스에서 규칙을 찾아서 공식화시켜야 한다! 이 예시를 보니 result의 가운데 숫자는 항상 total/num의 값(..

728x90