![]()
https://programmers.co.kr/learn/courses/30/lessons/42746?language=python3 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 문제를 파악해보자. 0 또는 양의 정수가 주어졌을때 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내는 문제이다. 제한 사항을 보면 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수..
![]()
URL : https://programmers.co.kr/learn/courses/30/lessons/42748 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 배열 array의 i번째 숫자부터 j번째 숫자까지 고르고 정렬한 후 k번째 수를 구하는 문제이다. 입력 형태는 아래와 같다. 기본적인 solution()함수의 매개변수로 array,commands를 받게되는 것이다. commands안에 각각의 상황에 따른 i,j,k값이 있고, 각 command별로 결과값들을 모아서 리스트로 반환하는 것이다. 아래와 같이 구현하였다 from typing import MutableSequ..
URL : https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 기본적인 정렬 문제이다. 첫번째 줄에 n을 받고 그 다음줄부터 총 n개의 수를 받아서, 정렬하는 문제이다. 버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 파이썬 내장 sort, 숏코딩 총 6가지 방법으로 풀어보았다 from typing import MutableSequence ''' python short coding print(*sorted([int(input()) for _ in range(int..
![]()
링크 : https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수열 문제이다. 피보나치 수열이란, 제 0항을 0, 제 1항을 1로 두고, 두번째 항부터 바로 앞의 두수를 더한 수로 놓는다.(F(2) = F(1) + F(0)). 피보나치 수를 상향식 분석하면 아래와 같다. 결론적으로 계속해서 f(n) = f(n-1) + f(n-2) 형태로 나아가는것을 볼 수 있다. 다만 주의해 줄 것이 있다. 피보나치 ..
![]()
링크 : https://level.goorm.io/exam/43083/%EA%B3%84%EB%8B%A8-%EC%98%A4%EB%A5%B4%EA%B8%B0/quiz/1 구름LEVEL 코딩테스트에서 가장 높은 비중을 차지하는 알고리즘 문제를 제작하고 풀이할 수 있는 온라인 저지 서비스입니다. 기업에서 선호하는 C, C++, 파이썬(Python), 자바(Java), 자바스크립트(Javascript) 이 level.goorm.io 우선 문제를 분석해 보겠습니다. 계단을 최대 2칸 오를 수 있다고 할때 계단을 오르는 방법의 가짓수를 출력하는 프로그램을 작성하시오. n 이 3인경우 1. 1 - 2 - 3 2. 1 - 3 3. 2 - 3 이를 기반으로 그림으로 작성해 보면 아래와 같습니다. 내가 지은 결론은, 계단을..
![]()
재귀란? 재귀란 자기 자신을 재참조하는 형태의 알고리즘을 의미한다. 재귀의 장점 1. 피보나치수열, 팩토리얼과 같이 재귀적 표현이 자연스러운 해결에 대해서는 도움이 된다.(가독성) 2. 함수를 단순하게 만들어 준다 3. 변수사용을 줄여준다. 재귀의 단점 1. 메모리를 많이 차지하며 성능이 반복문에 비해 느리다.(함수 스택 call이 반복적으로 이루어지므로) 2. StackOverflow가능성이 크다 3. CPU 크래쉬를 발생시키기도 한다. 재귀의 대표적인 예시들 - Factorial def factorial(n : int) -> int: if n > 0: return n * factorial(n - 1) else: return 1 if __name__ == "__main__": n = int(input(..
![]()
Queue란? 큐는 스택과 동일하게 데이터를 임시 보관하는 자료구조이다. 다만 스택과 달리 선입선출(FIFO, First In Frist Out)구조를 가지고 있다. 큐에서 가지는 기본적인 작업은 아래 두개가 있습니다 인큐(Enqueue) : 데이터를 추가하는 작업 디큐(Dequeue) : 데이터를 빼내는 작업 그리고 스택의 구조에 쓰이는 용어도 두가지가 있습니다. 프런트(Front) : 데이터를 꺼내는 쪽 리어(Rear) : 데이터를 빼내는 쪽 Ring Buffer로 원형 큐 구현하기 일반적으로 배열형태로 큐를 구현하게 되면, 만약 디큐를 하게 되면 그 뒤 원소들을 모두 앞쪽으로 땡겨주어야합니다. 이 작업에서는 시간복잡도 O(n)이 추가적으로 들어가게 됩니다.디큐의 시간복잡도가 O(1)인데 이 작업으로..
![]()
스택(Stack이란?) 스택은 데이터를 임시저장할때 사용하는 자료구조이다. 기본적으로 후입선출(LIFO,Last In First Out)방식이다. 스택의 동작은 두가지가 있다 푸시(Push) : 데이터를 넣는 작업이다. 팝(Pop) : 데이터를 꺼내는 작업이다. 그리고 푸시, 팝을 하는 윗부분을 top, 아랫부분을 bottom이라고 한다. 스택 구현하기 스택을 구현해 보자. 우선 기본적으로 Fixed-Stack으로 구현해 보자. 스택을 구현하는데 있어 기본적으로 아래 세가지가 필요로 하다 스택배열 : stk - 데이터를 저장하는 본체이다 스택크기 : capactiy - 스택의 최대 크기를 나타내는 정수이다 스택포인터 : ptr - 스택에 쌓여있는 데이터 개수를 나타내는 정수값이다. 비어있으면 0, 차있으..
![]()
버블 정렬은 이웃한 두 원소의 관계를 비교해, 필요에 따라 교환을 반복하는 알고리즘입니다.버블정렬은 '단순 교환 정렬' 이라고 부르기도 합니다. 우선 버블 정렬의 교환 방식을 그림으로 살펴보겠습니다 버블정렬은 기본적으로 이웃된 원소들간의 비교, 교환이 일어나기 때문에, 안정적인 정렬이라고 할 수 있습니다. 이제 한번 그림을 같이 보겠습니다.총 길이 6인 리스트가 있습니다. 이 리스트에서 한번의 정렬을 위해서 (총 길이) - 1번만큼의 비교, 교환이 이루어 지는것을 볼 수 있습니다. 그리고 참고로 버블 정렬에서 일어나는 비교,교환 과정을 '패스'라고 부릅니다. 자 그럼 일단 코드를 작성해 봅시다. 우선 총 길이에 대해 -1 번만큼 교환이 일어난다고 했죠? 아래와 같이 작성해 줍니다. from typing ..
![]()
프로그래머스 문제를 풀었다. https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 결론적으로 내가 작성한 코드는 아래와 같다 from typing import Any, Sequence from collections import deque from random import randint class PriorityPrint(object): def __init__(self,seq,location): self.location..
https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 소인수 분해를 문제를 풀면서 두가지 접근 방법을 생각하였다 1) 재귀 2) 단순 반복문 우선 문제를 파악해보자 문제 : 정수 N이 주어졌을때 소인수분해하는 프로그램을 작성하시오 입력 : N(1
![]()
1. 유클리드 호제법이란? -> 유클리드 호제법이란 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 여기서 '호제법' 이란 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 의미한다. 예를 들어 a > b라고 할때 a를 b로 나눈 나머지를 r이라고 하면 b와 r의 최대공약수는 a와 b의 최대 공약수와 같다. 15와 6 라고 가정을하면 나머지는 3이된다 15와 6의 최대 공약수는 3, 6과 3의 최대공약수는 3이된다. 다시 b와 r을 나는 나머지인 r'이라고 하면 b와 r의 최대 공약수는 r r'의 최대 공약수와 같아진다(6,3 과 3,0 -> GCD : 3) 결론적으로 맨 마지막에 나오는 r r'의 나누기 나머지가 0이 될때 a와 b의 최대공약수가 나오는 것이다. 2. 관련 문제 UR..
