'알고리즘' 카테고리의 글 목록

알고리즘/문제풀이 2022. 8. 10.

[백준알고리즘] 10989. 수 정렬하기 3 풀이 (Java)

❓ 문제 ❗ 풀이 이 문제는 시간 제한, 메모리 제한을 신경써야한다. 수 정렬하기2에서 푼 코드를 가져와 제출하였을 때 Array.sort()를 사용한 코드는 통과되었지만 Collections.sort()를 사용한 코드는 메모리 초과로 통과되지 못하였다. Array.sort()외 다른 방법이 없을까 보는 중 카운팅정렬을 사용하는 방법을 보았다. 카운팅정렬의 시간복잡도는 O(N + K)로 K는 자릿수를 의미한다. 입력데이터가 K 보다 훨씬 큰 경우, 즉 데이터가 많으면 많을수록 O(N) 에 가깝기 때문에 이상적으로는 O(N) 이라고 보아도 무방하다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRea..

알고리즘/문제풀이 2022. 8. 10.

[백준알고리즘] 2751. 수 정렬하기 2 풀이 (Java)

❓ 문제 ❗ 풀이 해당 문제는 시간 제약이 있었기 때문에 Arrays.sort()를 사용할 경우 시간초과 문제가 발생할 수 있다. (뒤에 Arrays.sort()를 사용하여 푸는 방법도 설명해두었다.) Arrays.sort()의 경우 평균 시간복잡도가 O(nlogn)이고 매우 빠른 알고리즘이지만, 최악의 경우 시간복잡도는 O(n^2)이다. 따라서, Collections.sort()를 사용해 문제를 풀었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; class Main { // So..

알고리즘/문제풀이 2022. 8. 8.

[백준알고리즘] 10814. 나이순 정렬 풀이 (Java)

❓ 문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다. 출력 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다. ..

알고리즘/문제풀이 2022. 7. 9.

[LeetCode] 88. Merge Sorted Array (Easy) 풀이

❓ 문제 You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively. 내림차순으로 정렬된 두 개의 정수형 배열인 nums1 및 nums2와 nums1과 nums2의 element 수를 나타내는 두 개의 정수인 m, n가 주어진다. Merge nums1 and nums2 into a single array sorted in non-decreasing order. nums1과 nums2를 내림차순으로 정렬된 하나의 배열로 병합하려고 한다. The final..

알고리즘/문제풀이 2022. 7. 6.

[LeetCode] 70. Climbing Stairs (Easy) 풀이

❓ 문제 You are climbing a staircase. It takes n steps to reach the top. 계단을 올라가야한다. 계단 끝에 도달하기 위해 n 계단을 밟아야한다. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 한번에 1계단 또는 2계단만 올라갈 수 있다. 계단 마지막으로 올라가기 위해서 중복 없이 얼마나 많은 경우의 수가 있는가? Example 1: Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Exampl..

알고리즘/문제풀이 2022. 6. 20.

[LeetCode] 69. Sqrt(x) (Easy) 풀이

❓ 문제 Given a non-negative integer x x. Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned. pow(x, 0.5) or x ** 0.5. 음이 아닌 정수 x x가 주어진다. 리턴타입이 정수형이기 때문에 소수점 이하 자리수는 잘리고 오직 결과의 정수부분만 리턴한다. pow(x, 0.5) or x ** 0.5. Example 1: Input: x = 4 Output: 2 Example 2: Input: x = 8 Output: 2 Explanation: The square root of 8 is 2.82842....

알고리즘/문제풀이 2022. 6. 20.

[LeetCode] 66. Plus One (Easy) 풀이

❓ 문제 You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's. Increment the large integer by one and return the resulting array of digits. 정수 배열 자릿수로 표현되는 큰 정수가 주어진다. 여기서 각 자릿수[i]는 정수의 i번째 ..

알고리즘/문제풀이 2022. 6. 10.

[백준알고리즘] 10815. 숫자 카드 풀이 (Java)

❓ 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다...

알고리즘/문제풀이 2022. 4. 26.

[백준알고리즘] 7568. 덩치 풀이 (Java)

❓ 문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"라고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165)라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼..

알고리즘/문제풀이 2022. 4. 25.

[백준알고리즘] 2231. 분해합 풀이 (Java)

❓ 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자릿수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. 예제 1 입력 216 출력 198 ❗ 내 풀이 import java.util.*; cla..

알고리즘/문제풀이 2022. 4. 12.

[백준알고리즘] 2798. 블랙잭 풀이 (Java)

❓ 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때,..

알고리즘/문제풀이 2022. 3. 16.

[LeetCode] 20. Valid Parentheses (Easy) 풀이

❓ 문제 Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. '(', ')', '{', '}', '[' 및 ']' 문자만을 포함하는 문자열이 주어지면 입력 문자열이 유효한지 확인한다. 문자열이 유효한 경우 : 열린 괄호는 반드시 같은 타입의 괄호로 닫혀야 한다. 열린 괄호는 반드시 올바른 순서로 닫..

알고리즘/문제풀이 2022. 3. 16.

[LeetCode] 14. Longest Common Prefix (Easy) 풀이

❓ 문제 Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". 문자열 배열 중에서 가장 긴 공통 접두사 문자열을 찾는 함수를 작성하자. 공통된 접두사가 없으면 빈 문자열 ""을 반환한다. Example 1: Input: strs = ["flower","flow","flight"] Output: "fl" Example 2: Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input..

알고리즘/문제풀이 2022. 3. 14.

[LeetCode] 13. Roman to Integer (Easy) 풀이

❓ 문제 Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. 로마 숫자는 I, V, X, L, C, D, M의 7가지 기호로 표시된다. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II. Roman numerals are usually written..

알고리즘/문제풀이 2022. 3. 11.

[LeetCode] 9. Palindrome Number (Easy) 풀이

❓ 문제 Given an integer x, return true if x is palindrome integer. An integer is a palindrome when it reads the same backward as forward. For example, 121 is a palindrome while 123 is not. 정수 x가 주어졌을 때, x가 회문이면 true를 반환한다. 앞으로 읽었을 때와 뒤로 읽었을 때 같을 경우 해당 정수를 회문이라고 한다. 예를 들어, 121은 회문이지만 123은 회문이 아니다. Example 1: Input: x = 121 Output: true Explanation: 121 reads as 121 from left to right and from right..

알고리즘/문제풀이 2022. 3. 11.

[LeetCode] 1. Two Sum (Easy) 풀이

❓ 문제 Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. 정수로 이루어진 배열과 정수인 target이 주어지면, 두 숫자의 합이 target이 된 인덱스를 반환한다. 각각의 입력은 단 하나의 방법이 있다고 가정하며, 같은 배열의 요소를 두 번 사용하지 않도록 한다. 순서 상관없..

알고리즘/문제풀이 2021. 8. 25.

[프로그래머스] 코딩테스트 연습 - 평균 구하기 Java, JavaScript

문제 설명 정수를 담고 있는 배열 arr의 평균값을 return하는 함수, solution을 완성해보세요. 제한사항 arr은 길이 1 이상, 100 이하인 배열입니다. arr의 원소는 -10,000 이상 10,000 이하인 정수입니다. 입출력 예 arr return [1,2,3,4] 2.5 [5,5] 5 나의 풀이 JavaScript Vue로 개발하면서 js의 중요성도 점차 깨닫게 되었다. js를 잘 짜는 것도 FE에서 중요하다는 것을 느껴 js도 함께 공부하려고 한다. function solution(arr) { var answer = 0; arr.forEach(item => { answer += item }); answer = answer/(arr.length); return answer; } Jav..

알고리즘/문제풀이 2021. 8. 24.

[프로그래머스] 위클리챌린지 1주차 - 부족한 금액 계산하기 Java

문제 설명 새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이용료가 100이었다면 2번째에는 200, 3번째에는 300으로 요금이 인상됩니다. 놀이기구를 count번 타게 되면 현재 자신이 가지고 있는 금액에서 얼마가 모자라는지를 return 하도록 solution 함수를 완성하세요. 단, 금액이 부족하지 않으면 0을 return 하세요. 제한사항 놀이기구의 이용료 price : 1 ≤ price ≤ 2,500, price는 자연수 처음 가지고 있던 금액 money : 1 ≤ money ≤ 1,000,000,000, money는 자연수 놀이기구의 이용 횟수 c..