알고리즘 예제

점의 위치 구하기

점의 위치 구하기
점의 위치를 입력받았을 때 그에 따른 평면의 사분면을 결과로 반환하는 문제

def solution(dot):
	if dot[0]>0:
    	if dot[1]>0:
        	return 1
        else:
        	return 4
    else:
    	if dot[1]>0:
        	return 2
        else:
        	return 3

위 해답처럼 사용해도 문제해결은 문제가 없지만 삼항연산자를 통해 코드의 길이를 줄여보기로 했다.

def solution(dot):
    return (1 if dot[0]>0 else 3) if dot[0]*dot[1]>0 else (4 if dot[0]>0 else 2)

삼항연산자를 중첩하여 return을 4개 사용한 코드를 한 줄로 구현하였다.

---

예습

그리디 알고리즘

예제 - 거스름돈

현재 상황에서 지금 당장 좋은 것만 고르는 방법
매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

주의 사항

• 그리디 알고리즘은 문제의 정당성에 대한 분석을 해야한다.
• 가장 좋아 보이는 것을 선택한다고 해서 그것이 최적의 해를 구하는 방법이라고 확신할 수 없다.

예제에서 잔돈이 500, 400, 100 이라면 800원을 거슬러 줄 때 그리디 알고리즘은 500, 100x3의 결과가 나오지만 최적의 해는 400x2이다.

---

완전 탐색

Exhaustive Search

모든 경우의 수를 시도하는 방법

• Brete-Force

  • 평소에 사용하는 반복문과 조건문을 사용하여 모든 경우를 확인하는 방법

• 비트마스트(Bitmask)

• 재귀함수

• 순열

• BFS, DFS

---

알고리즘 문제는 30개 정도 풀었지만 아직은 난이도가 쉬운 것 같다.
난이도가 쉬워서 삼항연산자를 사용해서 코드도 줄여보았다.(여러운 문제는 코드를 극한으로 줄일 시간도 없고 다시 봤을 때 이해도 못함....)
발제를 보고 내일 있을 알고리즘을 간단히 예습해보았다. 오늘 강의는 녹화본이 올라오면 복습하면서 정리할 예정이다.