본문 바로가기

Algorithms & CS15

[JAVA] 프로그래머스 - 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 이하입니다. a.. 2019. 7. 12.
[JAVA] 프로그래머스 - 모의고사 문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작.. 2019. 7. 11.
[JAVA] 프로그래머스 - 완주하지 못한 선수 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. Solution class Solution { public String solution.. 2019. 7. 10.
[자료구조] 02. Single Linked List 구현하기 링크드 리스트(동적 연결 리스트) 1) 논리적으로 연속된 리스트 2) 필요할 때 공간을 할당할 수 있다. 3) 검색: 임의의 검색은 순차적으로검색하다가 나타나면 땡큐! ArrayList와 동일, 정렬시는 이진검색/보간검색을 통해 바로index로 점프! (데이터가 고르게 분포되어 있어야 유리한 구조) 이중 연결 리스트일 경우, Head 또는 Tail로부터 접근을 결정할 수 있고 바로 jump는 안 된다. 4) 추가: 새로운 객체 할당 → 이전 element에 새로운 객체를 가리키게 함 5) 삽입: 새로운 객체 할당 → 이전 element가 나를 지칭하게 만듦 → 나는 다음 element를 가리키게 함 6) 삭제: 대상의 이전 element가 다음 element를 가리키게 함. 7) 확장: 추가와 동일함 p.. 2019. 4. 3.
[자료구조] 01. hash, hashSet 중복 제거 Hash란? 어떠한 데이터를 어떠한 알고리즘에 의해 일정한 길이의 문자로 바꿈. 한 글자만 바뀌어도 연산의 결과는 전혀 달라짐. 리눅스 암호화 과정에서 ID와 Password를 받을 때에도 해쉬화 된 값으로 비교한다. 해쉬를 가지고 원래의 데이터를 복원하기란 어렵기 때문이다. 또한 검색 속도가 가장 빠른 구조인데, 데이터 저장시 해쉬 값으로 정렬되어 검색할 때 해쉬 값으로 한번에 데이터의 위치를 찾을 수 있기 때문이다. Database에서도 검색시 hash 알고리즘을 사용한다.(해쉬는 중복이 불가능 하지만, 동일한 해쉬가 생성될 경우 링크드 리스트를 사용해 적재한다. ) HashSet 중복제거 hashSet은 hash 알고리즘을 사용한 자료구조이다. hash는 기본적으로 중복이 불가능한데, 같은 값인지가.. 2019. 4. 2.
[자료구조] ArrayList 추가, 출력, 수정, 삭제, 삽입 물리적으로 연속적인 구조를 가진다순차적인 데이터 추가, 출력(읽기 전용)에서 가장 빠른 구조검색: 운 나쁘면 가장 뒤에서 발견삽입: 중간에 넣을 때 뒤에 있는 데이터를 전부 뒤로 밀어야함삭제: 중간에 삭제할 때 뒤에 있는 데이터를 전부 앞으로 당겨야함확장: 물리적으로 연속된 공간을 확보하지 못하면, 전체 데이터를 복사한 후 새로운 공간(새로운 배열을 생성)에 할당해야함. 2019. 4. 2.