본문 바로가기

분류 전체보기91

[PS] 프로그래머스 - K번째수 | C++, Python 프로그래머스 K번째수 문제 Write-Up입니다. https://school.programmers.co.kr/learn/courses/30/lessons/42748 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제의 배열을 추출해 오름차순 정렬 후 조건에 맞게 원소를 출력하면 됩니다. 1. C++ 풀이 1 : 배열 추출 후 정렬하고 원소를 출력합니다. #include #include #include using namespace std; vector solution(vector array, vector commands) { vector answer; fo.. 2023. 1. 18.
[Algorithm] 삽입 정렬 (Insertion Sort) 삽입 정렬은 해당 요소를 올바른 위치에 삽입하는 정렬 알고리즘입니다. 다음과 같은 순서로 이루어집니다. i번째 원소 선택 (i = 1, 2, 3...) i번째 앞 원소들을 비교하여 올바른 위치에 i번째 원소 값 삽입 위 과정을 배열 원소의 개수만큼 반복 [그림 1] 배열이 있다고 했을 때, 오름차순으로 삽입정렬을 해 보겠습니다. 1. i번째 원소 선택 (i = 1, 2, 3...) 차례대로 원소를 선택합니다. 맨 처음 원소는 선택해도 아무런 의미가 없으므로 두 번째 원소부터 선택합니다. tmp에 i번째 원소 값을 따로 저장하는 이유는, 삽입하는 과정에서 i번째 원소 값이 손실되기 때문입니다. 2. i번째 앞 원소들을 비교하여 올바른 위치에 i번째 원소 값 삽입 앞 원소와 값을 비교합니다. [그림 3]에서.. 2023. 1. 18.
[Algorithm] 버블 정렬 (Bubble Sort) 버블 정렬은 인접한 원소를 비교하여 정렬하는 정렬 알고리즘입니다. 이 모습이 거품 같다고 해서 버블 정렬이라는 이름이 붙었습니다. 다음과 같은 순서로 이루어집니다. n번째와 n+1번째 원소 비교 n+1이 끝에 도달할 때 까지 비교 위 과정을 배열 원소의 개수만큼 반복 [그림 1] 배열이 있다고 했을 때, 오름차순으로 버블정렬을 해 보겠습니다. 1. n번째와 n+1번째 원소 비교 [그림 2]처럼 첫 번째부터 비교하면 됩니다. 두 번째 원소가 더 작기 때문에 서로 swap합니다. 이제 두 번째 원소, 세 번째 원소를 비교하면 됩니다. 끝나면 세 번째, 네 번째 비교, 또 끝나면 네 번째, 다섯 번째... 2. n+1이 끝까지 도달할 때 까지 반복 계속 비교를 하다 보니 제일 큰 숫자인 13이 맨 뒤로 갔습니.. 2023. 1. 17.
[Algorithm] 선택 정렬 (Selection Sort) 선택 정렬은 차례대로 하나의 값을 선택한 후 다른 값과 비교하여 정렬하는 정렬 알고리즘입니다. 다음과 같은 과정으로 이루어집니다. 기준 원소 선택 해당 원소 이후의 원소 값들과 비교 기준 원소가 마지막 원소까지 도달할 때 까지 반복 [그림 1]과 같은 배열이 있다고 했을 때, 오름차순으로 선택정렬을 해 보겠습니다. 1. 기준 원소 선택 기준 원소 선택은 차례대로 이루어집니다. 기준 원소는 i라고 하겠습니다. 우선 첫 번째 원소를 기준으로 잡고, 비교가 완료되면 두 번째, 세 번째... 2. 해당 원소 이후의 원소 값들과 비교 i 이후의 원소들을 비교합니다. [그림 3]에서 j 표시된 부분 하나하나 비교해주면 됩니다. i = 3일 경우에는 i보다 작은 j가 없으므로 넘어가겠습니다. 3. 기준 원소가 마지막.. 2023. 1. 16.
[PS] 백준 1712번 - 손익분기점 | Python 백준 1712번 문제 Write-Up입니다. https://www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net 손익분기점을 구하면 되는데... 총지출보다 총수입이 많아지는 때를 구하면 됩니다. 판매량을 x라고 했을 때, 총지출은 A + (B * x)이고, 총수입은 C * x입니다. 이 때 최초로 A + (B * x) < C * x 식을 만족하는 x의 값을 찾으면 됩니다. 반복문으로 직접 찾는 방법도 있지만, 입력 범위가 21억까지이기 때문에 시간 초과가 나옵니다. 따.. 2023. 1. 13.
[PS] 백준 10809번 - 알파벳 찾기 | Python 백준 10809번 문제 Write-Up입니다. https://www.acmicpc.net/problem/10809 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 알파벳 인덱스를 저장하는 26개의 배열을 정의하고, -1로 모두 초기화를 합니다. 이후 입력받은 문자열을 검사하는데, 해당 문자열이 처음 나올 경우(해당 문자에 해당하는 배열 값이 -1인 경우) 인덱스를 배열에 저장합니다. Python의 경우 배열 통째로 출력하면 오답 처리되네요. C언어처럼 값 하나하나 다 끄집어내서 출력해야 합니다. d.. 2023. 1. 13.
[PS] 백준 2908번 - 상수 | Python 백준 2908번 문제 Write-Up입니다. https://www.acmicpc.net/problem/2908 2908번: 상수 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 www.acmicpc.net 세 자리 숫자 입력 받은 후 거꾸로해서 비교하면 됩니다. int를 직접 입력받아 /와 % 연산을 이용해도 되지만, 문자열로 입력받아 뒤집은 다음 int 형변환해서 비교해도 됩니다. def solution(n, m): return n if n > m else m if __name__ == "__main__": n, m = input().split() print(sol.. 2023. 1. 13.
[PS] 백준 1463번 - 1로 만들기 | Python 백준 1463번 문제 write-up입니다. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제에 주어진 연산을 이용하여 입력되는 수를 1로 만드는데, 이 연산을 사용하는 최솟값을 출력하면 됩니다. 주어진 연산은 다음과 같습니다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 직접 1로 만드는 경우의 수를 계산하게 되면 시간 초과가 나기 때문에, dynamic programming을 이용하여 문제를 풀어야 합니다. dynamic programming에 관한 내용은 다음 게시물을 참고하시기 바랍니다. h.. 2023. 1. 11.
[Algorithm] Dynamic Programming(동적 계획법)과 피보나치 수열 Dynamic Programming(DP, 동적 계획법)은 큰 문제를 작은 문제들로 분할하여 문제를 해결하는 방법입니다. 컴퓨터의 자원은 한정적이어서 무한히 값을 계산할 수 없기 때문에, 이미 계산된 값의 결과를 재활용하여 문제를 해결하는 방법을 만들어 내게 되는데 이것이 dynamic programming입니다. 뭐가 다이나믹한 건지 의문을 제시할 수도 있는데, 이 기법을 처음 고안한 Richard Bellman은 dynamic이라는 단어가 멋있어 보여서, 벨 연구소에서 펀딩을 받기 위해 이렇게 이름을 지었기 때문에 그냥 넘어가면 됩니다. '기억하며 풀기'라고 이해하면 됩니다. 아래의 순서로 DP 문제를 접근해 볼 수 있습니다. 1. DP의 조건 DP를 이용해 문제를 해결하기 위해서는 아래 3가지 조건.. 2023. 1. 11.
[Algorithm] C++로 구현한 행렬 곱셈 알고리즘 행렬의 곱셈 알고리즘은 여러 가지가 존재합니다. 이번 글에서는 행렬의 곱셈 방식과 이를 토대로 한 단순 곱셈 알고리즘을 유도해 보겠습니다. $$ \begin{bmatrix} a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ \end{bmatrix} \times \begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \\ b_{31} & b_{32} \\ \end{bmatrix} $$ 위와 같은 행렬이 존재할 때, 앞의 행렬을 A, 뒤의 행렬을 B라고 하겠습니다. 행렬 A의 크기는 2*3이고, 행렬 B의 크기는 3*2입니다. 1. 행렬 곱셈의 조건 행렬 곱셈을 하기 위해서는 행렬 A의 열과 행렬 B의 행의 개수가 동일해야 합니다. 예시로 .. 2022. 12. 28.

티스토리툴바