수치해석 뉴턴법/뉴턴-랩슨법 정리방정식의 해를 구할 때 중고등학교 때는 근의공식과 조립제법을 이용해서 해를 구했었는데요. 정확해 해를 구할 수 없는 경우 해에 근접한 근사해를 찾아 구하는 방식 중 하나인 뉴턴법에 대해 알아보겠습니다.근사해를 구하는 이유대수적으로 모든 방정식의 해를 구하면 좋겠지만 안타깝게도 수학이란 세계에는 수많은 방정식이 있지만 해를 단번에 구할 수 있는 근의 공식은 4차까지밖에 없습니다. 5차 이상의 방정식은 근의 공식이 없기 때문에 인수분해가 잘 된다면 해를 구할 수 있겠으나 대개는 방정식의 해를 정확하게 구할 수가 없습니다.근의공식이 없는 상황에서 정확한 해를 구하는 건 무모한 작업이기 때문에 정확한 해가 아니라 충분히 사용할만한 근사해를 구해서 오차범위 안에서 해라고 가정하고 ..
동적 계획법이란? 동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 간단한 여러 개의 하위 문제(subproblem)로 나누어 푸는 알고리즘 기법 중 하나입니다. DP는 부분 문제의 결과 값을 저장해놓고 재활용하여 전체 문제를 해결하는 방식으로 동작합니다. 동적 계획법의 조건 DP는 크게 2가지 조건을 만족해야 합니다. 작은 부분 문제들이 반복되어 나타나는 구조여야 합니다. 한 부분 문제에서의 정답이 다른 부분 문제에서의 정답을 결정하는 데 영향을 미쳐서는 안 됩니다. 동적 계획법의 절차 DP 알고리즘은 일반적으로 다음과 같이 세가지 절차를 따릅니다. 주어진 문제를 작은 부분 문제로 분할합니다. 부분 문제의 해결을 위해 이전 단계에서 구한 값을 저장하고 재귀로써 문제를 해결합니다...
리스트에서 특정 문자 있는 경우 제거하는 방법입니다. 조건 걸어서 하나씩 지우면 되긴 하는데 이게 될 때가 있고 안 될 때가 있더군요. 그래서 다른 방법을 추천하는 글입니다. 보통 for문으로 제거하려고 할텐데 if 문 써서 리스트 원소의 문자열에 해당 문자가 있으면 remove를 통해 지우려고 할 겁니다. 저도 그렇게 했고요. 그래서 아래와 같이 for문으로 합니다. 그럼 그냥 안된다고 봐야 합니다. search = 'temp' for word in file_list: if search in word: print('원소 제거: ' + word) file_list.remove(word) print(file_list) 전혀 지워지지 않습니다. 그 이유는 인덱스 문제로 remove의 방식 때문인데 인덱스가 ..
요즘 알고리즘 공부를 하고 있는데 어찌나 귀찮은지 게으른 생활이 계속되는 것 같습니다. 심심풀이로chatGPT에게 알고리즘 공부를 하는 이유를 물어보았습니다. \ 알고리즘 공부를 해야하는 이유는 무엇인가요? 한글로 해봤더니 확실히 느리고 쓰다 마네요. 타임제한이 있는 것 같습니다. 두번이나 continue를 했습니다. chatgpt는 여러가지 이유가 있지만 큰 맥락은 프로그래밍 스킬향상과 문제해결 능력 향상된다. 문제를 정의하는 기술이 생긴다는 얘기가 주였던 것 같습니다. 알고리즘 공부 하는 방법을 3가지로 요약해주세요 chatgpt에게 알고리즘 공부방법을 3가지로 얘기해달라고 했더니 다음과 같이 3가지로 얘기했습니다. 1. 연습 반복 2.책이나 강의를 통해서 배운다. 3.다른 사람과 협업하고 프로젝트 ..
선택정렬이란? 선택정렬은 아주 단순한 정렬 알고리즘입니다. 최소값을 찾은 후 맨 앞에 데이터와 교체하는 것을 반복하는 방법입니다. 당연히 정리가 끝난 인덱스 이후로 반복해야합니다. 다시 처음부터 하면 안됩니다. 내가 최소값을 선택한 후 그걸 맨 앞으로 끌어오는 작업만 하면 됩니다. 그래서 선택정렬이라고 하는게 아닌가 싶습니다. 출처: https://en.wikipedia.org/wiki/Selection_sort 알고리즘 구현 선택정렬은 최소값을 선택하고 지정한 리스트의 앞의 값이랑 비교를 해야합니다. 맨 앞에 있는 값과 최소값을 비교해 작으면 바꿉니다(swipping) 예를 들어, 데이터가 3개 [16,3,8]라면 처음 한 번 실행할때 [16,3,8]의 최소값인 3과 맨 앞값인 16을 앞으로 넣습니다...
요즘 알고리즘을 공부중인데 로직만으로는 뭔가 답답하네요 ㅜ 알고리즘 진행을 눈으로 보고 싶다는 생각이 굴뚝 같습니다. 그래서 구글링을 해봤더니 있었습니다. 정렬 알고리즘만 확인할 수 있지만 그래도 눈으로 확인할 수 있어서 속이 시원합니다. 물론 위키백과에서 정렬 알고리즘 치면 그림으로 나오긴 하는데 하나씩 봐야하는 단점이 있어서 제가 찾는 건 아니었습니다. 저는 한꺼번에 알고리즘을 보면서 비교해보고 싶었습니다. visualgo 으로 가면 알고리즘 진행과정을 확인할 수가 있습니다. 사이트 바로가기 : https://visualgo.net/en/sorting?slide=6-8 Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - Vi..
삽입정렬 삽입정렬은 데이터 중 하나를 뽑아서(A) A 앞에 있는 데이터(B)와 비교해 $ A 앞 데이터 6보다 작음 -> [1,6,4,2] 4 뽑음 -> 앞 데이터 6보다는 작고 1보다 큼 -> [1,4,6,2] 2 뽑음 -> 앞데이터 4,6 보다 작고 1보다 큼 -> [1,2,4,6] 여기서 주의할 것은 계속 2번째 인덱스만 뽑지 않도록만 하면 됩니다. 계속해서 다음 인덱스로 넘어간다고 생각해야 합니다. 굉장히 중요합니다. 삽입정렬 알고리즘을 코드로 구현시 꼬이기 쉬운 부분입니다. 아무튼 순회횟수 +1 인덱스로 앞데이터와 하나씩 비교를 합니다. 버블 정렬에서는 뒤부터 정렬이 완성된 것에 반해 앞에서부터 하나씩 정렬이 됩니다. 데이터길이 비교 최대순회횟수 2 1 1 3 2 2 4 3 3 버블정렬과 같습니..
알고리즘 이론의 정렬에 대한 내용입니다. 프로그램 작성시 정렬을 세우는 건 아주 중요하고 빈번한 일입니다. 간단한 프로그램을 만들 때는 파이썬 내장 함수로 정렬이 가능하니 큰 필요성을 못 느낄 수 있는데 큰 프로그램을 만들거나 새로운 문제가 나타날 때 정렬 알고리즘을 알고 있지 않으면 역량부족으로 한참 해맬 수도 있습니다. 정렬 알고리즘은 알고리즘 파트 중에서 쉬운 편에 속해서 기초로 알고리즘이라는 분야를 입문하기 좋은 파트이므로 시간을 내서 배워보시는 것을 추천드립니다. 이번 포스팅에서는 버블 정렬에 대해 소개하겠습니다. 버블정렬 정렬은 데이터가 있을 때 이를 정해진 순서대로 나열하는 것을 의미합니다. 손으로 쓰면 너무 쉽겠지만 컴퓨터는 그게 아니라서 알고리즘을 짜서 데이터를 정렬할 수 있게 해주어야 ..
재귀용법이란? 함수 안에서 동일한 함수를 호출하는 방법으로 여러 곳에서 응용되니 익숙해져야 할 용법입니다. 재귀 호출의 동작방식은 함수 내부에서의 스택이라고 볼 수 있는데 함수의 결과값 위에 또 다른 결과값을 얹히는 방식으로 알고리즘이 진행됩니다. 그후에 맨 위에 값부터 리터하고 값을 넘겨줍니다. 얹는 과정을 Call function 결과값을 리턴하는 과정을 Returning values 라 했습니다. 실제 코드가 어떻게 돌아가는지 볼 수 있는 사이트가 있는데 아래 링크로 남겨놓겠습니다. 알고리즘의 진행순서가 어떻게 되는지 살펴보시기 바랍니다. https://pythontutor.com/visualize.html#mode=display 재귀용법의 제한 재귀용법을 무한정 쓸 수 있다면 반복문은 필요하지 않..
해쉬테이블(HashTable)은 주어진 공간에서 값을 저장하게 되면 충돌이 일어나게 됩니다. 이를 처리하는 기법 2가지를 소개합니다. 사실 더 많은 방법이 있는데 어짜피 파이썬에서는 딕셔너리로 다 커버가 되기 때문에 연습용으로 보시면 좋을 것 같습니다. 아래 내용을 보시면 공간의 제약이 거의 없는 딕셔너리의 장점이 얼마나 큰지 느끼실 수 있을겁니다. 참고로 실제 딕셔너리처럼 key값을 잘 정리하지는 않았습니다. 해쉬테이블이 충돌하는 이유 데이터는 많은데 공간은 제약되어있다면 충돌이 일어날 수밖에 없습니다. 예를 들어, 데이터가 만약 9개가 있고 공간이 8개까지밖에 없다면 해쉬테이블의 원리상 무조건 1개 이상은 충돌이 일어날 수밖에 없습니다. 공간을 넓힐 수 있다면 최대한 넓히는 게 좋지만 현실세계는 메모..