HOME

[C++ 알고리즘] 백준 21609번 : 상어 중학교

Implementation BFS 상어 중학교 풀이과정 상어 초등학교 문제와 마찬가지로 우선순위 큐를 이용해 구현하였다. 1. 크기가 가장 큰 블록 찾기(BFS) -> find_block() 2. 중력 적용 -> down() 3. 90도 반시계 방향 회전 -> rotate() 4. 중력 적용 -> down() 위의 문제 요구사항대로 차근차근 구현만 해주면 쉽게 끝난다. 여기서 헷갈릴만한 부분은 크게 두 가지가 있는 것 같다. (1) BFS시 무지개 블록 방문 처...

더보기

[C++ 알고리즘] 백준 21608번 : 상어 초등학교

Implementation 상어 초등학교 풀이과정 우선순위큐를 이용해서 구현하였다. 순서대로 학생의 자리 정하기 만족도 구하기 를 구현만 해주면 끝난다! 가장 핵심적인 부분은 우선순위큐를 작성하는 부분인 것 같다. 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다. 위의 요구대로 아래와 같이 코드...

더보기

[C++ 알고리즘] 백준 10942번 : 팰린드롬?

DP 팰린드롬? 풀이과정 1. 알고리즘 선택 문제를 보자마자 떠올렸던 풀이방법의 시간복잡도를 계산해보았다. s,e를 입력받을 때 마다 s~e까지 검사하며 팰린드롬 여부를 확인하는 방법 이 방법은 1 ≤ N ≤ 2,000 이고, 1 ≤ M ≤ 1,000,000 이므로 최악의 경우 2,000* 1,000,000 = 2,000,000,000 (20억번)의 연산 횟수가 발생한다. 따라서 시간복잡도를 줄일 수 있는 방법이 필요했고, 일단 DP 같은데 조건을 어떻게 세워야할 지 몰라서 테스트케이스를 보면서 규칙을 찾았다. 2. 규칙 찾기 palindrom[s][e] = s~e 까지 수의 팰린...

더보기

[C++ 알고리즘] 2021 KAKAO : 합승 택시 요금

Dijkstra Floyd–Warshall 합승 택시 요금 풀이과정 백준의 특정한 최단 경로 문제와 비슷하다고 느꼈다. 다익스트라랑 플로이드-와샬 두 가지 방법으로 풀어보았는데, 플로이드-와샬이 더 효율이 좋았다. 모든 정점에서 모든 정점까지의 최단 거리를 구할 때는 플로이드-와샬, 한 정점에서 다른 정점까지의 최단 거리를 구할 때는 다익스트라를 사용하는 것이 맞는 것 같다. 복잡도 다익스트라 플로이드-와샬 시간복잡도 인접행렬 : \(O(V^2)\)인접리스트 + 우선순위 큐 : \(O(E log V) ...

더보기

[C++ 알고리즘] 프로그래머스 : 조이 스틱

Greedy 조이 스틱 풀이과정 알파벳 위 아래로 조작하는 건 알겠고, 단순히 오른쪽으로 쭉 이동하거나 왼쪽에서 쭉 이동하는 것만 비교해서 제출했더니 11번 테케에서 오류나서 구글링의 힘을 빌렸다.. 간단한 건데도 이해하기 힘들어서 직접 써서 증명하면서 풀었다 ㅠㅠ 그리디 넘 어려웡 name[i]에서 가장 가까운 A가 아닌 문자 name[ind] 찾기 여기서 조이스틱을 움직이는 최단 경로는 (1) 원점 –> i –> 원점 –> ind (2) 원점 –> ind –> 원점 –> i 이렇게 두 가지이다. 따라서 (i : 0~name.lengt...

더보기

[Design Pattern] MVC, MVP, MVVM 패턴이란?

MVC(Model-View-Controller) 구성요소 Model : 프로그램에서 사용되는 데이터, 데이터를 처리하는 로직을 담당 View : 사용자가 보는 부분, 데이터가 보여지는 UI Controller : 사용자의 입력을 받고 처리 구조 동작 방식 사용자의 입력이 Controller에 들어옴 Controller는 사용자의 입력을 확인한 후 Model을 업데이트함 Model은 보여줄 View 선택 View는 변경된 Model을 이용해 사용자에게 보여줄 UI 업데이트 특징 Controller와 View는 1:N 관계를 가진다. 장점 보편적이며, 단...

더보기

[C++ 알고리즘] 백준 1865번 : 웜홀

벨만포드 웜홀 풀이과정 벨만-포드 알고리즘을 이용해 해결하였다. 시간이 줄어들면서 출발 위치로 돌아오는 것 을 보고 벨만포드를 떠올리기 도로는 무방향이므로 양방향 간선 2개를 추가하기 웜홀의 가중치는 음수로 취급하기 이 세가지는 캐치했지만 놓친 부분이 있었다. (1) 모든 정점에서 음의 사이클의 여부를 판단하였다. vector<vector<int>> dist(n + 1, vector<int>(n + 1, MAX)); for (int k = 1; k <= n; k++) { dist[k][k] = 0; ... } 대략 이런식으로 ...

더보기

[C++ 알고리즘] 2021 KAKAO : 메뉴 리뉴얼

DFS Brute Force 메뉴 리뉴얼 풀이과정 내가 수행한 전체 Process는 다음과 같다. 메뉴 조합 구하기 요리 n개의 코스 중 가장 많이 주문된 것들 구하기 answer에 추가 후 정렬 1번은 손님들이 주문한 전체 메뉴들 중 DFS를 이용해 nCm의 조합을 구했다. 코스(조합)를 구한 후에는 각 코스가 손님들에게서 주문된 적 있는지 검사 후 최댓값을 추출하였다. 풀면서 BOJ 복면산 문제가 생각이 나서 비슷하게 풀었는데, 다른 풀이를 보니 나는 너무 복잡하게 푼 것 같다 ㅠㅅㅠ.. map을 이용해서 풀 수도 있고 전역변수를 쓸데없이 많이 선언하지 않고 매개변수에 strin...

더보기