문제요약 (2252. 줄 세우기) 키 순서가 주어질 때 키를 비교한 순서를 출력하라. 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이를 위한 부연 설명 같은 순서가 나올 때 관계가 없이 출력된다는 점에서 위상 정렬이 사용된다. 반드시 순환관계가 없는지 확인해야한다. 위상정렬에 대한 개념과 연관 문제는 다음 게시글을 참고하면 된다. [코테 알고리즘] 그래프 이론 / 관련 문제 본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문..

문제요약 ( 1920.수 찾기 ) 주어진 리스트에 원하는 값이 있는지 찾아 출력한다.. 풀이를 위한 부연 설명 정렬 알고리즘은 O(nlogn)의 시간 복잡도를 가진다. 이분탐색의 경우 O(nlogn)의 시간 복잡도를 가진다. 이분 탐색은 정렬된 데이터에 대해 실행할 수 있으므로 미리 sort()해야한다. 코드 import sys input = sys.stdin.readline num = int(input()) nums = list(map(int, input().split())) nums.sort() find = int(input()) finds = list(map(int, input().split())) for target in finds: first = 0 last = num - 1 isFind = F..

문제 요약 (2178. 미로 탐색) n * m 크기의 배열로 표현되는 미로가 주어질 때, (1, 1) 부터 (n, m)으로 이동하기 위해 지나가야하는 칸 수의 최솟값을 구해 출력한다. 배열의 n, m 모두 100 이하이기 때문에 시간 복잡도는 걱정할 필요는 없다. 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이를 위한 부연 설명 길찾기를 위한 표의 경우 45도 꺽어서 보면 그래프로 표현할 수 있다. 그래프의 문제의 경우 DFS와 BFS를 이용한 풀이 두 가지 모두 생각할 수 있다 그러나 해당 문제는 BFS를 통해 문제를 풀어야한다 완전..

문제요약 (2023. 신기한 소수) 소수 중에서 각 자리수 별로 나눠도 모두 소수라는 성질을 유지하는 소수를 찾아 출력한다. ex. 7331 -> 7331, 733, 73, 7 모두 소수 -> 우리가 구하고자 하는 수 정수를 입력 받고, 입력받은 정수 값의 자리 수만을 출력한다. 2부터 증가하면서 소수를 찾으면 시간초과에 걸릴 것이다. 다른 방법을 생각해봐야한다. 또한 뒷 자리수부터 숫자가 제거된다는 사실도 문제 해결의 키로 작용할 것이다. 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이를 위..

문제 요약 (11724. 연결 요소의 개수) 방향이 없는 그래프(양방향 그래프)의 노드와 간선이 주어졌을 때 연결 요소의 개수를 구하는 것이다. 연결 요소는 연결된 노드들의 뭉텅이라고 생각하면 문제를 풀기 편하다. ex. 1-5-2, 3-4, 6 이렇게 연결되어 있다면 연결 요소의 개수는 3이다. 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 풀이를 위한 부연 설명 입력되는 값들을 받아 그래프를 완성한다. 그래프 내에서 연결 요소를 찾아야하므로 ..