본문 바로가기

알고리즘/백준

 (263)
[백준] 14891번 : 톱니바퀴 14891번: 톱니바퀴 해당 문제는 구현 문제로 주어진 문제의 조건에 따라 문제를 해결하면 된다. 해당 톱니바퀴에서 다른톱니바퀴를 돌릴 수 있는 재귀적인 로직이 있기때문에 재귀함수로 문제를 해결하였습니다. 현재 톱니바퀴 위치에서 각각의 극과 극을 확인하여 재귀함수를 호출할것인지 말것인지에 판단합니다. move = (1, -1) north = 0 right = 2 left = 6 def sumScore(graph): sum = 0 for i in range(1, len(graph)): if graph[i][north] == '1': sum += (2)**(i-1) return sum def rightRotate(arr): # 시계방향 temp = arr[-1] for i in range(len(arr)-2..
[백준] 2504번 : 괄호의 값 2504번: 괄호의 값 해당 문제를 스택자료구조를 활용하여 문제를 풀면된다. 주어진 조건에따라서 스택을 pop, append 해가면서 최종 마지막 스택값에 있는값을 출력하면 된다. “(”을 만나면 temp에 *2를 해준다. “)”를 만나면 result에 가중치를 더하고 temp에 //2를 해준다. “[”를 만나면 temp에 *3를 해준다. “]”를 만나면 result에 가중치를 더하고 temp에 //2를 해준다. char = input() stack = [] temp = 1 result = 0 errorFlag = False for i in range(len(char)): if char[i] == '(': stack.append(char[i]) temp *= 2 elif char[i] == '[': st..
[백준] 2250번 : 트리의 높이와 너비 2250번: 트리의 높이와 너비 해당 문제는 이진 트리의 성질 중 “중위 순회” 법을 사용하여 문제를 해결 할 수 있다. 중위순회는 왼쪽노드 → 루트노트 → 오른쪽 노드를 순서대로 방문한다. 순서대로 방문했을때 각각의 노드와 x,y 좌표를 배열에 저장해 두었다가, 가장 큰 레벨을 찾으면 된다. import sys sys.setrecursionlimit(10000000) N = int(input()) rootgraph = [[] for _ in range(N+1)] graph = [[] for _ in range(N+1)] graph2 = [[] for _ in range(N+1)] for _ in range(N): root, left, right = map(int, input().split()) # 자식..
백준 2239번 : 수도쿠 2239번: 스도쿠 완전탐색 문제로, 비어있는 수도쿠 수의 좌표에서 놓을 수 있는 경우의수를 구한뒤, 그 경우의수를 하나하나 다 넣어보면서 스도쿠를 완성해나간다. 완성해 나가는도중에 수도쿠를 놓을 수 없는경우 백트래킹 한다. def getavailable(i, j): h, w = getpos(i,j) temp = {1,2,3,4,5,6,7,8,9} # 놓을 수 있는 수. for k in range(h, h+3): # 3x3 정사각형 for n in range(w, w+3): if table[k][n] in temp: temp.remove(table[k][n]) for t in range(9): # 가로, 세로 n1 = table[i][t] n2 = table[t][j] if n1 in temp: temp..
[백준] 1051번 : 숫자 정사각형 1051번: 숫자 정사각형 해당문제는 완전탐색 문제로 특정 좌표에서 정사각형을 그릴수 있는 크기를 구한뒤 후보를 정한뒤 각각의 후보에서 꼭지점의 수가 같은지 확인합니다. 특정좌표에서 정사각형의 크기를 구하는 로직 크기 4의 정사각형 탐지법, 특정좌표에서 + (1, 1)의 값이 범위 안에 있는지 확인한다. 크기 9의 정사각형 탐지법, 특정좌표에서 + (2,2)의 값이 범위 안에 있는지 확인한다. N, M이 주어졌을때 정사각형의 크기는 반드시 N, M이랑 작거나 같다. 꼭지점의 수가 같은지 확인법 크기 4의 정사각형 탐지법, 특정좌표에서 자기자신과 (1,1), (0,1), (1,0)가 같다면 꼭지점이 같다. 크기 9의 정사각형 탐지법, 특정좌표에서 자기자신과 (2,2), (0,2), (2,0)가 같다면 꼭지..
[백준] 1182번 : 부분수열의 합 1182번: 부분수열의 합 해당 문제는 완전탐색 문제로 수열의 개수 N이 주어졌을때 특정 위치가 있는경우와 없는경우 의 조합으로 이야기 할 수 있습니다. 따라서 시간복잡도는 O(2^n) 입니다. 깊이우선탐색으로 해당 조합을 생성합니다. 조합을 만들어가면서 누적합이 S인 경우를 가중치에 추가합니다. import sys input = sys.stdin.readline N, S = map(int, input().split()) arr = list(map(int, input().split())) cnt = 0 def solve(queue, idx): global cnt if queue: if sum(queue) == S: cnt += 1 for i in range(idx, N): queue.append(arr[..
[백준] 7490번 : 0만들기 7490번: 0 만들기 해당 문제는 완전탐색문제로 해결할 수 있습니다. 각각의 숫자에 대하여 +, -, ‘ ‘ 연산을 수행해봄으로서 N이 9보다 작거나 같기 때문에 최악의 연산 횟수는 O(3^8) 입니다. 테스트 케이스 또한 10 이하 이기때문에 O(10* 3^8) 임으로 충분히 시간안에 풀 수 있습니다. 깊이우선 탐색으로 경우의 수를 모두 구한뒤 구한 결과를 0인지 아닌지에 따라서 결과를 출력 하면 됩니다. oper = ['+', '-', ' '] def dfs(depth, sequence): if depth == N: newsequence = sequence.replace(' ', '') total = eval(newsequence) if 0 == total: ans.append(sequence) r..
[백준] 1941번 : 소문난 칠공주 1941번: 소문난 칠공주 해당문제는 완전탐색과 백트래킹 문제로 특정한점 (i,j)로부터 7명의 학생수를 연속으로 방문한 경우의 수 중에서 조건에 만족하는 경우의 수만 카운팅 하면 된다. 7명의 여학생들로 구성되어 있어야한다 DFS탐색을 하였을때 길이가 7인 경우 7명은 가로나 세로로 반드시 인접해야함 DFS탐색을 할때 상,하,좌,우로 움직인다. 화합과 번영을 위해 반드시 이다솜파 학생들로만 구성될 필요는 없다. (Y,S 혼용가능) 반드시 이다솜파가 우위를 점하여야 한다. 이다솜파는 적어도 반드시 4명을 포함해야한다. ( 만약 임도연 파가 4명이 이상이 될경우 조건을 만족시키지 못함으로 탐색을 중지한다) 이 문제에서 중요한 포인트는 중복탐색을 방지해야한다. 예를들어 (0,0)에서 탐색한 결과와 (1,1)..

티스토리툴바