본문 바로가기
728x90

ALGORITHM35

[알고리즘 이론] 정렬 알고리즘 정렬 알고리즘이란?배열 등의 데이터 단위를 사용자에 맞춰 순서대로 배치 시켜주는 알고리즘.  선택 정렬 이름과 같이 현제 위치에 들어갈 값을 찾은 후, 정렬하는 알고리즘입니다. 시간 복잡도의 경우 O(n^2)입니다.1. 배열의 크기 만큼 반복문문을 돌려준다. 2. 현제 위치부터 배열의 크기만큼 반복문을 다시 돌려준다. 3. 가장 작은 값을 찾고, 해당 값을 해당 위치와 스왑한다. 4. 2로 돌아간다. int i,j;int aLength;for (i = 0; i   버블 정렬 현제 인덱스의 값과 뒤 인덱스 값을 비교한 후, 큰 값을 뒤로 보내며 정렬하는 알고리즘입니다.시간복잡도는 O(n^2)입니다. 1. 배열 전체를 반복문을 돌려준다. 2. (배열 크기 - 현 인덱스)값만큼 반복분 돌려준다. 3. 현 인덱.. 2024. 8. 18.
[알고리즘 이론] 시간 복잡도와 공간 복잡도 복잡도란, 1. 알고리즘의 성능, 효율성을 나타내는 척도2. 알고리즘의 사용 시간 및 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준 3. 빅오(O), 오메가(Ω), 세타(Θ) 표기법 등이 잇다.  빅-오(Big-O) 표기법 최악의 경우를 나타냅니다.즉, 알고리즘을 실행 했을 때 최대로 걸릴 수 있는 시간을 나타냅니다.  O(1): n이 증가하여도 실행 시간은 동일한 알고리즘 (EX, 기본 연산 수)O(log n): 연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘 (EX, 이진 탐)O(n): n의 값이 증가함에 따라 선형적으로 증가하는 알고리즘 (EX, 1중 for)O(n log n): O(n)의 알고리즘과 O(log n)의 알고리즘이 중첩된 형태 (EX, 퀵 정렬)O(n^.. 2024. 8. 8.
[백준 9461] 파도반 수열 문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 분석 우측에 있는 그림처럼 생긴 그림이 있고, 입력 받은 수의 번째에 생성된 삼각형의 크기가 몇인지 출력하는 문제이다. 알고리즘 설계 우선 테스트 케이스의 개수를 담을 t와 테스트 케이스를 담을 n을 int형으로 선언한다. n이 100 이하로 나오기에 longlong을 가지고 있을 vector을 하나 만들고 크기를 101로 만들어준다. 이후 1, 2, 3번 인덱스는 1로 초기화 시켜준다. 이.. 2023. 11. 30.
[백준 1654] 랜선 자르기 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 분석 잘라서 가져야하는 랜선의 개수가 주어지고, 가지고 있는 랜선의 길이가 주어진다. 랜선을 잘라 개수를 맞추는데 최대한 길게 남겨두고, 또 같은 길이로 자른다면 몇 m로 잘라야 하는지 구하는 문제이다. 알고리즘 설계 우선 얻어야하는 랜선의 개수를 정수형 변수 n으로, 랜선들의 길이를 담을 vector vec을 전역변수로 선언한다. main함수에서 몇개의 랜.. 2023. 11. 24.
[프로그래머스] 의상 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석 입을 수 있는 옷의 종류 얼굴, 상의, 하의, 겉옷 4가지가 있다. 같은 종류의 옷은 같이 입을 수 없지만 다른 종류의 옷, 예시를 들자면 얼굴 얼굴 조합은 안되지만, 얼굴 상의 조합은 되는 것이다. 이렇게 옷의 조합이 몇개가 나오는지 계산하는 문제이다. 알고리즘 설계 우선 unordered_map, key는 string, value는 int로 가지는 um을 선언한다. 또 int를.. 2023. 11. 22.
[백준 2805] 나무 자르기 문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 분석 상근이가 필요한 나무의 조각의 크기와 나무조각들이 주어지고 나무조각을 얼만큼 남기고 짤라야하는지 구하는 문제이다. 다만 최대한 많이 남기고 잘라야한다. 알고리즘 설계 long long을 가진 vector tree를 선언한다. 또 long long n과 m, input을 선언한다. n은 나무의 개수, m은 얻어야하는 나무의 크기, 나무들을 입력.. 2023. 11. 22.
[프로그래머스] 입국심사 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석 입국 심사를 받아야하는 사람의 수 n과 각각의 심사대에서 심사가 걸리는 시간 times가 들어온다. n명의 사람이 모두 심사를 받아야하며 times에 맞춰서 심사가 끝나고, 다음 사람이 들어오는 형태이다. 여기서 중요한 점은 10분이 걸리는 심사대와 1분이 걸리는 심사대가 있고, 1분이 걸리는 심사대에 3명이 줄이 서 있어도 10분 걸리는 심사대는 10분 후 심사가 끝나고, 1분이.. 2023. 11. 22.
[백준 5397] 키로거 문제 https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 문제 분석 문자열이 주어지고, 그 안에 , -들이 섞여 있다. 커서가 존재하고, ''면 왼쪽으로 움직인다. '-'가 입려되면 바로 앞에 있는 값을 지운다. 하나의 커서가 있다고 생각하면 편하다. 알고리즘 설계 입력받을 문자열 str과 몇개의 문자열을 받을지 알려줄 정수형 변수 num을 선언한다. num을 입력 받고 그 수 만큼 반복문을 돌린다. 반복문 안에서 char 인수로 가지는 연.. 2023. 11. 14.
[백준 1920] 수 찾기 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 분석 두가지의 변수 집합이 주어지고, 첫번째 집합에 두번째 집합에 해당하는 변수가 존재한다면 1을, 존재하지 않는다면 0을 출력한다. 알고리즘 설계 정수형 변수 n, m, input, num을 선언하고, int형을 가진 vector v1을 선언해준다 . n은 첫번째 집합의 개수, m은 두번째 집합의 개수, input은 반복문을 돌며 입력 .. 2023. 11. 13.
[백준 25192] 인사성 밝은 곰곰이 문제 https://www.acmicpc.net/problem/25192 25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net 문제 분석 우선 몇 가지의 입력이 있을지 입력 받고, 그 이후 문자열이 들어온다. 문자열이 이전에 들어오지 않은 문자열이라면 값을 하나 올린다. 다만 'Enter'가 들어오면 전에 입력 받은 값들이 초기화 된다. 그렇게 올린 값을 출력하는 문제이다. 알고리즘 설계 우선 입력 받을 값과, 출력할 값을 담을 정수형 변수, 입력 받고 확인할 문자열, 앞에서 입력 받은 문자열인.. 2023. 11. 13.
[백준 11004] K번째 수 문제 https://www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 입력 받을 수의 개수와 몇 번째에 있는 수를 출력할지를 입력받고, 그 수를 오름차순으로 정렬한 후 입력받은 수의 번째에 있는 수를 출력하면 된다. 알고리즘 설계 우선 몇 가지 수를 받을지, 몇 번째 수를 출력할지, 수를 입력 받을 정수형 변수, int가 들어가는 vector를 하나 만들어준다. 이후 몇 가지 수를 받을지와 몇 번째 수를 출력할지 입력 받고 몇 가지 수를 받을지 입력 받은 수 대로 반복문을 돌려준다. 반복문 내부에서 입.. 2023. 11. 13.
[백준 10825] 국영수 문제 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 문제 분석 학생의 이름과 국어, 수학, 영어 과목에 따라 정렬한다. 국어는 감소, 영어는 증가, 수학은 감소, 이름은 사전순으로 정렬해준다. 알고리즘 설계 이름과 국영수 과목의 점수를 입력 받고, 모두 tuple을 가지고 있는 vector에 넣어준다. 이후 sort를 해주는데 compare을 해주어 직접 설정해준다. 국어를 우선으로 감소 순으로, 이후 영어는 증가순, 수.. 2023. 11. 9.
728x90

티스토리툴바