알고리즘/알고리즘

문제 링크 : https://leetcode.com/problems/linked-list-cycle/ 문제 연결리스트가 순환하는지에 대한 여부를 판별하는 문제 입력 head = [3,2,0,-4] 와 같은 연결리스트의 head를 함수의 매개변수로 준다. 출력 순환하면 true, 순환하지 않으면 false를 리턴 접근방식 floyd's tortoise and hare 이라는 알고리즘을 이용해서 해결했다. 한글로 번역하면, 토끼와 거북이라는 알고리즘인데, 2개의 포인터의 이동하는 속도가 다른 걸 이용해서 연결리스트의 순환 여부를 판단한다. 재밌는 알고리즘이다. 코드 bool hasCycle(struct ListNode *head) { struct ListNode* turtle; struct ListNode*..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12977 코딩테스트 연습 - 소수 만들기 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 programmers.co.kr 소수를 판별하는 방법만 알면, 비교적 간단하게 풀 수 있다. 소수를 판별하는 방법에서는 여러가지 알고리즘이 있지만, 여기서는 제곱근을 이용하는 방법을 사용했다. 제곱근을 이용한 소수 판별 어떤 곱으로 이루어진 수는 제곱근을 기준으로 대칭적으로 구성됩니다. 12를 예로 들어봅시다. 12의 약수는 [1, 2, 3, 4, 6, 12]..

문제 링크 : https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤..

탐욕 알고리즘(그리디 알고리즘) 탐욕 알고리즘 또는 그리디 알고리즘 이라는 것에 대해서 이야기 해봅시다. 탐욕 알고리즘은 주어진 순간 순간마다 가장 최선의 선택을 하는 알고리즘 설계 기법입니다. 매 순간마다 하는 선택은 최선이지만, 전체로 봤을 때는 최적의 선택이라는 보장을 하지는 않습니다. 그리디 알고리즘이 제대로 동작하지 않은 예시로 주로 드는 것은 마쉬멜로우 실험입니다. 예를 들어서, 지금 당장에 마쉬멜로우 1개를 받을 수 있지만, 10분을 기다린 경우 2개의 마쉬멜로우를 받을 수 있는 실험이 있다고 가정해 봅시다. 그리디 알고리즘으로는 지금 당장 1개를 선택하겠지만, 전체로 본다면 10분을 기다린 후에 2개의 마쉬멜로우를 받는게 가장 많은 마쉬멜로우를 받을 수 있을 것 입니다. 그리디 알고리즘은 ..