알고리즘
-
[백준] 2 x n 타일링알고리즘/백준 2021. 8. 13. 18:54
문제 링크 풀이 동적 계획법은 d[n]을 정의하고 그에 맞는 점화식을 세우는 것이 중요합니다. 점화식은 수열에서 이웃하는 두 개의 항 사이의 관계를 나타는 관계식입니다. 조금 더 쉽게 말하면 n번째 항의 값을 구하려면 n-1번째 항의 값을 알아야 합니다. n-1번째 항의 값을 알려면 n-2항의 값을 알아야 합니다. 이렇게 가다 보면 첫 번째 항을 알고 있다면 두 번째 항의 값을, 세 번째 항의 값을 알 수 있습니다. 때문에 초기값을 정의하고 항 사이의 관계식을 만들면 점화식이 완성됩니다. 출처 https://ko.wikipedia.org/wiki/%EC%A0%90%ED%99%94%EC%8B%9D https://blog.naver.com/ao9364/221651296608?viewType=pc 이 문제에서..
-
[백준] 피보나치 함수알고리즘/백준 2021. 8. 10. 16:51
문제 링크 풀이 0, 1의 갯수에 대한 규칙만 찾으면 된다. f(0) -> 1, 0 f(1) -> 0, 1 f(2) -> 1, 1 f(3) -> 1, 2 f(4) -> 2, 3 f(5) -> 3, 5 각 항목도 피보나치 수열처럼 n번째 값은 [n-2] + [n-1]이다. 조금 더 자세히 보면 0의 갯수는 직전 항목의 1의 갯수와 같다. 그러므로 1의 횟수를 기준으로 점화식을 만들고 값을 설정해놓으면 된다. 코드 #include int main() { int dp[41]{ 0, 1, 1 }; int T; scanf("%d", &T); for (int i = 3; i < 41; ++i) dp[i] = dp[i - 2] + dp[i - 1]; while (T--) { int N; scanf("%d", &N);..
-
[백준] 바이러스알고리즘/백준 2021. 8. 10. 16:46
문제 링크 풀이 1번 컴퓨터에 연결된 노드의 갯수만 구하면 된다. 카운트할 때 1번 컴퓨터는 제외한다. 예를 들어 1번, 2번이 감염됐다면 카운트는 1이다. 큐를 이용해 bfs로 풀 수 있다. 1번 컴퓨터가 다른 컴퓨터와 연결되어 있지 않다면 0이 출력되면 된다. 코드 #include #include using namespace std; int main() { int N, pair; bool visited[101] = {}; scanf("%d%d", &N, &pair); ++N; int com[101][101] = {}; for (int i = 0; i < pair; ++i) { int a, b; scanf("%d%d", &a, &b); com[a][b] = 1; com[b][a] = 1; } queue..
-
[백준][2667번] 단지번호 붙이기알고리즘/백준 2021. 8. 9. 20:29
문제 링크 풀이 아직 방문하지 않은 집을 방문해 인덱스를 큐에 넣고, 인접 노드를 검사해 방문한 적 없는 집이라면 해당 인덱스를 큐에 넣는 걸 반복합니다. 코드 #include #include using namespace std; int main() { int N; scanf("%d", &N); char map[25][25] = {}; bool flag[25][25] = {}; int row_dir[] = {0, 1, 0, -1}; int col_dir[] = {1, 0, -1, 0}; for (int i = 0; i < N; ++i) scanf("%s", map[i]); priority_queue pq; int count = 0; for (int i = 0; i < N; ++i) { int answer..
-
[백준] 미로 탐색알고리즘/백준 2021. 8. 9. 17:12
문제 링크 풀이 BFS을 활용해서 풀면 방문하는 노드는 자연스럽게 최소 경로가 됩니다. 방문할 때마다 거리를 계산해주면 됩니다. 코드 #include #include using namespace std; int main() { int N, M; scanf("%d%d", &N, &M); int row[] = { 0, 1, 0, -1 }; int col[] = { 1, 0, -1, 0 }; char temp[100]; int map[102][102]; int dist[102][102]; bool visited[102][102]; for (int i = 1; i
-
[프로그래머스] 예상 대진표알고리즘/프로그래머스 2021. 8. 5. 14:32
문제 링크 풀이 시드 개념으로 접근했습니다. {1,2}는 1번 시드, {3,4}는 2번 시드. 라운드가 진행되면서 주어진 a, b가 같은 시드가 되면 됩니다. 1번 시드에 속하면 계속 1번 시드이지만 다른 시드에 속한 사람은 배정된 번호가 라운드마다 바뀌므로 새롭게 시드가 배정됩니다. 배정 번호로 시드를 구하면 됩니다. 짝수 번호는 나누는 수가 자신의 시드이지만 홀수인 자는 올림 연산을 해야 합니다. 7번은 4번 시드이니까요. 처음에 ceil()을 사용했지만 비트 연산을 활용하는 방법도 있습니다. 코드 #include int solution(int n, int a, int b) { int answer = 0; while (a != b) { a = ceil(a / 2.f); b = ceil(b / 2.f)..
-
[프로그래머스] 올바른 괄호알고리즘/프로그래머스 2021. 8. 5. 14:16
문제 링크 풀이 예외 케이스를 생각해봐야 하는 문제 같습니다. 처음에 작성한 코드는 괄호 짝을 다 맞추고 나서 뒤에 붙는 괄호를 걸러낼 수가 없었습니다. "()()(" 이런 경우가 해당됩니다. 그래서 조건문을 조금 변경했습니다. 코드 #include #include using namespace std; bool solution(string s) { if (s[0] == ')') return false; stack b; for (int i = 0; i < s.size(); ++i) { char c = s[i]; if (!b.empty() && c == ')') b.pop(); else b.push(c); } return b.empty() ? true : false; }
-
[알고리즘] Quick sort개발/C·C++ 2021. 8. 3. 16:17
종류 분할-정복 알고리즘입니다. 분할-정복 알고리즘은 재귀적으로 자신을 호출하면서 연산 단위를 조금씩 줄여나가는 방법입니다. 재귀 호출이 한 번 진행될 때마다 최소 하나의 원소는 위치가 정해지기 때문에 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있습니다. 장점 재귀호출의 과정에서 임시 메모리를 쓰는 것은 성능 저하를 가져오기 때문에(리턴값을 사용하지 않음) 배열 내부에서 분할 작업을 구현하는 편이 좋습니다. 퀵 정렬은 메모리 참조가 지역화되어 있기 때문에(캐시의 공간 지역성) 캐시 히트률이 높습니다. 이런 이유로 일반적인 경우 퀵 정렬은 다른 O(nlogn) 알고리즘보다 빠르게 작동합니다. 기본 흐름 피벗을 기준으로 왼쪽에는 피벗보다 작은 원소를, 오른쪽에는 피벗보다 큰 원소들을 위치합니다. 개념적으..