programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 1. 먼저 triangle 배열과 같은 모양의 dp 2차원 배열을 만든다. 2. 마지막 줄부터 올라갈 것이므로 dp의 마지막줄은 triangle의 마지막 줄과 같게 만들어준다. 3. 마지막에서 두번째 줄부터해서 dp[i][j]에 (밑의 두 숫자 중 큰 값 + triangle[i][j]값)을 넣어준다. 4. 최종적으로 맨 윗줄에 최댓값이 저장되므로 dp[0][0]을 return해준다. def solution(triangle): length = len(t..
programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 스택이 개념은 쉬운데, 마스터하기는 매우 어려운 자료구조인 것 같다. (나만 그런가..) 스택을 활용해 푸는 문제들이 유독 어렵게 느껴진다... 1. answer에 len(prices)-1부터 0까지 넣어준다. prices길이가 5이면 answer = [4, 3, 2, 1, 0] 2. prices가 [1, 2, 3, 2, 3]일 때, ..
programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 처음에 numbers에 있는 숫자들에 대해 모든 경우의 수를 구해야 한다. 이 문제를 풀고 나서 다른 사람들의 풀이를 보니 다양한 방법이 존재했다. 나는 itertools모듈의 permutations함수를 사용했다. 1. numbers에 있는 숫자를 num배열에 넣고 dab에도 넣어준다. (한자리 수는 따로 처리) -> permutations(num, 1)을 하..
programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 백준에서 많이 풀어본 그래프 문제들과 비슷하다. 처음에 DFS로 풀어보려다 실패하고 BFS로 풀었다. from collections import deque def solution(n, edge): graph = [[] for _ in range(n+1)] dist = [0] * (n+1) visited = [False] * (n+1) q = deque() q.append(1) visited[1] = True for i in edge: graph[..
www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 앞서 올렸던 위상정렬 알고리즘을 응용해서 푸는 문제이다. 1. M만큼 X, Y를 입력받고 graph[X]에 Y를 append해주고, indegree[Y]에 1을 더해준다. 2. K만큼 반복문을 돌며 건물을 짓거나 파괴합니다. 3. 만약 command가 1이라면 building번 건물을 짓고자 하는 것이므로 indegree[building]을 확인한다. 3-1. indegree[b..
www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 전형적인 위상정렬 문제이다. 위상정렬 알고리즘은 추후에 한 번 포스팅 할 예정이다. 1. N, M을 입력받고 M번 만큼 A와 B를 입력받는다. 2. A가 B 앞에 줄 서야 하므로 graph[A]에 B를 append해주고 indegree[B]에 1을 더해준다. (indegree 배열: 진입차수) 3. indegree[1]부터 indegree[N]까지 돌며 진입차수가 0인 노드를 큐..
www.acmicpc.net/problem/11946 11946번: ACM-ICPC 대회가 끝난 후 팀 별 성적을 순위에 따라 출력한다. 만약 순위가 같으면 팀 번호가 빠른 것을 먼저 출력한다. 각 팀마다 팀 번호, 푼 문제 수, 총 시간을 출력한다. www.acmicpc.net 단순 구현문제이지만, 생각보다 빡세서 포스팅해본다. 일단 입력값이 많고, 그에 대한 순서 처리가 생각보다 힘들다. 1. dic이라는 딕셔너리를 만들고 미리 1번팀의 1번문제 결과부터 n번팀의 m번 문제결과 까지 [0, -1]을 만들어 놓는다. (주석에 설명했듯이 '틀린횟수'와 '총 시간'이다) 2. q개의 로그를 입력받는다. 만약 log[3]이 'AC'가 아니라면 틀린 것이므로 해당하는 팀의 문제결과인 dic[dic[(int(l..
www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net N이 100이하이므로 O(N^3)인 플로이드-와샬 알고리즘을 사용해도 통과가 될 것 같아서 풀어보았다. 1. M개 만큼 a와 b를 입력받고 a와 b사이의 거리를 1로 cost배열에 넣어준다. 2. 플로이드-와샬 알고리즘을 통해 각 건물 사이의 거리를 구해준다. 3. 브루트포스 방식으로 치킨집이 1번,2번일 때 부터 1번,3번 ... N-1번,N번까지일 때 모든 도시에서의 왕복 시간..
모르는 사이에 조금씩 조금씩..
