본문 바로가기

Programming

(56)

[Algorithm] 플로이드 와샬(Floyd Warshall) 알고리즘(ft.파이썬) 🚩 플로이드 와샬 알고리즘 파이썬 구현 플로이드 와샬은 다익스트라 알고리즘과 같이 최단거리 혹은 최소비용을 구하는 알고리즘입니다. 플로이드 와샬은 다익스트라 알고리즘과는 달리 모든 노드에서 다른 모든 노드들까지의 최소 거리(혹은 최소비용)을 구하기 때문에 "어딘가를 경유한다."라는 조건이 주어질 때, 사용을 고려하기 좋은 알고리즘 입니다. 다만, 출발점(s), 도착지점(e), 경유지(p)에 모든 노드를 고려해야하므로 시간 복잡도는 O(N^3)으로 큰 편 입니다. 즉, 문제에서 주어진 노드(N)의 최댓값을 고려해 미리 계산해 사용할 가치가 있는 알고리즘인지 고려해봐야합니다. ✏️ 플로이드 와샬 알고리즘 위 그림의 경우는 출발지점이 1번 노드, 도착지점이 4번 노드인 경우 입니다. 1 -> 4로 가는게 경유..

[Algoritm] 행렬 회전 (Python 구현) 프로그래머스에서 제공하는 카카오 2020년 신입 개발자 블라인드 코딩 테스트 1차 문제 3번을 풀어 보았다. https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 해당 문제는 어떤 알고리즘을 사용할 것인가를 알아내는 것보다 구현력이 필요한 문제였다고 생각한다. 해당 문제의 경우 제한 사항의 크기가 작기 때문에 모든 경우를 확인하는 완전 탐색으로 풀이가 가능한데, 행렬의 회전과 범위를 설정하는 것이 중요했다. 문제를 해결하기 위해서는 2차원 행렬의 회전을 구현해야 ..

[Algorithm] 최대 공약수, 최소 공배수 구하기 GCD(Greatest Common Divisor) 최대 공약수 구하기 유클리드 호제법 사용 def gcd(a, b): while b: a, b = b, a % b return a a = b x q + r 이라고 했을 때, GCD(a, b) = GCD(b, r)를 만족한다. 간단 증명: 수학적으로 증명하는 방법이 있지만 이해를 위해서 간단히 설명하자면 아래와 같이 표현할 수 있다. b = r x m + n으로 표현할 때, n이 0이라면 b = rm으로 표현된다. 즉, b와 r의 최대 공약수 GCD(b, r) = m이 된다. a = bq + r = rmq + r = r(mq + 1) 이므로 GCD(a, b) = r 이다. => GCD(a, b) = GCD(b, r) = GCD(r, 0) = r LCM(Lo..

[Java] 자바에서 인자의 실제 값이 변경되는 이유 Java는 인자로 넘겨준 객체의 값을 변경하면 해당 객체의 실제 값이 변경된다. add 함수는 인자로 받는 model 객체 안의 number 필드의 값을 1 더하는 함수이다. 처음에 있는 model 객체를 add 함수의 인자로 넘겨서 실행하면 처음 model의 필드 값이 변경된다. C언어나 python에서 함수에 인자를 넘기면 실제 값(혹은 객체의 주소 값)이 아닌 인자의 값을 복사 값이 넘어간다. 이렇게 원본의 복사 값을 인자에 넘겨주는 방법을 "Call By Value"라고 부른다. 실제로 원본 A를 변경하기 위해서 add함수의 return 값인 B 다시 대입해줄 수 있다. Model model = new Model() model = add(model)// add 함수의 return은 Model cl..

[42 Seoul] Norminette 설치하기(ft. Homebrew) Norminette는 42 아카데미에서 사용하는 문법 규칙 프로그램입니다. 이 글은 개인 로컬 환경에 norminette를 설치하는 방법을 다룹니다. mac os전용 패키지 관리자인 homebrew를 이용하는 방법으로 window 사용자는 아래 공식 깃헙을 확인하여 설치해주시면 됩니다. ⬇️ 42 공식 norminette github https://github.com/42School/norminette GitHub - 42School/norminette Contribute to 42School/norminette development by creating an account on GitHub. github.com ⏯ Norminette 설치하기 1. homebrew 설치 홈브루가 설치 되어있지 않다면, ..

postgresql Homebrew로 설치부터 DBeaver 연결까지 패키지 설치 도구인 homebrew를 이용해서 postgresql을 설치하고 DBMS 도구인 DBeaver에 연결하는 것까지 정리해 보겠습니다. Homebrew나 DBeaver를 설치하는 부분은 생략합니다. ☝️homebrew로 postgresql 설치하기 1. 터미널에 접속합니다. 2. 버전 확인하기 brew search postgresql 위 명령어를 입력하면 homebrew에서 설치 가능한 postgresql의 버젼을 확인할 수 있습니다. @ 뒤에 있는 숫자가 버전을 의미합니다. 3. 설치하기 brew install postgresql 위 명령어를 입력하면 최신 버전의 posrgresql을 설치할 수 있습니다. 만약, 특정 버전을 설치하고 싶다면, @까지 포함한 전체 이름을 적어주면 됩니다. ex)..

깃헙 특정 브랜치 클론 하기 / github branch clone 팀으로 진행되었던 프로젝트에서 자신의 브랜치 가져올 때, 사용하기 좋습니다. 📝 특정 branch clone하기 git clone -b [브랜치 이름] --single-branch [리포지토리 주소] 리포지토리 주소는 HTTPS, SSH 주소 모두 가능 합니다. 예시 git clone -b space_jin --single-branch https://github.com/space-team/toy-proj space-team 깃헙의 toy-proj 리포지토리의 space_jin 브랜치만 클론 합니다.

M1 CocoaPods install 오류 해결(ft. lottie-ios) You may have encountered a bug in the Ruby interpreter or extension libraries. 해결 방법 IOS를 공부하면서 CocoaPods를 이용해 lottie-ios를 설치하려는데 바로 위 같은 오류가 나왔다. 역시 오류 넘어 오류... 다행이 금방 해결 할 수 있었습니다. 🥸 해결 방법 sudo arch -x86_64 gem install ffi arch -x86_64 pod install 터미널로 Podfile이 있는 디렉토리로 이동하신 후 위 명령어를 차례로 입력해주시면 됩니다. M1 환경과 기존의 루비로 이루어져있던 라이브러리의 호환성 문제였기에 아키텍쳐를 지정해서 설치해주면서 해결한 것 같다. 간단명료하게 해결법을 찾아 글을 작성해주신 doka..

이전 1 2 3 4 5 6 7 다음

728x90

티스토리툴바