[Algorithm] 그리디 알고리즘

그리디 알고리즘(탐욕법)이란 ?현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올 릴 수 있는 능력을 요구합니다. 그리디 해법은 그 정당성 분석이 중요합니다. 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다. [문제상황]  루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다.  Q. 단순히 매 상황에서 가장 큰 값만 고른다면 어떻게 될까요?  일반적인 상황에서는 그리디 알고리즘은 최적의 해를 보장할 수 있을 때가 많습니다.  연습문제 1. 거스름돈 : 정당성 분석 https://www.acmicpc.net/problem/5585   최적의 해를 빠르게 구하기 위해 ..

• format_list_bulleted Algorithm
• · 2024. 4. 30.

[Algorithm] 프로그래머스 - OX퀴즈

https://school.programmers.co.kr/learn/courses/30/lessons/120907 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡문제풀이 (접근방식) 1. 'X [연산자] Y= Z ' 형태인 문자열을 하나씩 꺼낸다. 2. '=' 을 기준으로 분리한다. 3. X, [연산자] , Y를 공백기준으로 분리하고 , X,Y,Z를 int 형으로 변환해준다. 4. 만일 연산자가 '+(-)' 라면 x+y(x-y) 를 계산하여 결과를 반환한다. 5. 만일 계산결과가 Z와 동일하다면 정답에 'O' , 아닐경우 'X' 를 추가해준다. def..

• format_list_bulleted Algorithm
• · 2024. 4. 23.

[Algorithm] 배열과 리스트

✍️ 해당 포스팅은 https://www.youtube.com/watch?v=_hP21RzyqHA 강의자료를 참고하여 작성하였습니다. 1. 배열 배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 구조입니다. 인덱스를 사용하여 값에 바로 접근할 수 있습니다. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵습니다. (값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요합니다. ) 배열 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없습니다. 2. 리스트 리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료입니다. 노드는 컴퓨터과학에서 값, 포인터를 쌍으로 갖는 기초 단위를 부르는 말입니다. 인덱스가 없으므로 값에 접근하려..

• format_list_bulleted Algorithm
• · 2024. 4. 16.

[Algorithm] 시간복잡도

해당 포스팅은 https://www.youtube.com/watch?v=DYA2q0oX5CA 강의자료를 참고하여 작성하였습니다. 1. 시간 복잡도란? 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 연산 횟수는 1초에 2,000만 번 연산하는 것을 기준으로 생각합니다. 2. 시간 복잡도 정의 빅-오메가: 최선일 때(best case)의 연산 횟수를 나타낸 표기법 빅-세타 : 보통일 때(average case)의 연산 횟수를 나타낸 표기법 빅-오 : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 코딩 테스트에서는 빅-오 표기법을 기준으로 수행시간을 계산하는 것이 좋습니다. 3. 시간 복잡도 활용하기 ① 알고리즘 선택의 기준으로 사용 e.g. 백준 온라인 저지 2750번 https://ww..

• format_list_bulleted Algorithm
• · 2024. 4. 15.