본문 바로가기
반응형

알고리즘 테스트58

백준 9184 : 신나는 함수 실행 (파이썬) 신나는 함수 실행 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 20643 8926 6757 42.008% 문제 재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구.. 2022. 2. 7.
백준 14889 : 스타트와 링크 (파이썬) 스타트와 링크 시간 제한 메모리 제한 제출 정답 맞힌 살마 정답 비율 2 초 512 MB 52962 26730 15618 47.160% 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사.. 2022. 2. 6.
백준 14888 : 연산자 끼워넣기 (파이썬) 연산자 끼워넣기https://www.acmicpc.net/problem/14888풀이 코드# https://teching.tistory.com/import sysn = int(sys.stdin.readline().rstrip())nums = list(map(int,sys.stdin.readline().split()))#operator 0: +, 1: -, 2: *, 3: /operator = list(map(int,sys.stdin.readline().split()))use_operator = [0, 0, 0, 0]answerMax = -1000000000answerMin = 1000000000def solve(idx,res): global n, answerMin, answerMax if i.. 2022. 2. 5.
백준 2580 : 스도쿠 (파이썬) 스도쿠https://www.acmicpc.net/problem/2580 코드import sysboard = []answerCnt = 0empty = []emptyLoc = []for i in range(9): line = list(map(int,sys.stdin.readline().split())) board.append(line) for j in range(9): if line[j] == 0: empty.append(0) emptyLoc.append([i, j])def sudoku(idx): global answerCnt if answerCnt == 0: #이전 빈칸들 채워넣기 for i in ran.. 2022. 2. 4.
백준 9663 : N-Queen (파이썬) N-Queenhttps://www.acmicpc.net/problem/9663코드# https://teching.tistory.com/n = int(input())cnt = 0def nQueen(placed): global n, cnt row = len(placed) if row == n: cnt += 1 else: #해당 열에서 퀸을 둘 수 있는 곳을 찾기. can = [1 for i in range(n)] for i in range(row): can[placed[i]] = 0 #대각선 if placed[i]+(row-i) = 0 : can[pla.. 2022. 2. 4.
깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 깊이 우선 탐색 (DFS : Depth First Search) 대표적으로 백트래킹에 사용한다. 일반적으로 재귀 호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다. 자동 미로 생성에 많이 사용 되는 알고리즘! 장점 현 경로상의 노드만 기억하면 돼서 저장공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 수 있다. ( 임의 깊이까지만 탐색하도록 만들기! ) 얻어진 해가 최단 경로가 아닐 수도 있다. 왜냐? DFS는 일단 해를 찾으면 탐색이 끝나기 때문이다. 동작 방식 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 .. 2022. 2. 1.
백준 15649 : N과 M (1) (파이썬) N과 M (1)https://www.acmicpc.net/problem/15649코드1# https://www.acmicpc.net/problem/15649# https://teching.tistory.com/import itertoolsn, m = map(int,input().split())nums = [i+1 for i in range(n)]for ln in list(itertools.permutations(nums,m)): for i in range(m): print(ln[i],end= ' ') print('')코드 2# https://www.acmicpc.net/problem/15649# https://teching.tistory.com/def bts(n, m, visite.. 2022. 2. 1.
백준 2108 : 통계학 (파이썬) 통계학https://www.acmicpc.net/problem/2108코드# https://teching.tistory.com/import syscnt = [0 for _ in range(8001)]n = int(sys.stdin.readline().rstrip())total = 0maxN = -4000minN = 4000for _ in range(n): num = int(sys.stdin.readline().rstrip()) cnt[num+4000] += 1 total += num maxN = max(maxN, num) minN = min(minN, num)mode = []index = 0for i in range(8001): num = i-4000 if cnt[i.. 2022. 1. 31.
정렬 알고리즘 3 : 계수 정렬(Counting sort) 세 번째로 알아볼 정렬 알고리즘은 바로 계수 정렬! 계수 정렬은 수의 범위가 적을 때 사용하면 좋은 정렬 알고리즘으로 배열의 가장 큰 값에 따라 시간 복잡도가 달라진다. 배열의 가장 큰 값이 k라고 한다면 O(n+k)의 시간 복잡도를 갖는다. 즉, 입력에 비해서 원소들의 값의 범위가 적다면 계수정렬을 사용하는 것이 효율적인 방법이 될 수 있다! 방법 1. 입력된 배열중 가장 큰 값(k) 찾기 2. k+1 크기의 0으로 초기화된 배열 생성한다. 이는 입력된 배열의 원소가 각각 몇 개가 있는지 셀 배열이다. 3. 배열의 원소를 하나씩 검사하여 2번에서 생성한 배열의 인덱스에 해당하는 값을 1씩 올려준다. (즉, 각 값이 몇 개가 나왔는지 카운팅 해준다.) 4. 각 인덱스를 값만큼 반복하여 출력한다. 예시 배.. 2022. 1. 31.
반응형

티스토리툴바