YANGORITHM

문제 https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 풀이 문자열의 replace 함수를 이용해서 문자를 숫자로 바꾼다. 코드 python 1 2 3 4 5 6 def solution(s): num_dic = {"zero":"0", "one":"1", "two":"2", "three":"3", "four":"4", "five":"5", "six":"6", "seven":"7", "eight":"8"..

문제 https://programmers.co.kr/learn/courses/30/lessons/12977 코딩테스트 연습 - 소수 만들기 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 programmers.co.kr 풀이 조합을 통해 3개를 뽑아낸 후 합을 구해 소수인지 판단한다. 뽑아낼 수가 3개로 고정되 있어서 3중 for문을 활용해 문제를 해결할 수도 있다. 코드 python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 from itertools import combinations def setPrime():..

문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 다익스트라 알고리즘을 이용하여 최소비용을 구한다. 노드 간의 최단거리가 갱신될 때 부모 노드를 갱신해줘서 도착점과 시작점 사이의 길을 알 수 있게 만든다. 코드 python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ..

문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 www.acmicpc.net 풀이 특정 정점에서 모든 정점까지의 최소 거리를 구하는 문제이므로, 다익스트라 알고리즘을 이용하는 문제이다. https://..

문제 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 모든 간선의 비용이 동일하기 때문에 bfs 탐색을 통해 최단 거리를 찾을 수 있다. 시작점 x에서부터 bfs 탐색을 통해 모든 도시까지의 최단 거리를 구한 후에 k 값과 비교하여 답을 구한다. 코드 java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..

문제 https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 풀이 0이 연속되는 부분의 개수와 1이 연속되는 부분의 개수를 구해서 비교를 한다. 코드 python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 s = input() zero = 0 one = 0 state = s[0] if state == '0': zero += 1 else: one += 1 for i in s: if i != state: state = i if ..

문제 https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 풀이 사용할 수 있는 타일이 2 * 1(가로), 2 * 1 (세로), 2 * 2 세 종류이다. 왼쪽부터 차례대록 타일을 채운다고 생각하면서 점화식을 생각해본다. 길이가 i인 타일을 채워야 하고, i-1까지 타일이 채워져 있다면 2 * 1(세로)를 사용하면 된다. 길이가 i인 타일을 채워야 하고, i-2까지 타일이 채워져 있다면 2*1(가로) 두개를 사용하는 방법과 2*2 타일을 사용하는 방법이 있다. 따라서 다음과 같은 점화식을 만들 수 있다. a[i]..

문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 나무 높이의 범위가 엄청 넓으므로 이분 탐색을 통해 절단기의 높이를 정한다. 절단기의 최소 높이는 0이고 최대 높이는 나무들 중에 최대값과 같다. 이 사이에서 절단기의 높이를 찾으면 된다. 이분 탐색을 이용하므로 중간점을 절단기의 높이로 설정하면서 문제 조건 M을 만족하는지 확인한다. 1. 만약 중간점으로 잘랐을 때 가져가는 나무의 길이가 M보다 ..

문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 문제 조건 중 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고" 를 만족하기 위해 인접 리스트 형식으로 입력을 받은 후 정렬을 해줘야 한다. 그 후 dfs와 bfs를 진행 하면 된다. 코드 python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제 www.acmicpc.net/problem/17977 17977번: Triangulation A regular n-sided polygon P can be partitioned into n − 2 triangles by adding non-crossing line segments connecting two vertices of P. For example, a square can be partitioned into two triangles, a regular pentagon can be partitioned into three triangles www.acmicpc.net 풀이 각 정다각형에서 다음과 같은 답이 나온다. 1. 정육각형의 경우 내부에 정삼각형이 있어야 거리가 최소가 된다. 이때 최대거리..