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번까지일 때 모든 도시에서의 왕복 시간..
www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이런 유형의 문제를 처음 보면 '이게 왜 BFS문제지?' 라는 의문이 든다. S층에서 G층으로 가는데 U칸 위로가거나 D칸 아래로 가야하므로 1. 처음에 visited[S]를 방문 처리를 해주고 q에 S를 넣는다. 2. q에서 pop한 뒤 x + U에 해당하는 칸에 방문한 적 있는지 확인하고 없으면 버튼을 누른 횟수를 1 증가시킨다. 3. 2번과 마찬가지로 x - D에 해당하는 칸에 방문한 적 있는지 확인하고 없으면 버튼을..
www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 이제는 무난한(?) BFS문제이다. 단지 3차원배열을 사용해 조금 귀찮을 뿐이다. 1. Test Case마다 m(빌딩상태), time(이동시간), visited(방문여부) 배열을 초기화해주고 m을 입력받는다. 2. m을 전체돌면서 'S'가 있는 칸의 좌표를 sz, sx, sy에 저장하고, 'E'가 있는 칸의 좌표를 ez, ex, ey에 저장한다. 3. bfs를 돌리면서 다음 칸으로 갈때마다 시간을 1씩 더해주고 큐에..
모르는 사이에 조금씩 조금씩..
