Algorithm
-
[BOJ] 2156번: 포도주 시식Algorithm/Baekjoon Online Judge 2022. 4. 11. 18:10
문제 풀이 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 3연속으로 시식할 수 없다는 조건이 제일 중요하다. 다이나믹 프로그래밍을 통해 해결할 수 있는데 첫번 째 포도주 잔부터 마지막까지 하나씩 보면서 해당 잔에서 마실수 있는 최대 양을 구하면 된다. 3연속 조건에 의해 매번 3가지 경우 중에 하나로 판별을 해야한다. 현재 잔을 i번째 잔이라고 하면 1. i번째 잔을 마시고 i-1번째 잔을 마셨을 때 i-3번째까지 마실 수 있는 최대 양의 합 ..
-
[BOJ] 10844번: 쉬운 계단 수Algorithm/Baekjoon Online Judge 2022. 4. 10. 23:12
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 처음에 생각했던 방식은 N이 1일 때 부터 시작해서 9, 17, 32,,,,순으로 개수가 증가하길래 dp[1] = 9로 정해두고 dp[N] = dp[N-1]*2 - N + 1 와 같은 식을 생각했다. 하지만 이렇게 코드를 작성했을 경우 틀렸습니다!가 표시,,,, 예를들어 N이 5일경우 내 식에 의하면 118이지만 답은 116이 나온다. 따라서 다른 코드를 생각했다. N이 1일때, 0 은 0가지 1, 2, 3, 4, 5, 7=6, 7, 8, 9 모두 1가지이다. N이 2일때, 뒤에 붙는 숫자를 기준으로 생각해보자..
-
[Algorithm] 동적계획법(Dynamic Programming)Algorithm/Algorithm Theory 2022. 4. 7. 21:43
Dynamic Programming 동적 계획법은 문제를 해결할 때 하나의 문제를 여러개의 작은 문제로 나누어서 작은 문제의 결과를 기억해두었다가 이를 사용하여 큰 문제를 해결하는 것이다. 재귀처럼 반복적으로 작은 문제들에 접근할 경우 이를 구하기 위해서 오랜 시간이 걸리기 때문에 비효율적이다. 따라서 이러한 반복적인 접근을 피하기 위해 메모리제이션, 기억해두는 방법을 사용하게 되는 것이다. 대표적인 예로 피보나치 수열이 있다. int fibo(n): if n
-
[BOJ] 2580번: 스도쿠Algorithm/Baekjoon Online Judge 2022. 4. 4. 13:28
https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제풀이 스도쿠를 해결하기 위해 백트랙킹 알고리즘을 사용해야하는 것까지는 떠올리기 쉬웠지만, dfs를 어떤 방식으로 적용할지 생각해내는 것이 어려웠다. 우선 가장 기본적인 생각은 수를 채워야하는 칸의 행, 열, 정사각형 안에서 필요한 수를 찾는 것이다. 후보가 한개의 수만 존재한다면 단순히 값을 집어넣어주면 되지만 여러개라면 어떻게 할지 생각해야 했다. 그래서 생각한 방식이 우선 후보수 중에 하나..
-
[BOJ] 9663번: N-QueenAlgorithm/Baekjoon Online Judge 2022. 4. 1. 00:13
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net Python3 체스판에서 퀸이 놓여질 때 서로 공격할 수 없게 놓아야한다. 퀸이 공격할 수 있는 상황은 1. 같은 행에 다른 퀸이 위치할때, 2. 같은 열에 다른 퀸이 위치할 때, 3. 대각선상에 다른 퀸이 위치할 때 3가지 경우이다. 이는 백트랙킹으로 해결 할 수 있다. 먼저 퀸을 행 중 한 열에 놓은 후 다음 퀸의 위치를 택하는 상황을 연쇄적으로 하면 된다. 예를 들어보자! Q x x x Q x x x x x..
-
[BOJ] 15649번: N과 M(1)Algorithm/Baekjoon Online Judge 2022. 3. 31. 02:09
https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net Python3 백트랙킹 알고리즘으로 해결하는 방식과 파이썬 내장함수를 사용하여 해결하는 방식 2가지로 풀어보았다. Code 1 from itertools import permutations if __name__ == '__main__': N, M = map(int, input().split()) numbers = [i for i in range(1, N+1)] for item in permuta..
-
[Algorithm] 백트랙킹(BackTracking)Algorithm/Algorithm Theory 2022. 3. 31. 01:51
백트랙킹 백트랙킹은 가능한 모든 방법을 탐색한다. 즉, 현재 상태에서 가능한 모든 후보를 따라 후보를 다시 탐색하면서 해를 찾아나가다가 해가 아니라고 판단되면 다시 되돌아가 다른 후보를 탐색하여 해를 찾아가는 방식이다. 이는 최적화 문제와 결정문제를 푸는 방법이 된다. 위의 상황을 트리에 적용해보면 트리 탐색 알고리즘이라고 생각할 수 있다. 트리 탐색 알고리즘은 방식에 따라서 깊이 우선 탐색(Deep First Search, DFS), 너비 우선 탐색(Breadth First Search, BFS)으로 나눌 수 있다. 백트랙킹은 모든 경우의 수를 고려해야하기에 DFS로 구현한다. 더보기 DFS(Deep First Search) 트리의 root에서 바닥에 도달할 때까지 한 쪽에서 시작하여 가능한 모든 경로..
-
[BOJ] 2108번: 통계학Algorithm/Baekjoon Online Judge 2022. 3. 26. 01:45
https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net Python3 import sys from collections import Counter N = int(input()) numbers = [] for _ in range(N): numbers.append(int(sys.stdin.readline())) numbers.sort() print(round(sum(numbers)/N)) print(numbers[N//2]) nums = Counter(numbers)...