Google DSC Sookmyung

최근 코어멤버 남수연님의 'C++로 알고리즘 시작하기'라는 알고리즘 세션을 진행하면서 피드백을 받아보았는데요, 많은 분들이 궁금해하시는 부분 중 하나가 어떻게 알고리즘 학습을 시작했는지, 어떤 방식으로 알고리즘 스터디를 진행했는지 등 이었습니다. 알고리즘 스터디를 시작하시는 모든 분들께 조금이나마 도움이 되었으면 하는 바람에서, 저희 2020-2021 DSC Sookmyung 내부에서 진행한 알고리즘 스터디의 커리큘럼을 공유하고자 합니다. 어떤 자료로 학습하고 어떤 백준 문제를 풀었는지에 대한 글을 작성합니다. 알고리즘 공부를 처음 시작한 사람부터 약간 공부해본 사람들을 대상으로 진행했으므로 처음 공부하시는 분들에게 도움이 될 것 같습니다. 총 0주차부터 8주차까지, 각 주차마다 정해진 주제로 문제를 풀..

문제 (1260: DFS와 BFS) www.acmicpc.net/problem/1260 풀이 BFS와 DFS의 차이점을 기억하면서 풀자 DFS(Depth-First-Search) : 깊이 우선 탐색은 맹목적 탐색방법의 하나로 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. 참고하면 좋을 사이트 : swexpertacademy.com/main/visualcode/main.do#/home/editor/R/57c78219a4c12ab823c2fbd2 BFS(Breadth-First-Search) : 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 참고하면 좋을 사..

문제 (10816 : 숫자 카드 2) www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 정수가 하나씩 적혀있는 숫자 카드들이 있다. 상근이가 숫자 카드 N개를 가지고 있다. 또 다른 M개의 숫자 카드가 있는데, 각각의 숫자가 같은 카드를 상근이가 몇 개나 가지고 있는지를 출력하는 문제이다. 풀이 배열을 오름차순으로 정렬한 후, upper_bound(key) - lower_bound(key) 를 이용하면 key 값과 같은 요소의..

문제 (11726: 2xn 타일링) https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제다. 풀이 dp[n] = dp[n-2] + dp[n-1] 점화식을 유추할 수 있다. 소스코드 n = int(input()) dp = [0 for i in range(1001)] dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): dp[i] = (dp[i - 1] + dp[i ..

문제 (11866: 요세푸스 문제 0) www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤N)가 주어진다. 순서대로 K번째 사람을 제거하고, N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. N과 K가 주어지면, (N, K)-요세푸스 순열을 구하는 문제다. 풀이 queue의 FIFO(First-In-First-Out) 구조를 활용한다. queue에 1부터 N까지의 정수를 push 한다. K를 기준으로 그 앞의 수를 모두 순서..

알고리즘 스터디 3주차에는 선형 자료구조인 스택을 공부하고 스택 관련 문제들을 풀어보았습니다. 17608 막대기 [문제 링크] 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net [문제 요약] 높이가 각각 다른 막대기들을 왼쪽에서부터 오른쪽으로 일렬로 세웁니다. 그리고 나서 오른쪽에서 막대기들을 바라보면 오른쪽에 있는 막대기보다 높이가 낮은 막대기는 보이지 않습니다. N개의 막대기의 높이가 왼쪽에서 오른쪽으로 차례대로 주어지고, 오른쪽에서 바라봤을 때 보이는 막대기의 개수를 구하는 문제입니다. [풀이] 스택에 왼쪽에서부..

문제(2751: 수 정렬하기 2) https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 첫째 줄에 수의 개수 N이 주어지고, 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이를 오름차순으로 정렬하는 프로그램을 작성하라. 풀이 입력할 숫자의 개수인 N을 int(input())으로 입력을 받고, list 변수에 N개만큼의 숫자를 입력받아 저장한 후, sorted 메소드로 정렬을 하여 그 결과값을 출력하고자 하였다. N개의 숫자를 입력받을 때도..

문제(2309: 일곱 난쟁이) www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 총 9명의 난쟁이의 키가 주어진다. 이 난쟁이들 중 키의 합이 정확히 100이 나오는 경우에 포함되는 자들이 '진짜' 난쟁이들이다. 그렇게 해서 총 7명의 난쟁이를 찾는 것이 문제이다. 찾은 7명의 난쟁이들의 키를 오름차순으로 정렬해서 출력한다. 풀이 처음에는 9명 중 진짜 난쟁이 7명을 찾는 풀이를 생각했었다. 하지만 그것보다는, 차라리 현재 가짜 난쟁이들도 포함된 9명들의 키의 합에서 ..