배움의공간(學)/알고리즘6 [백준] 2252-줄 세우기 [조건] - 시간 제한: 문항, 2초 - Stack: 128MB [문제] N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. - 학생의 수: 1 ≤ N ≤ 32,000 - 비교 횟수: 1 ≤ M ≤ 100,000 [접근법] 알고리즘은 기본 개념과 어떻게 문제에서 응용되는지를 알아야 한다. "순서가 있는 일을 순서에 맞게 나열한다" 는 기본 개념을 잊지 않았다면 본 시험에서 적용해 봤을텐데.. 아쉽기만 하다. [알고.. 2021. 4. 5. [기출] 디자이너의 고민 [조건] - 시간 제한: 40문항, 1.5초 - Stack: 1MB [문제] 디자이너 조이는 가로 폭이 N인 화면의 배경 디자인을 의뢰 받았다. 서로 다른 가로 폭을 가진 K 종류의 배경 디자인 조각을 사용하여 디자인을 할 수 있는 방법이 몇 가지인지 찾아보아라. (답이 굉장히 클 수 있기 때문에 답을 1,000,000,007 로 나눈 나머지를 출력한다. - 화면 가로 폭: 1 ≤ N ≤ 50,000 - 조각 종류: 2 ≤ K ≤ 100 - 조각의 가로 폭: 1 ≤ A ≤ 1,000 - 각 디자인 조각의 가로 폭은 모두 다르다. - 각 디자인 조각은 여러 번 사용할 수 있다. [접근법] 1단계: 경우의 수. 즉 조합 문제로 접근하였다. 경우의 수를 백트래킹으로 구하고, 중복된 숫자를 카운팅하여 nCk 수.. 2021. 2. 10. [그래프] 사이클 찾기 1. 사이클을 이루는 정점 확인 1) BFS bool findCycle(int here, int depth) { stack s; // 사이클을 만나면 while문 종료 while (visit[here] == 0) { s.push(here); visit[here] = depth++; here = node[here]; } // cnt: 사이클 크기 int cnt = depth - visit[here]; cycle[here] = true; // 사이클에 포함되는 정점들을 마킹 while (cnt > 0) { int item = s.top(); s.pop(); cycle[item] = true; cnt--; } return cycle[here]; } 2) DFS int cnt; bool findCycleDfs(.. 2021. 2. 5. [기출] 산책하자 [문제] - N: 마을의 수 (2 ≤ N ≤ 100,000) - Ai: 이웃한 마을간 산책로의 수 (1 ≤ Ai ≤ 1,000,000,000 십억) - 산책을 출발하면 이웃한 마을로만 이동이 가능하며, 한번 지난 산책로는 다시 지나지 않는다. - 어떤 마을에서든 산책을 시작할 수 있고, 어떤 마을에서든 마칠 수 있다. [알고리즘] DP [Key Point] - 임의의 마을(Ai) 은 아래 세 가지 경우를 포함한다. . L[Back] + R[Back] : 좌우를 모두 다녀오는 경우 . L[Go] + R[Back] : 우측을 돌고 좌측으로 가는 경우 . L[Back] + R[Go] : 좌측을 돌과 우측으로 가는 경우 - 점화식: L[i][Back] = L[i-1][Back] + 짝수(r[i-1]) R[i][.. 2020. 12. 18. 기본 알고리즘 ▶ 트리 - 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 - 트리의 크기가 N일 때, 간선의 크기는 N-1 - 이진 탐색 트리: 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 ▶ 이진 탐색 - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 - 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 int binarySearch(int target, int start, int end) { while (start target) end = mid - 1; else start = mid + 1; } return -1; } - 직접 구현하지 않고 upper_bound / lower_bound 함수 사용 가능 int countByRange(int left, int rig.. 2020. 12. 14. 알고리즘 학습 [문제풀기] 정올 : 문제는 많지 않지만 표준적이거나 well-known 문제가 많고, fail 판정 시 그에 해당하는 반례를 보여줌 JUNGOL www.jungol.co.kr 백준 : 경쟁적으로 공부할 수 있고, 문제풀이가 블로그에 많이 올라와 있다. 알고리즘 분류 www.acmicpc.net [학습] - 알고리즘 설명 & 커뮤니티 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com - Visual Reference Code SW Expert Academy 1366*768 이상 해상도에 최적화되어 있으며 Google Chrome 브라우저를 권장합니다. (Internet Explorer 11 이상 지원) 본 사이트.. 2020. 10. 20. 이전 1 다음