본문 바로가기
728x90

study/알고리즘

 (44)
[알고리즘/백준] 2659번 - 십자카드 문제 🔗 문제 2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net level : 실버 3 알고리즘 분류: 브루트포스(완전탐색), 정렬 문제 설명: 위와 같은 십자 모양 카드에서 네 모서리의 숫자( 1 ~ 9, 중복 가능)를 시계 방향으로 읽어서 만들 수 있는 수(3227, 2273, 2732, 7322) 중 가장 작은 수 2273을 시계수라고 한다. 입력으로 주어진 카드의 시계수를 계산하여, 그 시계수가 모든 시계수들 중 몇 번째로 작은 시계수인지를 알아내는 프로그램을 작성하시오 🔮 풀이 아이디어 문제 접근 방식 하나의 십자 모양 카드에서 만들..
[알고리즘/백준] 2960번 - 에라토스테네스의 체 🔗 문제 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net level : 실버 4 문제 설명: 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 1. 2부터 N까지 모든 정수를 적는다. 2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. 3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. 🔮 풀이 아이디어 에라토스테네스의 체 알고리즘을 알고 있어서 먼저 함수로 작성 ..
[알고리즘/백준] 26069번 - 붙임성 좋은 총총이 🔗 문제 26069번: 붙임성 좋은 총총이 첫번째 줄에는 사람들이 만난 기록의 수 $N\ (1 \le N \le 1\ 000)$이 주어진다. 두번째 줄부터 $N$개의 줄에 걸쳐 사람들이 만난 기록이 주어진다. $i + 1$번째 줄에는 $i$번째로 만난 사람들의 이름 $A_i$ www.acmicpc.net level : 실버 4 문제 설명: 무지개 댄스를 추지 않고 있던 사람이 무지개 댄스를 추고 있던 사람을 만나게 된다면, 만난 시점 이후로 무지개 댄스를 추게 된다.기록이 시작되기 이전 무지개 댄스를 추고 있는 사람은 총총이(ChongChong) 뿐이라고 할 때, 마지막 기록 이후 무지개 댄스를 추는 사람이 몇 명인지 구해보자! 🔮 풀이 아이디어 defaultdict(int)로 딕셔너리를 선언해주면 ke..
[알고리즘/백준] 1912번 - 연속합 카테고리 : DP(다이나믹 프로그래밍) 1912번 연속합 - https://www.acmicpc.net/problem/1912 예제 입력 1 10 10 -4 3 1 5 6 -35 12 21 -1 예제 출력 1 33 접근 방법 n개의 정수로 이루어진 임의의 수열 중 연속된 수들의 합이 가장 큰 경우를 출력해야 한다. 특정 수의 경우의 수는 이전에 연속된 합을 선택하거나 선택하지 않는 경우이다. 선택하는 경우 : 이전 합에 자신의 수를 더한 값 선택하지 않는 경우 : 자신의 수 (이전에 연속된 합을 선택하지 않으면서 현재 숫자가 처음이 된다) 처음에는 더한 모든 경우의 수를 배열에 저장해야 할까 생각했는데 과정을 적어보니 결국 이전 값이 가장 큰 경우에 자신의 수를 더하는 경우가 합이 가장 클 수 밖에 없다..
[알고리즘/백준] 1967번 - 트리의 지름 카테고리 : Tree / DFS(그래프 탐색) 1967번 트리의 지름 - https://www.acmicpc.net/problem/1967 접근 방법 먼저 tree의 정보를 딕셔너리를 통해 저장해주었다. p는 부모 노드, c는 자식 노드, w는 가중치 정보이다. tree = defaultdict(list) n = int(input()) for _ in range(n - 1): p, c, w = map(int, input().split()) tree[p].append((c, w)) DFS를 통해 트리를 탐색한다. 루트 노드의 번호가 항상 1이라고 가정되어있기 때문에 항상 루트부터 시작할 수 있다. tree는 아까 저장해두었던 딕셔너리이고 i는 노드 번호이다. def DFS(tree, i): global r..
[알고리즘] 3-Way inPlaceQuickSort - 네덜란드 국기 알고리즘 서론 quick sort quick sort는 기준 원소 pivot을 설정 후 기준 원소보다 작은 / 기준 원소와 같은 / 기준 원소보다 큰 리스트 3개로 분할하여 정렬한다. 따라서 입력 리스트의 모든 원소는 세 개의 부 리스트 중 하나에 삽입된다. inPlaceQuickSort quick sort는 제자리에서 수행되도록 구현이 가능하다. 입력 리스트의 원소를 재배치할 때 값을 삽입하는 대신 대체 작업을 수행한다. 대체란 입력 리스트 내에서 재배치되어야 할 원소들의 자리를 맞바꾸는 것이다. ※ 지금부터 설명하는 부분은 inPlaceQuickSort를 구현할 때 배열로 구현한다고 가정한다. 연결리스트에서는 쉽게 해결이 가능한 문제이기에 고민할 필요가 없었다. ※ quicksort를 진행할 때 분할 과정에 ..
[알고리즘/백준] 11725번 - 트리의 부모 찾기 11725번 트리의 부모 찾기 - https://www.acmicpc.net/problem/11725 카테고리 : Tree / BFS(그래프 탐색) 접근 방법 노드 정보를 받을 때 트리 상에서 연결된 두 정점에 대해서 받게 된다. 따라서 정보를 받을 때 누가 부모인지 알 수 없어서 먼저 Tree를 2차원 리스트에 담아주었다. 노드 번호를 인덱스로 사용하기 위해 0번째 인덱스는 사용하지 않았다. 그리고 그래프처럼 각 정점에 대해 연결된 서로의 정점 정보를 모두 담아주었다. node = [[] for _ in range(N + 1)] for _ in range(N - 1): n1, n2 = map(int, input().split()) node[n1].append(n2) node[n2].append(n1) ..
[알고리즘/백준] 16401번 - 과자 나눠주기 16401번 과자 나눠주기 - https://www.acmicpc.net/problem/16401 카테고리 : 이분 탐색 / 매개변수 탐색 접근 방법 이 문제는 매개 변수 탐색 문제이다. 매개 변수 탐색이란 이분탐색을 사용하여 조건을 만족하는 최댓값을 구하는 방법이다. 1. 막대 과자 길이를 매개 변수(이분 탐색을 진행하는 대상)으로 설정한다. --> 최소 길이 1 / 최대 길이 max(snack) 을 start와 end로 설정 start, end = 1, max(snack) 2. mid만큼 자를 때 mid 길이로 잘릴 수 있는 개수를 세어준다. ex) 만약 길이가 11인 막대 과자를 5로 자른다면 5 / 5 / 1 로 잘리기 때문에 개수는 2개 cnt = sum([snack[i] // mid for i..
반응형

티스토리툴바