알고리즘_PS

[Baekjoon] 1019 책 페이지 - C++

> 문제 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자. > 풀이 문제 자체는 보기엔 간단해 보이지만, 1~n까지의 모든 문자열 각각에 대해 각 자리의 숫자를 카운트 해주면 시간초과가 나는 문제이다. 시간복잡도만 보자면 O(nlogn)인데 문자열 처리에 걸리는 시간에 n 0은 100~109, 200~209, .., 54200~542..

[Baekjoon] 3273 - 두 수의 합 (C++)

> 문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i 풀이 idea 1) m..

[Algorithm] 위상 정렬 - C

https://m.blog.naver.com/ndb796/221236874984 25. 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 ... blog.naver.com https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%ACTopology-sort [알고리즘] 그림으로 알아보는 위상 정렬(Topology sort) 위상정렬은 순서가 정해져 있는 노드..

[Baekjoon] 2156 - 포도주 시식 / C++

> 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효..

[Baekjoon] 21921 블로그 - C++

> 문제 문제 링크 : https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 문제 요약 : 총 n개의 방문자 수가 주어질 때, x일간 방문한 최대 방문자수와 그 방문자수가 있는 구간의 개수를 구하여라. > 풀이들 첫 번째 풀이 : 구간 x 안에 있는 사람들의 합을 각각 구하고, 그걸 n - x + 1번만 반복하면 되는 줄 알았다. 하지만 시간 초과가 떠서 다른 방법을 생각해야만 했다. (시간 복잡도가 O(n-x+1) * O(x) => O(x*..

[백준] 22943_수 / python

https://www.acmicpc.net/problem/22943https://www.acmicpc.net/problem/22943 22943번: 수 0부터 9까지 $K$가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 중 아래 조건을 모두 만족하는 수들의 개수를 구해보자. 단, 수의 맨 앞에는 0이 올 수 없다. 즉, 0143는 불가능하다. 서로 다른 www.acmicpc.net 문제 0부터 9까지 K가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 중 아래 조건을 모두 만족하는 수들의 개수를 구해보자. 단, 수의 맨 앞에는 0이 올 수 없다. 즉, 0143는 불가능하다. 서로 다른 두 개의 소수의 합으로 나타낼 수 있는 경우 M으로 나누어 떨어지지 않을때까지 나눈 수가 두 개의 소수의 곱인 경우..

[Project_Euler] 55번 10000 미만의 라이크렐 수 세기

코드 def palidrome(k): # 대칭수 찾는 함수, O(logn) k = str(k) length = len(k) for i in range(length//2): if k[i] != k[length - i - 1]: return 0 return 1 n = 1 lychrel = 0 # 라이크렐 수의 개수 while n

[Baekjoon] 9461 파도반 수열, 10844 계단 수, 1924 2007년

백준 9461 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 나선을 따라 가며 n번째의 삼각형의 변의 길이를 찾는 문제이다. 삼각형의 변의 길이는 이전 삼각형과 5번째 전 삼각형의 변의 길이를 더한 것과 같다는 점을 이용해 문제를 해결할 수 있다. 정삼각형의 한 각의 크기는 60도이므로, 이 점을 이용해 5번째 전의 삼각형을 추론할 수도 있을 것이다. 코드는 다음과 같다. t = int(input()) for i in range(t):..

[Baekjoon] 9663_N-Queen #3

N - Queen 문제 중 한 종류인 8-Queen 문제이다. N - Queen 문제는 결국 n을 입력받아 n * n 사이즈 보드 안에 n개의 퀸을 겹치지 않고 배열할 수 있는 경우의 수가 얼마나 되는지를 세는 알고리즘이다. 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예시 입력과 출력은 다음과 같다. 이외에도 표로 나머지 경우를 정리하면 다음과 같다. n 1 2 3 4 5 6 7 8 경우의 수 1 0 0 2 10 4 40 92 이외에도 9..

[Baekjoon] 7576 토마토

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 ..

[Algorithm] Dynamic Programming에 관해

소마 13기 코테를 준비하며, dp문제를 많이 풀 기회를 접하였다. 그래봤자 난이도가 실버급에 있는 문제들이긴 하지만, 그래도 일단 내가 풀면서 느낀 점들을 정리하려 한다. 먼저 DP, Dynamic Programming은 문제풀이 알고리즘의 한 종류로, DFS나 그리디, 백트래킹과는 또다른 성격의 문제풀이법이다. 풀면서 수학적 귀납법과 비슷하다는 느낌을 받았다. 먼저, 속도에 관해 말해 보자면 DFS는 시간이 엄청 걸리고, 백트래킹은 그걸 조금 줄여주지만 DP는 확실히 줄여 주는 것을 느꼈다. 여기서 한 가지 느낀 점은 "DP는 시간과 공간을 trade해서 효율성을 올린 알고리즘" 이다. DP문제를 풀다 보면 점화식 형태의 풀이법이 많다. 대부분 배열이나 리스트를 이용하여 점화식을 세워 문제를 푸는데,..

[Baekjoon] 9663_N-Queen #2

저번 글에서는 Python으로 N-Queens 문제를 푸는 시도를 적었다. 하지만 최적화를 진행해도 속도가 너무 느리다는 단점이 있었다. 그래서 혹시 속도가 빠른 C언어로 진행하면 어떨까 싶어 C언어로 코드를 옮겨 실행해 보았다. 이정도면 시간 복잡도가 O(10^n)....;;;;; 결과는 놀라웠다. C언어는 월등히 빠른 속도를 자랑했지만, 여전히 n = 15까지는 가지도 못했다. 결국, 알고리즘 실력이 문제였다... 더 열심히 해야겠다. C 코드는 다음과 같다. #include #include // 함수 선언 void n_queen(int i, int j); int check(int i, int j); // 전역 변수 설정 int cnt = 0; int n = 0; int board[15][15] = ..

[Baekjoon] 9663_N-Queen #1

출처 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 먼저 이 문제를 해결하기 위해 필자는 이전 문제에서 배웠던 구조를 가져왔다. 함수 안에 반복문을 ..

[Baekjoon] 10989번 수 정렬하기 3, pypy3 메모리초과

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net [문제] N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. [입력] 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. [출력] 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 메모리 제한이 있어 (8MB) 자칫 잘못하면 메모리 초과가 떠서 문제를..

[Baekjoon] 1018 체스판 다시 칠하기

[문제] https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net M * N 보드에서 나올 수 있는 8 * 8 크기의 보드 중 최소한으로 색을 칠해 체스판으로 만드는 경우의 색을 칠할 칸의 수를 출력하는 프로그램을 만드는 문제. 입력받은 체스판을 이렇게 만드는 것이 목표. (또는 W, B가 반전된 채로) [입력] 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각..