본문 바로가기

분류 전체보기

[Java] K번째 수 구하기 (선택정렬 활용) 문제 K번째수 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 array의 길이는 1 이상 100 .. 더보기
[백엔드TIL]다익스트라 알고리즘(Dijkstra Algorithm) 원리 [Java]다익스트라 알고리즘(Dijkstra Algorithm) Algorithm/그래프&최단경로 2021. 3. 12. 00:40 *다익스트라 알고리즘(Dijkstra Algorithm) -> 다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다. -> 초기 모델은 O(V^2)의 시간복잡도를 가졌다. 이후 우선순위 큐 등을 이용한 고안된 알고리즘이 탄생했고, 현재는 O((V+E)log V)의 시간복잡도를 가지고 있다(만일 연결 그래프라면 O(ElogV)까지 시간 복잡도를 줄일 수 있다고 한다). 일반적으로는 그래프가 희소 그래프인 경우에 우선순위 큐를 이용하는 것이 낫다고 한다. ※음의 가중치를 가지면 안되는 이유.. 더보기
[백엔드TIL] JAVA 조이스틱의 상,하 조작으로 원하는 알파벳 조작하기 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서) 예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다. - 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를.. 더보기
[백엔드TIL] 그리디 알고리즘(탐욕법, Greedy Algorithm) 💡 그리디 알고리즘(탐욕법, Greedy Algorithm) 이란? - 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘입니다. - 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 하고 있습니다. - 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용됩니다. 💡 [문제] 노드에서 가장 합이 높은 방법을 선택하는 방법을 생각해 봅니다. 💡 해당 경우에서는 기준 없이 선택을 하는 경우를 보여주고 있습니다. https://velog.io/@kyunghwan1207/%.. 더보기
[백엔드TIL] 트랜잭션의 고립 수준 트랜잭션의 고립 수준(Isolation Level)이란? 트랜잭션의 고립 수준이란 트랜잭션들끼리 일관성 있는 데이터를 얼마나 허용할 것인지 정해놓은 수준이다. 즉, 트랜잭션 수행 중 다른 트랜잭션이 해당 데이터를 조회하는 것이 가능한 정도를 결정해 놓은 것이다. 고립 수준이 높을수록 일관성은 보장되지만 그만큼 동시성이 떨어져 성능이 하락한다. 트랜잭션에 대해 잘 모르겠다면 다음 게시물을 참고하자. [DB] 트랜잭션(Transaction)이란? | ACID 트랜잭션(Transaction)이란? 트랜잭션은 데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업의 단위 또는 한꺼번에 수행되어야할 일련의 연산들을 의미한다. 트랜잭션은 code-lab1.tistory.com 이상 현상의 종류 D.. 더보기
[백엔드TIL] REST API 설계 시 고려사항 API란 Application Programming Interface의 약자로 프로그램을 실행하는 인터페이스입니다. API를 통해 프로그램에 요청을 전달하기위한 통로 혹은 방법 RESTful API에서 HTTP Method GET: 조회 (받겠다) POST: 리소스 생성 (보내겠다) PUT: 리소스 전체 갱신(놓겠다/넣겠다) DELETE: 리소스 삭제 (지정한 서버의 파일을 삭제하겠다) 설계 예 :id와 같이 변하는 값은 하나의 특정 resource를 나타내는 고유값이어야 합니다. REST API 디자인 가이드 REST API 설계 시 가장 중요한 항목은 다음의 2가지로 요약할 수 있습니다. 첫 번째, URI는 정보의 자원을 표현해야 한다. 두 번째, 자원에 대한 행위는 HTTP Method(GET, P.. 더보기
[백엔드TIL] JSP와 Servlet 개념 Server Side Applet인 Servlet에 대해여 정의하고 Servlet클래스를 만들기 위한 방법을 기술하시오 -JAVA Servlet은 JAVA를 사용하여 웹페이지를 동적으로 생성하는 서버측 프로그램 혹은 그 사양을 말하며, 흔히 "서블릿" 이라 불린다. 서블릿은 JAVA EE 사양의 일부분으로, 주로 이 기능을 이용하여 쇼핑몰이나 온라인 뱅킹 등의 다양한 웹 시스엠이 구현되고 있다. 서블릿은 외부 요청마다 프로세스보다 가벼운 쓰레드로써 응답하므로 보다 가볍다. 또한 , 서블릿은 JAVA로 구현되므로 다양한 플랫폼에서 동작한다. Servlet과 JSP의 차이점에 대하여 말해주세요 -servlet은 java 소스에 HTML코드가 삽입된다 -JSP는 반대로 HTML코드에 java코드가 삽입된다. .. 더보기
[백엔드TIL] DFS 개념 및 부분집합 문제 DFS · DFS(Depth-First Search)는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 알고리즘 동작 방식 · 스택 자료구조를 이용한다. 1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 위의 1번과 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다. * ‘방문 처리': 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 이를 통해 각 노드를 한 번씩만 처리할 수 있다. 부분집합 문제 설명 N개의 원소로 구성된 자연수 집합이 주어지면, 이 .. 더보기
[백엔드TIL] IOC 와 DI 개념 IoC (Invesion of Control) 1. '제어' 와 '역전' 의 의미 제어: 어떠한 클래스 내부에서 다른 객체를 생성하고 이용할 때, 직접 코드를 생성하여 '제어' 한다고 한다. 역전: 객체를 클래스 내부에서 직접 생성하고 제어하는 것이 아니라, 외부에서부터 인자로 받아 초기화 하는 것 2. IoC (제어의 역전) 가 필요한 이유 영상에서 서브웨이를 예시로 이해하기 편하게 설명해주었다. 서브웨이에서 샌드위치를 주문한다고 하자. IoC 가 적용되지 않은 경우: 클래스 내부에서 다른 객체를 제어하고, 외부에서 인자를 받지 않기 때문에, 커스텀 없는 기본 레시피의 샌드위치라고 생각할 수 있다. IoC 가 적용된 경우: 외부에서 인자를 받아 객체를 생성하고 초기화하므로 샌드위치의 속 재료를 커스텀 .. 더보기
[백엔드TIL] BFS 너비 우선 탐색(JAVA) BFS 너비 우선 탐색(Breadth First Search) "꼼꼼하게 좌우를 살피며 다니자"와 같이 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 알고리즘이다. 시작 정점을 지나고 나면 깊이가 1인 모든 정점을 방문하고, 그다음에는 깊이가 2인 모든 정점을 방문한다. 이런 식으로 한 단계씩 깊이를 더해가며 해당 깊이에 있는 모든 정점들을 방문해 나가다가 나중에는 더 이상 방문할 곳이 없을 때 탐색을 종료한다. * 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 * 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. BFS의 특징 BFS는 시작 정점으로부터 거리가 가까운 정점의 순서.. 더보기