알고리즘

문제 풀이 DP와 그래프 탐색으로 풀 수 있다. 코드 그래프 탐색 #include #include #define VER 0 #define HOR 1 #define DIA 2 using namespace std; typedef struct { int x; int y; int dir; }type; // 파이프의 방향에 따른 이동 위치 vector move_x = { {0, -1, 1}, {-1, 1, 1}, {0, 1, 1} }; vector move_y = { {1, -1, 1}, {-1, 0, 1}, {1, 0, 1} }; // 파이프의 방향과 이동 위치에 따른 검사 위치 int check_x[3] = { 1, 1, 0 }; int check_y[3] = { 0 ,1, 1 }; //vector check..

문제 풀이 일반적인 다이나믹 프로그래밍으로 해결하려고 하면 메모리 초과 위의 식을 이용하여 피보나치 수열을 행렬의 거듭제곱으로 계산할 수 있다. 분할 정복을 이용한 거듭제곱으로 해결한다. 코드 #include #include #include using namespace std; #define MOD 1000000007 map cache; vector matrix = { {1, 1}, {1, 0} }; vector mulMatrix(vector m1, vector m2) { vector outM = { {0, 0}, {0, 0} }; outM[0][0] = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % MOD; outM[0][1] = (m1[0][0] * m2[0][1]..

문제 풀이 스택을 이용한다. 피연산자는 바로 answer의 뒤에 추가한다. 연산자는 다음으로 처리된다. 스택이 비어있다면 스택에 연산자를 push한다. 연산자는 스택의 top과 우선순위를 비교하여 자신보다 우선순위가 낮을 때까지 top을 answer의 뒤에 추가하고 스택을 pop한다. 그 후, 스택에 자신을 push한다. ' ( '는 바로 스택에 push한다. ' ) '는 스택에서 ' ( '가 나올때까지 top을 answer의 뒤에 추가하고 스택을 pop한다. 그 후, ' ( '를 스택에서 삭제한다. 코드 #include #include #include #include #include using namespace std; // 연산자 우선순위 unordered_map priority = { {'(', 0..

문제 풀이 다익스트라 알고리즘을 사용한다. 학생의 수 N만큼 각각의 학생이 X까지 가는 소요시간을 다익스트라로 계산하는 방법 혹은 역방향 간선을 사용하여 X까지의 소요시간이 최대인 학생을 찾는 방법 역방향 간선을 이용하는 방법은 2번만 다익스트라를 계산하면 되기에 속도차이가 크다. 코드 #include #include #include #include using namespace std; vector edges; vector reverse_edges; vector dists; vector reverse_dists; void dijkstra(int start) { dists[start][start] = 0; priority_queue q; q.push(make_pair(0, start)); while (!q..

문제 풀이 도연이의 위치에서부터 BFS를 실시하여 검사하는 자리가 P라면 결과값에 1을 추가한다. 코드 #include #include using namespace std; typedef struct { int x; int y; }type; queue bfs; char ground[601][601]; bool visited[601][601]; int main() { int N; int M; int result = 0; cin >> N >> M; for (int i = 0; i > ground[i][j]; if (ground[i][j] == 'I') { // 도연이의 위치를 큐에 저장 bfs.push({ i, j }); v..

문제 풀이 N이 100000으로 하나하나 비교하면 시간초과 MBTI의 종류는 16가지로 서로 최대한 MBTI가 다르도록 배치한다면 N이 16일 때, 모두가 다른 MBTI를 가진다. N이 16을 초과한 경우에 최대한 MBTI가 다르도록 배치한다면 2명은 같은 MBTI를 가진다. 같은 원리로 N이 32를 초과한 경우에 최대한 MBTI르 다르도록 배치한다면 3명은 같은 MBTI를 가지므로 N이 32를 초과한다면 결과는 0이 된다. N이 32이하인 경우는 탐색이 필요하다. 코드 #include #include #include #include using namespace std; vector MBTIs; vector mini_MBTIs; int mini = INT_MAX; // MBTI가 다른 자리마다 +1 in..