Do whatever you want

문제 : https://www.acmicpc.net/problem/2239 문제 요약스도쿠판이 주어졌을 때 스도쿠 판을 채우는 문제입니다. 문제 조건에 동일한 정답이 있을 경우 81자리가 가장 작은 숫자를 답으로 설정하라는 조건이 있습니다. 풀이 방식먼저 백트래킹을 사용해서 구현을 진행하였습니다. 먼저 2차원 배열에 입력을 받아서 앞에서부터 빈칸을 채우면서 백트래킹을 진행하는 방식으로 설계하여 구현했습니다. 따라서 아래 코드가 정답으로 나왔는데 아래 코드는 pypy3을 사용해서 정답으로 통과가 되었고 python3에서는 시간 초과가 되었습니다. 정답 코드import sysinput = sys.stdin.readlineclass Sudoku: def __init__(self): self...

문제 링크 : https://www.acmicpc.net/problem/12101문제 요약정수 n이 주어졌을 때 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전순으로 정렬했을 때 k번째로 오는 식을 나타내는 문제입니다. 풀이문제 풀이를 위해 DFS(깊이 우선 탐색) 알고리즘을 사용했습니다. 각 조합에 가장 작은 수인 1을 우선으로 추가해 주면서 DFS를 진행하게 된다면 최종 리스트에는 정렬된 값이 순서대로 들어있기 때문에 효율적으로 문제를 해결할 수 있습니다. 정답 코드import sysinput = sys.stdin.readlinedef dfs(nums, n, numbers): sumNums = sum(nums) if sumNums == n: numbers.append(n..

문제 링크 : https://www.acmicpc.net/problem/9251문제 요약LCS는 두 수열이 주어졌을 때, 두 수열의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제입니다. 풀이LCS(Longest Common Subsequence) 알고리즘은 두 문자열에서 순서대로 존재하는 가장 긴 공통부분 수열을 찾는 알고리즘입니다. 이 알고리즘은 동적 계획법(Dynamic Programming)을 사용하여 두 문자열 간의 부분 수열을 비교해 나가는 방식으로 구현됩니다. 이때, 문자열의 각 문자를 비교하며 공통된 문자가 나오면 그 문자까지의 LCS 길이를 갱신합니다. 점화식각 문자열을 리스트로 만들어주고 문자를 하나씩 늘려가며 비교해주는 방식을 점화식으로 나타내면 다음과 같이 식을 세워볼 수 있습니..

문제 링크 : http://boj.kr/2178문제 요약N x M 크기의 배열 미로에서 1은 이동 가능한 칸을 0은 이동 불가능한 칸을 나타냅니다.(1, 1) 에서 출발해서 (N, M) 까지 이동할 때 지나야 하는 최소 칸을 구하는 문제입니다.입력N, M (2 ≤ N, M ≤ 100)N개의 줄에 M개의 정수로 미로예시)2 3110011풀이현재 칸에서 이동할 수 있는 경로가 정해져 있기 때문에 그래프 구조라고 생각해서 접근해 보았습니다.각 칸에서는 지나오지 않은 4방향의 칸들 중 이동 가능한 칸으로 이동하는 방법을 생각해서 따라서 그래프 BFS 구조로 구현해 보겠습니다.import sysinput = sys.stdin.readlineN, M = map(int,input().split())maze = []f..