Algorithm/Baekjoon Online Judge
-
[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..
-
[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)...
-
[BOJ] 10989번: 수 정렬하기 3Algorithm/Baekjoon Online Judge 2022. 3. 26. 00:53
https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net Python3 수 정렬하기 2의 문제와 비슷해보였여 제출했던 코드를 그대로 제출해보았다. https://miraekwak.tistory.com/72 [BOJ] 2751번: 수 정렬하기 2 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,..
-
[BOJ] 2751번: 수 정렬하기 2Algorithm/Baekjoon Online Judge 2022. 3. 26. 00:05
https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net Python3 초기 코드 if __name__ == '__main__': N = int(input()) numbers = [] for _ in range(N): numbers.append(int(input())) numbers.sort() print(*numbers, sep="\n") 이전에 풀었던 정렬 문제와 유사하다고 생각했고 파이썬 내장함수인 sort()를 사용해 해결하려고 했다...
-
[BOJ] 2750번: 수 정렬하기Algorithm/Baekjoon Online Judge 2022. 3. 23. 23:15
https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net Python3 if __name__ == '__main__': N = int(input()) numbers = [] for i in range(N): numbers.append(int(input())) numbers.sort() print(*numbers, sep="\n") 파이썬 내장함수 sort를 사용했다. 정렬 내장함수 알고리즘이 궁금해서 찾아봤는데 병합정렬과 삽입정렬을 섞은 알고리즘으로 시간복잡도는..
-
[BOJ] 1436번: 영화감독 숌Algorithm/Baekjoon Online Judge 2022. 3. 22. 22:46
https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net Python3 if __name__ == '__main__': N = int(input()) six_n = 666 cnt = 0 while True: if '666' in str(six_n): cnt += 1 if cnt == N: print(six_n) break six_n += 1 제일 작은 수인 666부터 1씩 증가시키면서 종말의 수라면 카운트를 증가시킨다. 카운트가 일치 했을 경우의 1씩..