몰입하는 개발자 준비생 몰입하는 개발자 준비생

https://www.acmicpc.net/problem/1946요구사항시간 제한 2초N 메모리 제한 256MB100,000 * 4 = 40MB / 리스트당 다른 모든 지원자와 비교했을 때, 서류 심사 성적과 면접 시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않으면 합격.설계 1회의실 배정처럼 정렬하였지만 실패구현 1import sysinput = lambda: sys.stdin.readline().rstrip()test_case = int(input())def employment(candidate): maginot_line = 0 successful_candidate = 0 candidate = sorted(candidate, key=lambda x: (x[1], x[0])) ..

https://www.acmicpc.net/problem/11053요구사항 시간제한 1초N의 크기가 1,000 으로 작아 O(N**2) 까진 무리없다.메모리 제한 256MB 1,000 * 4  = 약 0.04MB수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하라.설계 1첫째 줄에 수열 A의 크기 N을 입력받는다.둘째 줄에 수열 A를 이루고 있는 Ai 를 입력받는다. 마지막 수열 안에 A[-1] 보다 작은 수를 카운트 한다. DP 테이블에 카운트 개수를 넣어준다.DP 테이블의 max 값을 출력한다.구현 1import sysinput = lambda: sys.stdin.readline().rstrip()N = int(input())A = list(map(int, input().split()))dp..

요구사항시간 제한 2초2억번 연산이 가능 . N**2 어려울 듯, 그 이하 시간복잡도를 사용메모리 제한 512MB리스트 안의 튜플 10,000개가 약 1.4MB 따라서 메모리 제한은 넣어둘것배낭에 들어갈 수 있는 무게를 초과하지 않는 선에서 가치가 가장 높은 최댓값을 출력설계배낭의 무게보다 무거운 아이템은 제외가치, 무게 순서대로 내림차순 정렬 (+ 근데 내림차순을 동시에 하면서 하나는 더 큰 값으로 다른 하나는 더 작은 값으로 할 수 있나?)아이템 리스트를 순회하면서 각 원소를 꺼냄만약 배낭 무게가 예를 들어 배낭의 무게가 3이고 아이템의 무게가 4라면elif 문에 안걸리게 된다. 아니다... 그러다 끝나겠지  for문이니깐... 아니라면, 각 아이템 무게가 현재 배낭의 무게보다 작다면배낭의 무게 -=..

https://www.acmicpc.net/problem/9084 요구사항시간 제한 1초 코인의 종류와 주어진 금액을 만드는 모든 방법, N과 M 따라서 O(N*M) 이 되겠다. 20 * 10000 이니 2만정도.. O(NlogN)정도메모리 제한 128MB메모리 제한은 128MB로 터지진 않을 거 같다. 이유는 리스트의 크기가 해봐야 dp 테이블 M+1 개, 이니깐.동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 세는 프로그램설계처음엔, 2차원 DP 테이블을 만들어서 하려고 하니 너무 복잡해서 다른 관점에서 보려고 노력했다. 따라서 동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 세는 함수의 로직은1차원 DP 테이블을 초기화 한다.  dp = [0] * (주어진 금액 + 1)dp..

요구사항시간 제한 0.75N이 최대 1,000,000 이기 때문에 O(NlogN) 까지 가능할 거 같다. 메모리 제한 256MB - 충분N이 주어졌을 때 가능한 모든 경우의 수를 카운트.모든 경우의 수 // 15746으로 나눈 나머지를 출력 설계피보나치 수열 확장판이다. N = 1일 때, 1N = 2일 때, 2N = 3일 때, 3N =4 일 때, 5따라서 bottom-up 방식으로 구현한다. 사용자로부터 입력을 받는다. dp테이블을 초기화해준다. 총 들어오는 입력값 + 1 만큼초기값 dp[1]과 dp[2]를 설정해준다.dp[2]의 경우는 if N > 1: 일 때 dp[2] = 2로 예외처리를 해주어야 한다.# if N > 1: 없는 경우N = int(input()) # N = 1dp = [0] * (N..

요구사항시간 제한 1초 N이 90이하 이므로 O(N^3) 까지 가능할 것. 메모리 제한 128MB N이 매우 작으니 신경 안 써도 될 것.N이 주어질 때, N번 째 피보나치 수를 출력한다.ex) N = 3이면, 0,1,1 -설계위 문제는 주관적인 생각으론 3가지 방법으로 풀어보고 싶다. 재귀함수사용자 정의 함수 안의 base case 설정 : N = 1일때 0을 N = 2일 때 1을 출력할 수 있게 한다.그 외 return 함수(N-1) + 함수(N-2) 를 할 수 있도록 한다.  Top-Down위 방식은 큰 문제를 작은 단위의 문제로 나누어 쪼개는 동적계획법 알고리즘 설계 방법 중 하나이다. 동적 계획법 즉, DP는 메모제이션을 사용한다. 메모제이션이란,,, 냉장고라고 생각하면 된다. 마트까지 가지 않..

2주차를 마치며, 2주차 알고리즘 테스트를 끝으로 2주차도 끝이 났다. 2주차를 한 문장으로 요약하자면, 요령이 없었고 그걸 오늘 깨달은 걸 다행이라고 생각하지 않고 짜증난다!!!!!!   그래도 좋았던 점을 시작으로 회고를 시작해보려 한다. 한 주동안 가장 기억에 남는 건 역시 러닝이다. 매일 6시에 일어나서 운동장을 5-6바퀴 돌았다. 운동장을 돌며 좋았던 점은 안한 날을 예로 들면 좋다. 안한 날의 경우는 강의실에 도착해도 머리가 바로 돌아가지 않았는 데, 러닝을 한 날에는 앉자마자 집중할 수 있어 좋았다. 또 2주차를 마무리하며 내가 뭘 잘했냐 생각해보면, 내가 공부했던 건 확실하게 머리 속에 넣었다는 점이다.   이제 반성의 시간을 가지자면... 알고리즘 테스트를 보며 스스로에게 제일 짜증났던 ..

요구사항시간제한N이 10만개 까지 가능하니 O(N) 이여야 한다. 메모리 제한 256MB 루트 노드는 1번이다.루트 노드를 제외한 노드들의 부모를 출력해라.2~7번 노드의 부모 노드를 한 줄에 하나씩 출력설계노드 개수 N을 입력 받는다.인접한 노드들을 N-1 개 입력 받는다.parent 값을 넣을 리스트를 초기화 한다. dfs 함수를 만든다.단, 여기서 인자로 들어간 노드가 부모 노드이다. 1이 루트 노드이니 dfs(1) 을 해주자.for 문을 통해 parent 리스트를 한 줄에 하나씩 출력하자.단, parent의 0, 1 번 인덱스를 제외0번과 1번은 빈 리스트이기 때문에.왜? 0번은 숫자 맞추려고1번은 루트 노드이기 때문에 부모가 없다. 구현import syssys.setrecursionlimit(1..