Leo.K | To become a cooler Developer

알고리즘 스터디를 하면서 큐에 관련된 문제를 풀었습니다. 순서대로 풀다가 마지막에 이 문제의 정답률을 보고 살짝 겁을 먹은 상태로 문제를 읽었을 때는 생각보다 쉬운데? 하고 풀었지만, 시간 초과로 몇 번이나 실패를 했습니다. 사실 아직은 시간 복잡도의 개념을 잘 몰라서 문제에서 제시되는 입력값의 범위를 고려하지 않았는데 디버그를 몇 번을 돌려보고 해 봐도 모르겠어서 포기하려던 와중,,, 문제 밑에 "덱을 활용하여 시간 복잡도를 해결하는 문제"라는 문구를 보고 다시 다른 방법을 생각해보게 되었습니다. 문제에 제시된 대로, 조건과 에러 처리를 충분히 했는데 왜 시간 초과가 날까 생각하면서 코드를 봤더니 결국 시간이 걸릴만한 코드는 배열의 순서를 뒤집는 거였던 것 같아서 그 부분만 수정했더니 코드가 제출되었습..

그리디 알고리즘을 적용하는 첫 번째 문제입니다. 오름차순으로 입력된 동전의 가치를 위에서부터 차례대로 사용합니다. 동전을 사용하면서 매번 조합해야 하는 금액을 넘지 않는지 체크를 해주어야 합니다. 기본적으로 입력의 조건을 보면, 다음 원소는 이전 원소의 배수라는 조건이 있습니다. 여기를 확인해보시면 동전 교환에서는 탐욕 알고리즘으로 최적해를 구하지 못하는 경우의 수가 있지만, 문제 자체에서 배수 조건을 줌으로써 문제 형태를 매트 로이드로 만들었습니다. 따라서 알고리즘만 구현하면 풀 수 있는 쉬운 문제입니다. 핵심 알고리즘은 다음과 같습니다. 1 2 3 4 5 6 7 8 //동전의 가치가 가장 큰 것부터 비교를 시작합니다. for(int i=N-1; i>=0; i--) { //몫 연산자가 0보다 커야 그 ..

탐욕 알고리즘이란 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법입니다. 최적해를 구하는 데에 사용되는 근사적인 방법입니다.(언제나 최적해를 구하진 못하지만, 최적에 근사한 값을 구함) 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘입니다. 동적 계획법보다 구현이 쉽고, 시간복잡도가 우수한 장점이 있지만 항상 최적해를 보장하지 못합니다. 여러 경우의 수 중에서 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식입니다. 단, 순간마다 하는 선택은 그 순간에 대해서 지역적으로는 최적이지만, 이러한 지역적으로 최적인 선택을 수집하여 최종적인 해답을 만들었다고 해서, 이 방법이 전역적으로 최적이라는 보장은 없습니다. 하지만..

자바에서 컬렉션 프레임워크란 일정 타입의 데이터들이 모여 쉽게 가공할 수 있도록 지원하는 자료구조들의 기본 틀을 이야기합니다. 틀이라고 하니까 생각나는 것이 있나요? 인터페이스를 떠올렸다면 아주 이해가 쉬울 것 같습니다. 자바의 JDK는 프로그램 개발에 필요한 기초적인 자료구조들을 거의 대부분 컬렉션으로 만들어서 제공하기 때문에, 아주 중요합니다. 컬렉션은 제네릭이라는 기법으로 구현됩니다. 즉, 데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것입니다. 컬렉션은 고정 크기의 배열이 가지는 단점을 극복하고, 요소라고 불리는 객체들의 삽입, 삭제, 검색 기능을 갖춘 가변 크기의 컨테이너 입니다. 컬렉션의 특징 1. 제네릭으로 구현된다. 컬렉션의 클래스나 인터페이스에..

오늘은 자바로 만든 성적관리 폼과, DB로 만든 성적관리 데이터를 연동하여 사용해보는 실습을 해보겠습니다. 전체적인 구조는 다음과 같습니다. 지난 포스팅에서 selectList를 구현하는 방법에 대해 공부해보았습니다. 내용이 궁금하신 분은 여기를 학습하세요. 이번에는 나머지 insert, update, delete명령의 실행과정을 중심으로 공부해보도록 하겠습니다. 1. 사전준비 새로운 프로젝트에 드라이버 라이브러리를 불러왔다는 가정 하에, 우선적으로 자바와 연동할 데이터베이스를 설계해야 합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 4..

오늘은 데이터베이스를 모듈화해서 JDBC를 사용해 자바로 핸들링하는 실습을 진행해보겠습니다. 1. 프로그램 구조 모듈화하고자 하는 프로그램의 구조는 다음과 같습니다. 2. 프로그램 실행 과정 전체 프로그램의 대략적인 개요는 다음과 같은 순서로 실행됩니다. 다음의 순서는 조회를 하는 예시입니다. 1. 사용자가 DB에 있는 데이터에 대해서 CRUD 명령을 요청합니다.(누구에게? DAO에게) ㄴ> 호출하는 방법 -> DeptDao.getInstance() [Dao의 객체를 생성 or 호출합니다.] ㄴ> 싱글톤 패턴을 사용했기때문에 가장 처음 호출에만 객체을 생성하고, 그 이후에는 이전에 만들어 둔 객체를 반환합니다. 2. 요청을 받은 DAO는 DB에 연결을 하기 위해서 연결 요청을 합니다. (누구에게?DBSe..

스택을 응용하는 알고리즘 문제입니다. 풀이를 시작하기게 앞서 문제를 먼저 분석하여 접근해보겠습니다. 1. 동일한 괄호가 짝을 이루어야 한다. ㄴ> 두 개의 괄호를 구분해서 생각해줘야 합니다. 2. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 있다. ㄴ> 반드시 왼쪽 괄호가 먼저 나와야만 짝을 이룰 수 있다. 3. 짝을 이루는 문자열이 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다. ㄴ> 균형이 이루어진 괄호 안에도 괄호가 있을 수 있는데 이 내부에 있는 괄호 또한 균형이 맞아야 합니다. ㄴ> ( ] [ ) 이런 문자열도 외부 괄호는 균형을 이루지만 내부 괄호는 균형을 이루지 않기 때문에 조건에 맞지 않습니다. 위의 문제 분석을 통해 알아낼 수 있는 핵심중에서 이 문제를 해결하기 ..

이클립스에서 데이터베이스를 사용하기 위해서는 언어의 사용하는 언어가 같아야 합니다. 쉽게 생각해서 두 명의 사람이 대화를 하는데 한 사람은 한국어만 사용할 수 있고, 한 사람은 일본어만 사용할 수 있다면, 두 사람 간의 공통적인 언어체계가 없기 때문에 소통이 이루어지지 않습니다. 따라서, 자바와 데이터베이스 사이에 "드라이버"를 두면 드라이버가 자바와 데이터베이스가 소통할 수 있도록 중간에서 명령어를 변환해주는 역할을 합니다. JDBC(Java Database Connectivity) : 자바를 통해서 데이터베이스에 접근하도록 도와주는 라이브러리입니다. 각 언어로 작성한 SQL명령을 JDBC드라이버를 통해서 DB에 전달해 주면, DB에서 실행한 결과를 드라이버를 통해 다시 각 언어로 전달해 줍니다. --..

문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 오늘 사용할 맵의 가장 큰 특징은 실제 데이터를 key-value의 한 쌍으로 저장한다..

이번 글은 앞 내용과 이어지기 때문에 이해가 어려우신 분들께서는 아래 링크의 내용을 먼저 보시기 바랍니다. https://cm-me0410.tistory.com/4 Join의 개념 Join연산자의 기본개념을 파악해보도록 하겠습니다. 1. 둘 이상의 테이블을 연결하여 데이터를 검색하는 방법입니다. 2. 연결하는 기준을 "조인 기준"이라고 하며, 각 테이블의 공통된 값을 통해 연결하는데, 보통 기본키(PK) 및 외래키(FK) 값을 사용하여 연결합니다. 3. 두 개의 테이블을 SELECT 문장 안에서 조인하여 조회하려면, 적어도 하나의 컬럼이 두 테이블 사이에서 공유되어야 합니다. [2번에서 말한 기본키 및 외래키가 그 역할을 합니다.] Join의 종류를 설명하기 위해서 sawon, gogek, dept 세 ..

문제 설명 문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있..

ERD(Entity_Relation_Diagram)를 통한 테이블 구조 파악 릴레이션의 Join연산은 공통 속성을 중심으로 2개의 릴레이션을 하나로 합쳐서 새로운 릴레이션을 만드는 과정으로 순수관계연산자의 종류 중 하나입니다. Join연산은 ▷◁의 기호로 표시하며, 두 릴레이션 R과 S의 조인을 표기하는 표기형식은 다음과 같습니다. 표기 형식 : R▷◁(JOIN 조건)S 조인연산의 개념을 명확하게 이해하기 위해서는 관계데이터베이스에서 각 개체들의 관계를 명확하게 이해할 필요가 있습니다. 사실상 DB를 직접 설계하고 구현하는 사람이 아니라면 실질적으로 ERD를 설계하는 일은 없겠지만, 일반 개발자 입장에서는 DB로부터 적절한 데이터를 검색하기 위해서 설계된 ERD를 보고 이해하며, 코드화할 수 있는 기능은..