CS STUDY

https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 이 문제는 딕셔너리에 대해서 좀더 명확하게 이해할수 있게 만들어준 문제이다. 딕셔너리를 만든후 딕셔너리 구조를 d[key]: [단어개수, 단어길이, 단어] 로 구성한다 1. 정렬 파이썬의 sort및 sorted 함수는 key 인자 값으로 정렬에 있어서 우선 순위 기준을 설정 할 수 있다. sort(key= lambda x: (기준..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 간단해 보이지만 간단히 완전탐색으로 풀면 시간복잡도가 최악의 경우 n! 이 되기때문에 스택을 써야한다 또한 인덱스를 저장해야하기 때문에 스택안에 리스트가 들어가는 구조로 풀어줘야 한다. import sys N=int(sys.stdin.readline()) tower=list(map(int,sys.stdin.readline().split())) stack=[] ans=[] for i in rang..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 이 문제는 BFS 문제이긴 하지만 한가지 조건이 있다. 바로 graph에서 1(벽)인 부분을 깨고 진행할 수 있다는 점이다. 그러므로 visited 배열을 잘 사용해야 하는데 최단거리를 저장하는것이 아닌 1이 만났을때만 count를 올려주는 방법이 좋다. 또한 graph 내에서 0들만 먼저 탐색할 수 있도록(벽을 최소한 부신다고 했다) appendleft 함수를 사용해서 탐색..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net DFS를 사용해 트리를 추적하는 문제이다. 먼저 말단 노드까지 도착한 뒤 올라오면서 왼쪽 오른쪽 자식 노드들의 길이와 합을 구한다. 트리의 지름은 무조건 왼쪽 최장경로 + 오른쪽 최장경로 이다. DFS로 리프 노드까지 내려간 뒤 해당 노드의 가중치를 리턴한다.그리고 자식 노드가 있는 부모 노드부터는 자식들의 경로들 중 가장 큰 두 길이를 선택한다.두 길이를 더한 것은 현재 노드..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 처음에 숫자를 일일히 써가면서 규칙을 찾는데 엄청 고생했는데 다음과 같이 풀이하는 방법이 더 효율적이다. 위 표는 마지막 자리 숫자가 무엇일때 생성될수 있는 가지수를 적어놓은 것이다. 예를 들어 dp[2][1]은 21 이렇게 하나밖에 존재 하지 않고 dp[2][3]은 23,43 두개가 존재한다. 위처럼 작성해 놓으니 규칙을 쉽게 발견할수 있는데 빨간 화살표처럼 왼쪽 오른쪽 대각선 원소의 합이다. 생각해보면 당연한게 5가 맨 뒷자리에 오려면 앞에 4나 6이 와야 하기 때문에 4나 6이 오는 경우의 수를 모두 합해..