본문 바로가기

알고리즘69

[백준 BAEKJOON] 14928번 큰 수 (BIG) ㅇ문제 제연이는 그의 생일(2000년 3월 3일)을 기념해 자신이 가장 좋아하는 수를 20000303으로 나눈 나머지를 구해 그 수만큼 잠을 자기로 했다. 제연이가 얼마나 잠을 잘 수 있을지 구하자. 입력 첫째 줄에 제연이가 가장 좋아하는 수 N이 주어진다. (N ≤ 101,000,000) 출력 N을 20000303으로 나눈 나머지를 출력한다. 14928번: 큰 수 (BIG) 첫째 줄에 제연이가 가장 좋아하는 수 N이 주어진다. (N ≤ 101,000,000) www.acmicpc.net 풀이 코드 char에 '0'을 빼는 코드가 처음에는 이해하기 힘들었지만 여기저기 찾아보니 아스키코드 관련으로 변환하기 위한 코드였다. 관련된 내용은 아래의 글을 참고하자. using System; class Progra.. 2024. 2. 26.
[백준 BAEKJOON] 6603번 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34]) 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 .. 2024. 2. 26.
[백준 BAEKJOON] 4948번 베르트랑 공준 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다. 입력의 마지막에는 0이 주어진다. 출력 각 테스트 케이스에 대해서, n보다 크고.. 2024. 2. 23.
[프로그래머스 Programmers] 소인수분해 문제 설명 소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요. 제한 사항 2 ≤ n ≤ 10,000 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 코드 using System; using System.Collections.Generic; using System.Linq; public class Sol.. 2024. 2. 22.
[백준 BAEKJOON] 16916번 부분 문자열 문제 문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다. 예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다. 문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자. 입력 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. 출력 P가 S의 부분 문자열이면 1, 아니면 0을 출력한다. 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다... 2024. 2. 19.
KMP 문자열 탐색 알고리즘 KMP 문자열 탐색 알고리즘 글 안에서 단어를 빠르게 찾거나, 문자열을 전처리하여 우리가 원하는 정보를 추출하는 알고리즘은 여러 분야에서 활용이 가능하다. 대표적인 문자열 안에서 단어를 찾는 문자열 탐색 알고리즘으로는 라빈-카프 보이어-무어 KMP 알고리즘 등이 있으며, 문자열 안에서 여러 개의 단어를 동시에 찾는 방법으로 아호-코라식 알고리즘이 있다. 가장 간단한 문자열 탐색 문자열 안에서 특정 단어를 검색하는 가장 간단한 방법은 전부 하나하나 비교하는 것이다. 위처럼 원본 문자열의 맨 앞 문자부터 탐색을 시작하여, 탐색 문자열과 다른 문자가 발견되다면 두 번째 문자부터 다시 비교하는 과정을 계속 반복하는 아주 간단한 방법이다. 위처럼 탐색 문자열을 원본 문자열의 모든 부분에 대해서 비교하는 방식은 매.. 2024. 2. 19.

티스토리툴바