알고리즘

MVC패턴이 생겨난 이유 프로그램의 코드가 많아지면 많아질 수록 코드가 복잡해져서 파악하기도 어렵고, 유지보수가 많이 어려워졌다. 그러다가 프로그래머들이 하나의 패턴을 찾게 되었고, 이걸 논문으로 발표하면서 MVC 패턴이 유명해지게 되었다. MVC -> 유지보수가 편해지는 코드 구성 방식 1. 클라이언트가 구글에 "개발자"라고 검색 2. 컨트롤러는 요청을 받아서 모델에 "개발자"에 대한 검색 결과 데이터를 달라고 요청 3. 데이터를 받은 컨트롤러는 View한테 검색 결과 데이터를 전달한다. 4. View는 사용자가 보는 UI(레이아웃)에 검색 결과 데이터를 넣어서 웹페이지로 보여준다. Model : 데이터와 관련된 부분 View : 사용자한테 보여지는 부분 Controller : Model과 View를 ..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크..

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?contestProbId=AV5PoOKKAPIDFAUq&solveclubId=AYWesuzK3nUDFAQK&problemBoxTitle=6%EC%A3%BC%EC%B0%A8&problemBoxCnt=5&probBoxId=AYdFW2sakzMDFASR+ SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이 문제에서 가장 핵심인 곳은 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K깊이 만큼 지형을 깎을 수 있다는 점이다. K=4가 주어지면 이걸 1,1,1,1 or 1,1,2 이렇게 나눠서 깎는 것이..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS의 대표적인 문제다. 1주일 전에 풀었는데 다시 풀려니깐 생각이 안나고 다시 코드를 찾아보게 돼서 정리하고자 한다. 미로는 배열의 처음부터 시작하고 N,M에 도착하면 끝난다. 그 중에서 가장 최단 거리로 이동할 수 있는 방법을 찾아야 한다. 나는 result 배열을 만들어서 구하고자 했다. 우선 전체 코드이다. package 단계별문제; import java.util.LinkedList; import java.util.Qu..

https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 색종이를 칸에 맞게 가장 최적으로 붙이는 개수를 구해야 하는 문제. 1,2,3,4,5의 nxn사이즈를 가진 색종이가 5장씩 주어지는데 처음에 가장 큰 사이즈부터 완탐을 돌리고 테케는 다 맞았는데 돌려보니 17%인가 18%에서 나가떨어졌다. 최적을 구해야 하니 가장 큰 것부터 돌리는 게 아니라 백트래킹으로 접근해야 문제를 풀 수 있었다. 우선 전체 코드를 보자 import java.util..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 스패닝 트리(MST)에 대한 문제다. 더보기 최소 스패닝 트리란? 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 가중치의 합이 최소인 트리를 말한다. MST개념을 공부하면 가장 처음 접하게 되는 문제다. (골드 4지만 방법을 알면 실버급이라고 생각한다.) MST를 구하는 대표적인 방법으로는 크루스칼, 프림 2가지가 있다. 나는 이중에..