취업을 준비하며 정리하는 컴퓨터 지식 (55) 썸네일형 리스트형 [Algorithm] 유클리드의 호제법은 뭐야? 두 정수 또는 두 정식인 a와 b가 있을 때, a를 b로 나눈 나머지 a'로 b를 나누고 그 나머지로 a'를 나누는 일을 완전히 나누어질 때까지 계속하여 a와 b의 최대 공약수를 구하는 방법. 단, a, b가 자연수일 때 a>b, 다항식일 때는 a의 차수가 b의 차수 이상이어야 한다. - 네이버 '유클리드의 호제법' 사전 정의 위의 정의에서는 아래의 조건이 만족해야 한다. a, b는 자연수이다. a > b가 만족한다. 유클리드의 호제법은 다음의 과정을 실행한다. a, b는 자연수(a > b), value = a % b이다. b!= 0 이 되기 전까지 a % b 연산을 실행한다. a에 b의 값을 대입하고, b에 value값을 대입한다. 1의 과정을 반복한다. 다음은 위의 과정을 그림으로 표현한 것이다. 다.. [Problem Solving] 백준 1916번 최소비용 구하기 문제풀이 백준 1916번 최소비용 구하기 문제 해설 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 모든 도시의 이동 비용이 양의 정수이고, 시작 지점에 대한 정보도 있으므로 해당 문제는 다익스트라 알고리즘을 활용하여 해결하면 된다. 다익스트라 알고리즘에 대한 설명은 다음을 참조하면 된다. 다익스트라 알고리즘 개념, 다익스트라 알고리즘 실습 다익스트라 알고리즘을 활용하여 코드를 작성하면 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19.. [Problem Solving] 백준 1092번 배 문제풀이 백준 1092번 그리디 문제에 대한 풀이를 알아보겠습니다. 문제 해설은 링크를 연결해두었으니 확인하시기 바랍니다. 백준 1092번 배 문제 해설 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 물건을 옮기는데 최적의 방법은 가장 무거운 것을 들 수 있는 크레인이 가장 무거운 박스를 옮기는 것이다. 방법은 다음과 같다. 각 크레인과 박스를 무게에 맞게 내림차순 정렬시켜준다. 크레인이 들 수 있는 가장 무거운 박스를 옮긴다. 모든 크레인에 대해서 해결했다면 시간을 1 올려준다. 2의 과정을 반복한.. [ProblemSolving] 백준 2589번 보물섬 문제풀이 백준 2589번 BFS 문제에 대한 풀이를 알아보겠습니다. 문제 해설은 링크를 연결해두었으니 확인하시면 됩니다. 백준 2589번 보물섬 문제 해설 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 보물이 있는 위치는 서로 간에 최단 거리로 이동했을 때 가장 이동 시간이 긴 육지 2곳에 있습니다. 가장 긴 이동 시간을 가진 육지를 찾는 방법은 각각의 육지에서 다른 육지로의 거리들을 비교하여 최댓값을 저장하는 방식을 활용하면 될 것입니다. 따라서 해당 문제는 브루트 포스와 너비 우선 탐색을 이용하여 해결할 수 있습니다.. [Algorithm] 에라토스테네스의 체는 뭐야? 에라토스테네스의 체는 소수의 배수들을 지우면서 소수를 찾는 방법이다. 해당 알고리즘에서 중요한 점은 만약 1부터 150까지의 소수를 구하고 싶다면 13^2 > 150 이므로 13보다 작은 수의 배수들만 지워주면 된다는 것이다. 에라토스테네스의 체는 다음의 과정으로 진행된다. 구하고자 하는 소수의 구간을 n, √n을 m이라고 한다. n개의 배열을 생성해준다. 2부터 m+1까지의 숫자들 중에 계산되지 않은 값을 확인한다. 계산되지 않은 값이 있다면 해당 값의 배수들을 계산 처리하고, 2번의 과정으로 돌아간다. 계산 처리되지 않은 값들을 출력한다. 위의 과정을 코드로 구현하면 다음과 같다. 1 2 3 4 5 6 7 8 9 10 def primeNumber(n): sieve = [True] * n m = int.. [ProblemSolving] 백준 2667번, 프로그래머스 64061번 문제풀이 백준 2667번 DFS 문제와 프로그래머스 64061번 구현 문제에 대한 풀이를 작성하겠다. 각각의 문제 해설은 링크를 연결해두었으니 확인하면 된다. 백준 2667번 단지번호붙이기 (DFS) 문제 해설 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 단지의 수를 세어야 하기 때문에 깊이 우선 탐색을 사용하여 구현하면 된다. 깊이 우선 탐색의 과정은 다음과 같다. 아파트가 있고, 아직 방문하지 않은 곳을 탐색한다. 방문 처리를 하고, 아파트의 수를 세어준다. 왼쪽, 오른쪽, 위, 아래의 방향으로 가상으로 이동한다.. [Algorithm] 브루트 포스는 뭐야? 브루트 포스 알고리즘은 가능한 모든 경우의 수를 하나씩 확인해보는 알고리즘이다. 모든 경우의 수를 탐색하는 과정에서는 막대한 자원과 시간이 소모되지만 모든 경우의 수를 하나씩 확인해본다는 것은 100%의 정답을 도출할 수 있는 방법이기도 하다. 백준 2231번 문제를 예시로 확인해보자 문제 해설 문제를 확인하기 위해서는 주어진 수를 n, 계산 중인 값을 m이라 할 때 다음의 과정을 따른다. m의 각 자릿수와 자기 자신을 더한다. 해당 값과 n을 비교한다. 2번 과정이 참이면 결과를 출력하고 종료한다. 2번 과정이 거짓이면 m을 1 더해주고 1의 과정으로 돌아간다. 모든 과정이 끝나도 출력 값이 없다면 0을 출력한다. 다음은 "216"을 계산 중인 값을 그림으로 표현한 것이다. 위의 그림에서 볼 수 있듯이.. [ProblemSolving] 프로그래머스 60057번 문자열 압축 문제풀이 모든 경우의 수를 탐색하여 정답을 도출하는 완전 탐색 유형의 문제이다. 다음은 문제를 풀 수 있는 사이트 링크이다. 프로그래머스 60057번 문제 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자 programmers.co.kr 길이가 n인 문자열을 입력받아 문자열 단위를 나누어서 같은 문자열이 몇 개씩 나왔는지 확인하는 문제이다. 여기서 중요한 점은 문자열 단위를 나눌 때 n//2+1 이상으로 나누면 같은 문자열이 나오지 않으므로 n//2+1까지의 문자열 단위에 대해서만 탐색을 시행하는 것이 좋다. "aabbaccc"를 이용하여 설명해.. 이전 1 2 3 4 5 6 7 다음
