본문 바로가기

프로그래밍/Algorithm109

[프로그래머스 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] 1929번 소수 구하기 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 기존 풀이 코드 바로 시간 초과가 출력됨, 기존 방식으로는 해결이 불가능 에라토스테네스의 체를 사용해야지 문제가 원하는 시간복잡도에 맞출 수 있을거라고 찾음 using System; using System... 2024. 2. 21.
[백준 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.
[백준 BAEKJOON] 2557번 Hello World 문제 Hello World!를 출력하시오. 입력 없음 출력 Hello World!를 출력하시오. 2557번: Hello World Hello World!를 출력하시오. www.acmicpc.net 풀이 코드 using System; class Program { static void Main() { Console.WriteLine("Hello World!"); } } 2024. 2. 16.
C# 힙 트리(Heap tree) 구현 힙 트리(Heap tree) 구현완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 힙 트리(Heap)의 종류최대 힙(max heap)부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리key(부모 노드) >= key(자식 노드)최소 힘(min heap)부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리key(부모 노드) >= key(자식 노드) 힙 트리(Heap tree)의 구현힙을 저장하는 표준적인 자료구조는 배열이다.구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용하지 않는다.특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.힙에서의 부모 노드와 자식 노드.. 2024. 2. 5.

티스토리툴바