본문 바로가기

전체 글67

[백준] 11055 - 가장 큰 증가 부분 수열 (DP) https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 난이도 : 하 DP 기본 문제 import sys n = int(sys.stdin.readline()) a = list(map(int,sys.stdin.readline().split())) dp = [0]*n for i in range(n) : dp[i] = a[i] # 자기자신만 수열인 경우 for i in range(n): for j .. 2022. 10. 12.

알고리즘 키워드 정수론, 배열, 문자열, 재귀함수, 정렬, 완전탐색, 시간복잡도 이분탐색, 분할정복, 스택, 큐, 우선순위 큐 그래프(vertex, edge, node, arc), BFS, DFS, 위상정렬 동적 프로그래밍, 그리디 알고리즘 2022. 9. 29.

[leetcode] 206번 Reverse Linked List 206번 역순 연결 리스트 https://leetcode.com/problems/reverse-linked-list/ Reverse Linked List - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 1 - 배열에 저장하여 뒤집기 class Solution: def reverseList( head: Optional[ListNode]) -> Optional[ListNode]: arr = [] while head : arr.append(head.val) h.. 2022. 5. 7.

[Week05] C언어 - Red Black Tree Red - Black Tree 레드 블랙 트리 https://ko.wikipedia.org/wiki/레드-블랙_트리 레드-블랙 트리 - 위키백과, 우리 모두의 백과사전 레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스(Leo J. Guibas)와 로버트 ko.wikipedia.org 이진 탐색트리의 한 종류 BTS의 worst case의 단점을 개선 - 스스로 균형을 맞추며 편향된 트리가 되지않도록 한다. 최악의 경우에도 시간복잡도가 O(logN) 규칙 레드와 블랙으로만 이루워진다. 루트 노드는 블랙이다. nil노드는 블랙이다. 레.. 2022. 5. 5.

[Week04] 알고리즘 - 비트 마스킹 백준 외판원 순회 문제(TSP)를 풀려면 비트 마스킹에 관한 개념이 필요하여 공부하게되었다. 해당 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net keywords 비트마스킹 dp, 비트마스킹 bfs, 비트마스크 순열, 비트마스크 조합 비트 마스킹 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법이다. check = [False] * .. 2022. 4. 26.

[Week03] 알고리즘 - DFS / BFS 백준 문제 두 문제를 구분하는 기준이 약간 모호하지만.. 문제를 풀면서 만났던 몇몇 유형들을 까먹지않기 위해 정리해둔다. DFS / 백트래킹 nums = [1,2,3] result = [] permute = [] def dfs(): if len(permute) == len(nums) : result.append(permute[:]) return for i in range(len(nums)) : if nums[i] not in permute : permute.append(nums[i]) dfs() permute.pop() dfs() print(result) DFS 25731번 : 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를.. 2022. 4. 21.

이전 1 ··· 7 8 9 10 11 12 다음

티스토리툴바