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이 오는 경우의 수를 모두 합해..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 이러한 유형의 문제는 가능한 조건을 미리 정리해놓고 풀이하는게 더 좋은 방법인것 같다. 특히 첫번째 부터 규칙을 찾으려고 하면 번거롭기 때문에 적당히 i값을 0이 아닌 4,5 정도의 값을 설정하고(규칙에 따라 유동적으로) 앞의 원소들을 체크하면서 풀이해야한다. 위 문제의 조건을 바탕으로 가능한 경우는 3가지가 있다. 1. i 번째 포도주를 마시면서 i-2번째 포도주까지 마셔온 경우 (arr[i] +..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net split() 함수에 다음과 같이 문자열 인자를 주면 그 문자열을 기준으로 나눈 리스트를 반환한다. import sys print('10'.split('+')) print('10+20'.split('+')) 이 문제는 주어진 문자열을 ' '.join()함수로 먼저 한칸씩 띄어쓰기 문자열을 만든후 split()함수로 문자열을 리스트로 만든다. '12+34' -> ['1','2','+','3',..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net dp문제인데 왼쪽부터 더해주면서 큰수가 나올경우 dp배열에 넣어준다. import sys N=int(sys.stdin.readline()) M=list(map(int,sys.stdin.readline().split())) dp=[0]*N dp[0]=M[0] for i in range(1,N): dp[i]=max(M[i],dp[i-1]+M[i]) print(max(dp)) 왼쪽부터 숫자 하나씩 비교하면서 만약..

출처: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 위 문제는 기본적인 최단거리 찾기 문제이다. 나는 처음에 DFS로 접근해서 답이 나오지 않았다. 이 문제는 BFS로 풀어야 한다. import collections N,M=map(int,input().split()) q=collections.deque() q.append((0,0)) m=[] for _ in range(N): m.append(list(map(int,input()))) arr=[0]*M visited=[] ..

https://leetcode.com/problems/fibonacci-number/ Fibonacci Number - 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 fib(self, n: int) -> int: if N int: if n int: self.dp[1]=1 for i in range(2,n+1): self.dp[i] = self.dp[i-1] + self.dp[i-2] return s..