'🥇코딩테스트:Algorithm' 카테고리의 글 목록 (7 Page)

[백준 2108번-파이썬]통계학

2023.06.20

백준 (BOJ) 11729번 https://www.acmicpc.net/problem/2108 사용언어 : PYTHON 1.문제 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. 2.풀이 최빈값을 구하는 것이 문제였는데, 파이썬의 내장 함수인 Collection모듈의 Counter을 사용하여 해결..

🥇코딩테스트:Algorithm

[백준 1181번-파이썬]단어 정렬

2023.06.19

백준 (BOJ) 11729번 https://www.acmicpc.net/problem/1181 사용언어 : PYTHON 1.문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 1.길이가 짧은 것부터 2.길이가 같으면 사전 순으로 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 2.풀이 중복 제거는 set함수를 사용하여 제거하고, 정렬은 sort함수를 사용하여 정렬하였다. 이때 상위 조건 A과 하위 조건 B가 있는경우, B로 먼저 정렬 한 후에 A로 정렬해야 한다. 여기선 A가 길이가 짧은 것부터, B가 길이가 같으면 사전 순으로 이다. 따라서 사전 순으로 정렬하고 길이가 짧은 순으로 정렬해..

🥇코딩테스트:Algorithm

[백준 11729번-파이썬]하노이 탑 이동 순서

2023.06.19

백준 (BOJ) 11729번 https://www.acmicpc.net/problem/11729 사용언어 : PYTHON 1.문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. *한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. *쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 2.풀이 재귀함수를 사용해서 풀어야 한다. 이전 포스팅에서 설명했던 암시적 매개변수인 각 장대를 명시적 매개변수 start, via end로 ..

🥇코딩테스트:Algorithm

[알고리즘]최대 공약수(GCD) 알고리즘 - 유클리드 호제법

2023.06.19

기존 GCD구하는 방법 for i in range(min(a,b),0,-1): if a%i==0 and b%i==0: print(i) break a와 b중 작은 숫자부터 시작해서 1까지 감소하면서, 제일 처음 a와 b모두 나눠떨어트리는 수를 찾는 방법이다. 이러한 경우는 무차별 대입(Brute Force)로 O(N)의 시간복잡도를 갖는다. 유클리드 호제법 (Euclidean Algorithm) def gcd(a,b): # a>b if b==0: return a c=a%b return gcd(b,c) a를 b로 나눈 나머지를 r이라고 했을때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한 것이다.(재귀함수 이용) 이러한 성질을 활용하여 b와 r의 최대공약수 r0를 구하고 r을 r0로 ..

🥇코딩테스트:Algorithm

[알고리즘]병합 정렬(Merge Sort)

2023.06.19

병합 정렬(Merge Sort) 정렬 순서 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 분할(divide) : 정렬되지 않은 배열을 절반으로 잘라 두 배열로 나눈다. 정복(conquer) : 나눠진 두 배열을 재귀적으로 병합정렬을 사용해서 정렬한다. 결합(combine) : 두 배열을 다시 하나의 정렬된 배열로 합병한다. 분할 정복(divide and conquer)기법과 재귀 알고리즘을 이용하여 정렬하는 방식이다. 수행 과정 예시 다음과 같이 정렬되지 않은 배열이 있다. [6, 5, 3, 1, 8, 7, 2, 4]절반으로 잘라 두 배열로 나눈다. [6, 5, 3, 1] [8, 7, 2, 4]다시 두 배열을 나눠 네 개로 나눈다. [6, 5] [3, 1] [8, 7] [2, 4]마지막으로 네 ..

🥇코딩테스트:Algorithm

카운팅 정렬(Counting Sort)Permalink

2023.06.19

카운팅 정렬(Counting Sort) 과정 배열에 존재하는 수의 개수를 세어서, 이를 바탕으로 정렬을 수행한다. 1.배열에 존재하는 각 값의 갯수를 저장하는 count 변수를 생성한다. 예를들어 count[1]=4 라면 배열에는 1의 값이 4개 있다는 것을 의미한다. count는 배열 원소의 최댓값까지를 인덱스로 사용한다. arr = [4, 7, 9, 1, 3, 5, 2, 3, 4] cnt = [0] * (max(arr) + 1) for num in arr: cnt[num] += 1 print(cnt) # [0, 1, 1, 2, 2, 1, 0, 1, 0, 1] 2. count배열을 누적합으로 계산하여 갱신하여 준다. 누적합으로 갱신하는 이유는 리턴 할 정렬된 배열 answer의 적절한 위치에 삽입하기 ..

🥇코딩테스트:Algorithm

[알고리즘]시간복잡도

2023.06.19

시간복잡도 = 알고리즘의 자원(resource) 사용량을 분석 자원이란 실행시간, 메모리, 저장장치, 통신 등을 말하는 것 인데 그 중에서 실행시간에 대해서 표현 메모리 : 가격대비 메모리 용량이 크게 증가하여 상대적인 중요성이 감소되었다. 실행시간은 하드웨어, 운영체제, 언어, 컴파일러 등에 따라서 달라지게 되므로 실행시간을 측정하는 대신 연산의 실행 횟수를 측정해야 한다. 연산의 실행 횟수 입력 데이터의 크기(n)에 관한 함수로 표현하게 된다. 데이터의 크기가 같더라도 실제 데이터에 따라서 달라진다. (n개의 데이터에서 검색을 할 때, 운이 좋으면 바로 찾을 수도 있고, 운이 나쁘면 n개의 데이터를 모두 검색해서 찾아야 할 수도 있다.) 최악의 경우 시간복잡도 평균 시간복잡도 (평균 시간복잡도 분석이..

🥇코딩테스트:Algorithm

[알고리즘]Recursion 응용(미로찾기)

2023.06.19

미로찾기 그림과 같이 wall 과 pathway로 구성된 미로를 탈출하는 코드를 recursion으로 구현할 수 있다. recursive하게 생각을 해야한다. 현재 위치에서 출구까지 가는 경로가 있으려면 현재 위치가 출구거나 이웃한 셀들 중 하나에서 출구까지 가는 경로가 있거나 간단하게 생각해보면 다음과 같이 구현할 수 있다. boolean findPath(x,y) if (x,y) is the exit return true; else for each neighbouring cell (x',y') of (x,y) do if (x',y') is a pathway cell if findPath(x',y') return true return false; (x,y)에서 출구까지 경로가 있으면 true, 없으면 f..

티스토리툴바