이 문제는 그리디 알고리즘을 이용하여 푸는 문제이다. 그리디 알고리즘 👇 [알고리즘] 그리디 알고리즘이란?(Greedy Algorithms) 💡그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘이란 탐욕적인 알고리즘이라고도 하며, 선택의 순간마다 당장 눈앞에 보이는 최적인 상황만을 쫓아 최종적인 해답에 도달하는 방법 - 문제를 dvlpseo.tistory.com 그리디 알고리즘이란 선택의 순간마다 당장 눈앞에 보이는 최적인 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 회의실이 가장 많이 이용되려면 현재 사용하고 있는 회의의 종료시간이 빨라야한다. 그리고 한가지 더 고려해야 할 점은 만약 종료시간이 같은 경우이다. 예를 들어 [시작 시간, 끝나는시간] 이 [2,2] [1,2]가 있는 경우..

문득 코틀린 언어를 사용하여 프로젝트를 진행하다 코틀린의 시작, 특징도 제대로 모르고 막연하게 코드만 짜고 있었던게 아닌가 라는 생각이 들었다. 그래서 코틀린에 대해 한번 파해쳐보기로했다. 코틀린은 Google I/O 2017에서 안드로이드의 공식 언어로 채택되었다. 코틀린은 자바를 대체하기 위한 목적으로 만들어진 언어이다. 언어적으로는 최신의 패러다임을 적용하며 자바의 몇몇 약점을 개선하면서 기존 자바에서 사용하는 자바 가상 머신과 호환될 수 있게 만들어졌다. 코틀린은 웹 서비스, 안드로이드 개발 뿐 아니라 자바스크립트 및 스위프트와도 연동 가능하다. ☝ 코틀린, 왜 쓰는가? 1. 표현력이 높고 간결함 적은 노력으로 많은 작업을 할 수 있습니다. 상용구 코드를 적게 사용하면서도 아이디어를 풍부하게 표현..

💡그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘이란 탐욕적인 알고리즘이라고도 하며, 선택의 순간마다 당장 눈앞에 보이는 최적인 상황만을 쫓아 최종적인 해답에 도달하는 방법 - 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. - 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 것이다. - 그리디 알고리즘은 순간 하는 선택은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종 해답을 만들었다고 해서 그것이 최적이라는 보장이 없다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제를 풀 때 보통 "가장 큰 순서대로" 혹은 "가장 작은 순서대로" 같은 기준을 제시..

현재 진행한는 앱 프로젝트를 MVC 디자인 패턴을 이용하여 진행하고 있었는데, 요즘 실무에서는 MVP 패턴이나 MVVM 패턴을 주로 사용한다는 이야기를 듣고 이 두 디자인패턴은 무엇인지 궁금해졌다. MVC, MVVM, MVP 디자인 패턴은 소프트웨어에서 자주 사용된다. 이 디자인패턴들의 특징으로는 각각의 역할을 분리해주어 결합도를 낮추고, 확장, 테스트 , 유지보수에 용이하다는 것이다. 💡 MVC 패턴이란? Model + View + Controller를 합친 용어로, 하나의 애플리케이션을 Model, View, Controller로 분리하여 개발하는 디자인패턴이다. Model View에 표시되기 위해 필요한 데이터 데이터가 어떻게 변경되고 조작될 수 있는지에 관한 규칙 정의 View 사용자에게 보여지는..

💡외판원 순회 문제(Traveling Salesman Problem, TSP) 란? 어떤 도시에서 출발하여 다른 모든 도시들을 돌고 다시 출발했던 도시로 돌아오는데 드는 최소 비용을 찾는 문제 브루트 포스 해결방법 ( 좋은 방법 x) 외판원 순회 문제를 막연하게 생각해보면, 특정 출발 도시를 가정해놓고 도시를 순회해도 경로의 길이는 다르지 않을 것이다. 출발 도시를 A로 가정해놓고 다른 도시들을 순회하는 방식은 (n-1)! 형식으로 경우의 수를 구할 수 있다. 하지만 이 경우는 n이 커지면 커질수록 많은 경우의 수를 따져주어야 하기 때문에 효율적인 방법으로 사용되지 않는다. DP 적용 방식 (도시가 16개 이하일 때) / 최적의 접근 방식 DP 메모제이션 = (n-1)!의 모든 경로를 조사하지 않고 중복..

처음 풀었던 방법 어떤 개념을 써야하겠다라는 생각을 하지 못하고 막연히 생각하였다. 몇번 예제로 최대 차이를 구하다보니 중간값이 1번째 배열의 위치에서 시작하여 나머지 값들을 for문으로 돌아가면서 첫번째 값과의 차이를 구하여 제일 차이가 많이 나는 값이 그 다음 배열에 위치하도록 풀어나갔다. 처음 짰던 코드이다. import sys N = int(sys.stdin.readline()) count = 0 plus = 0 result2 = 0 A = list(map(int, sys.stdin.readline().split())) A.sort() print(A) if N % 2 == 0: k = int(N/2) A[k], A[0] = A[0], A[k] else: k = int(N/2)+1 A[k], A[0..

그래프 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조 연결된 노드 간의 관계를 표현할 수 있는 자료구조 방향이 있는 그래프도 있고 없는 그래프도 있다. 루트 노드의 개념이 없고, 부모- 자식 간의 개념이 없다. 2개 이상의 경로가 가능하다. 트리 더보기 트리 (그래프의 한 종류) 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 자료구조 두 개의 노드 사이에 반드시 1개의 경로만을 가지며, 부모- 자식 관계가 형성 되어있다. 사이클이 존재하지 않는 방향그래프이. DFS/ BFS 알기 전 알아야 할 지식 재귀함수 💡 재귀함수의 개념 재귀함수란, 자신을 다시 호출하여 작업을 수행하는 방식 while문이나 for문을 사용하지 않고 자기 자신을 무한히 호출 할 수 있고, 종료 ..

문제 푸는 방법: 1. 입력받은 가로와 세로의 길이를 각각 가로배열 = [0, 가로] / 세로 배열= [0, 세로] 의 배열에 넣어준다. 2. 점선을 자르는 값이 (0, 값)으로 들어오면 가로로 자르는 점선이므로 1번에 만들어 준 가로 배열에 값을 넣어주고 (1, 값)으로 들어오면 세로로 자르는 점선이므로 세로 배열에 값을 넣어준다. 3. 가로 배열과 세로 배열을 sort()함수를 이용하여 오름차순으로 정렬해준 뒤, 각 근접해있는 값끼리의 차이를 계산하여 가장 차이가 큰 값만 추출해준다. 4. 가로에서 차이가 큰 값과 세로에서 차이가 큰 값의 곱이 가장 큰 종이 조각이 된다. 구현한 코드 x, y = map(int, input().split()) a = [0, x] b = [0, y] n = int(in..