알고리즘(21)
-
[프로그래머스] 억억단을 외우자 파이썬 풀이
※사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://school.programmers.co.kr/learn/courses/30/lessons/138475 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제설명 ◇ 문제를 요약하자면 다음과 같습니다. ▶ 구구단 같이, 억 X 억을 곱해둔 단이 존재합니다. 그리고 해당 억억단에서 s 부터 e까지의 수 중 가장 많이 나온 수를 찾고 출력합니다. 단, s 부터 e까지의 수 중 가장 많이 나온 수가 여러 개이면 가장 작은 수를 출력합니다. (여기서 s는 starts 배열 안의 수다.) ◇ 풀이 방법을 간단하게..
2023.01.07 -
[구름] 알고리즘 먼데이 챌린지 0주차 카드 교환하기 파이썬 풀이
※사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ 0주 차 챌린지 goorm 구름은 클라우드 기술을 이용하여 누구나 코딩을 배우고, 실력을 평가하고, 소프트웨어를 개발할 수 있는 클라우드 소프트웨어 생태계입니다. goorm.co 문제 접근 해당 문제는 구름 측에서 해설지를 제공하고있다. 그럼에도 불구하고 포스팅을 한 이유는 단순히 해설지에 파이썬 코드가 없기 때문이었다. 그냥 넘어가긴 조금 아쉬운 감이 있으니 해설지 내용을 간략하게 압축하여 서술하겠다. 해당 문제는 그리디로 접근이 가능하다. 그 이유는 사람의 순번이 작을수록 그 사람이 교환할 수 있는 카드 중 가장 작은 수를 선택해야 하기 때문이다. 예를 들어, 순번이 2, 5, 6 인 사람끼리 카드 교환이 가능하다고 가정하겠습니다. 그리고 세 명의 사람이 가..
2022.11.16 -
[백준] 18119 단어 암기
※ 사용언어 : 자바 ※ ▼ 문제 링크 ▼ https://www.acmicpc.net/problem/18119 문제 접근 1. 완전 탐색을 이용, 각 쿼리가 이루어질 때마다 각 단어의 알파벳을 다 기억하고 있는지 검사하면 시간 초과로 문제를 풀 수 없습니다. 그러므로 비트마스킹을 이용해 알고리즘 수행 시간을 감소시켜야 합니다. 2. 비트마스킹이란 정수의 이진수 표현을 자료구조로 이용하는 방식입니다. 3. 접근 1) 준석에는 처음에 모든 알파벳을 기억하고 있는 상태입니다. 모든 알파벳을 기억하는 변수(allAlphabet)를 하나 만들어줍니다. 알파벳은 총 26개로 0부터 시작한단 가정 아래 25개의 숫자열이 탄생하게 됩니다. 초기에는 전부 기억하고 있으니 아래 첨부된 표처럼 26개의 1이 나열된 숫자열이..
2022.08.13 -
[백준] 2293 동전 1
※ 사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 접근 1) K이 동전으로 만들어야하는 가치의 합이면, 이번 문제의 점화식은 dp[K]+=dp[K-동전의 액수] 이다. 어떤 방식으로 이런 점화식이 탄생하게 되었는지 천천히 알아보도록 하겠다. 예시) 동전의 종류=[1원, 2원, 3원]이고 가치의 합 K=5 인 경우 K를 1부터 5까지 하나씩 증가시키며, 가지고있는 동전을 점진적으로 늘려가며(처음에는 ..
2022.01.29 -
[백준] 11660 구간 합 구하기 5 파이썬, 자바 풀이
※ 사용언어 : 파이썬, 자바 ※ ▼ 문제 링크 ▼ https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 접근 1) 다이나믹 프로그래밍 알고리즘을 이용해, (1,1)부터 시작해 각 구간의 누적 합을 구한다. EX) (1,1) ~ (3,4) 까지의 구간 누적합 구하기 (3,4) 까지의 누적합은 (1,1)~(3,3) 누적합과 (1,1)~(2,4)까지 누적합을 더하고 배열[3][4]을 더하면 된다. 하지만 ..
2021.10.01 -
[알고리즘] 소수 판별
※ 사용 언어 : 자바, 파이썬 1. O(N) 시간 복잡도의 소수 판별 소수인지 판별할 수 N의 이전 값(=N-1)까지 2부터 for 문을 돌리는 방식이다. 해당 알고리즘은 N의 값 만큼 돌아간다. 『파이썬』 N=int(input()) if(N
2021.09.19