자바 알고리즘
-
[JAVA] 10430번: 나머지Algorithm/백준 알고리즘 2021. 7. 12. 10:14
문제 설명 (A+B)%C는 ((A%C) + (B%C))%C 와 같을까? (A×B)%C는 ((A%C) × (B%C))%C 와 같을까? 세 수 A, B, C가 주어졌을 때, 위의 네 가지 값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) 출력 첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다. 풀이 1. 왜 같은지를 수학적으로 이해만 하면 되는 쉬운 문제이다. 세개의 수 A, B, C를 입력받고 각각의 식을 출력문에 기입하여 화면에 출력하면 문제해결! 코드 /* (A+B)%C는 ((A%C) + (B%C))%C 와 같을까? (A×B)..
-
[JAVA] 1874번 : 스택 수열Algorithm/백준 알고리즘 2021. 7. 5. 12:44
문제 설명 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 입력 첫 줄에 n (1 ≤ n ≤ 100,000)이..
-
[JAVA/Level1] 완주하지 못한 선수Algorithm/프로그래머스 2021. 6. 22. 17:45
문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return하도록 solution함수를 작성해주세요. 제한 조건 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 풀이 HashMap자료형은 의 형태로 이루어진 자료형으로 처음 접하게 되었다. ..
-
[JAVA/자료구조] 합병 정렬(Merge Sort)Language/Java 2021. 6. 13. 18:40
평균 수행 시간이 O(logN)인 알고리즘 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 한번 수행될때 마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 사용한다. 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요하다. 합병 정렬(Merge Sort) 비교 기반 정렬 알고리즘 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다 이때 정렬 결과가 임시 배열에 저장된다. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다. 합병..
-
[JAVA/Level2] 정렬된 수에서 하나의 수 위치 찾기Algorithm/프로그래머스 2021. 6. 11. 23:33
문제 설명 여러 개의 수가 정렬된 순서로 있을 때 특정한 수를 찾으세요. 수의 예: [12, 25, 31, 48, 54, 66, 70, 83, 95, 108] 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어진다. 수가 정렬된 상태에서 이진 탐색을 활용할 경우 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있다. 입출력 예 찾고자하는 수의 위치를 찾을 경우 배열 내 인덱스의 값을 출력하세요. 찾고자하는 수가 존재하지 않을 경우 "찾는 숫자가 존재하지 않습니다."를 출력하세요. 풀이 수가 정렬된 상태이므로 중간의 값을 하나 선택하고, 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁히며..
-
[JAVA/자료구조] 자료구조(Data Structure)Language/Java 2021. 6. 8. 12:56
자료구조란? 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현 방법이다. 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 된다. 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있다. 여러 자료구조 중 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야하므로 자료구조에 대한 이해가 중요하다. 자료구조 종류 배열(Array) - 선형으로 자료를 관리, 정해진 크기의 메모리를 먼저 할당받아 사용한다. - 자료의 물리적 위치와 논리적 위치가 같다. 연결 리스트(LinkedList) - 선형으로 자료를 관리, 자료가 추가될 때마다 메모리를 할당 받고 자료는 링크로 연결된다. - 자료의 물리적 위치와 논리적 위치가 다를 수 있다. 큐(Queue) - 가장 먼저 입력 된 자료가 가장 ..