본문 바로가기

Coding Test32

[BoJ] #1182 부분 수열의 합 / c++ https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 부분수열의 합 2 초 256 MB 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 .. 2023. 7. 27.
[코테 한 알] 자료구조 / 투 포인터 1. 투 포인터란 ? 2개의 포인터를 이용하여 구간의 시작과 끝을 제한하는 방식 2. 투 포인터의 시간복잡도 포인터를 이동하는 계산이 전부이므로, O(n)의 시간복잡도를 가진다. 따라서 큰 수를 다루는 계산에 유리하게 사용된다. 3. 투 포인터 예제 [BOJ 2018] 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. 예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다... 2023. 6. 28.
[코테 한 알] 시작 🍏 방학을 맞아 알고리즘 정리를 시작하려 한다. 기본적인 알고리즘부터 코테에 필요한 스킬까지 정리할 생각이다. 방학 내 완주를 목표로 화이팅! 참고 도서 | Do it 알고리즘 코딩 테스트 C++ 2023. 6. 28.
[C++ 줍줍] next_permutation과 순열/조합 1. header #include 2. 순열 next_permutation(v.begin(), v.end()) ex. v = {1, 2, 3, 4} (1) 입력 벡터가 다음 순열로 바뀌면서 true를 리턴 : v={1, 2, 4, 3}, true 리턴 (2) 마지막 순열까지 모두 바뀌었다면 false를 리턴 : v={4, 3, 2, 1}, false 리턴 따라서, (1)때문에 while문이 아닌 do-while문을 사용해야 하고 (처음 자신 포함하려고) (2)때문에 while문 조건문이 next_permutation이 된다. void permutation() { int arr[] = { 1, 2, 3, 4 }; do { for (int i = 0; i < 4; i++) { cout 2022. 9. 20.
[C++ 줍줍] 올림, 내림, 반올림 ▷ 문제 상황 1 숫자를 올림, 내림한 결과를 알고 싶다 ! ▶ 해결 방법 1 ceil( ), floor( ) 메소드를 이용 * 헤더 : #include int c1 = ceil(2.2); // c1 = 3 int f1 = floor(4.7); // f1 = 4 ▷ 문제 상황 2 숫자를 반올림한 결과를 알고 싶다 ! ▶ 해결 방법 2-1 floor( ) 메소드와 0.5 이용 * 헤더 : #include int f1 = floor(4.7 + 0.5); // f1 = floor(5.2) = 5 int f2 = floor(4.2 + 0.5); // f2 = floor(4.7) = 4 ▶ 해결 방법 2-2 round( ) 메소드이용 * C++ 11 부터 사용 가능 * 헤더 : #include int c1 = r.. 2022. 9. 5.
[C++ 줍줍] 문자열 자르기 : substr( ) ▷ 문제 상황 문자열에서 원하는 만큼만 잘라내서 사용하고 싶다 ! ▶ 해결 방법 substr( ) 메소드를 이용 # substr( ) 사용법 1. 시작 인덱스, 길이 string s1 = "Happy"; string s2 = s1.substr(1, 3); // s2 = "app"; 2. 시작 인덱스만 이용 : 그 위치부터 끝까지 string s1 = "Happy"; string s2 = s1.substr(1); // s2 = "appy"; 2022. 9. 5.
[알튜비튜 줍줍] sort 함수 정리 std::sort 1. parameter 배열의 시작 위치, 끝 위치 2. 정렬 기준 [default] 오름차순 [custom] sort 함수의 3rd 인자로 다양한 비교함수 cmp를 넣어주면, 그 함수 기준으로 정렬 가능 ※ 내림차순 : sort ( , , greater()) ※ cmp (int a, int b) ① a가 b의 앞에 와야 할 경우 true를 리턴하게끔 설계 bool cmp(int a, int b) { if(a > b) return true; // a >= b 하면 안됨 return false; } ② a와 b의 우선순위가 같으면 false 반환해야 함 ( false를 리턴하는 경우, swap 한다는 사실을 숙지하고 있자! ) ③ cmp의 인자로 STL이나 클래스 객체가 전달되는 경우, .. 2022. 9. 3.
[프로그래머스 Lv.2] 게임 맵 최단거리 / c++ [출처] https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ▷▷ 문제 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시.. 2022. 8. 29.
[C++ 기초] 템플릿 1. 템플릿 1-1. 템플릿이란 ? 인스턴스를 생성하기 위한 틀은 클래스! 이와 유사하게, 함수나 클래스를 생성하기 위한 틀이 템플릿 이때, 템플릿은 모든 타입을 대변하는 T 타입을 이용해서 선언되는데, 덕분에 T 자리에 어떤 타입이 들어오는지에 따라 다양한 함수, 클래스를 생성할 수 있다. 🔔 제네릭(Generic) 프로그래밍 이처럼 일반화된 틀(템플릿)에 다양한 인자를 전달함으로써 여러가지 함수, 클래스를 만드는 프로그래밍 💥 템플릿 인스턴스화 (구체화) 정의된 템플릿에 구체적인 데이터 타입을 가진 인자를 전달함으로써 실제 함수, 클래스를 생성하는 과정 1-2. 템플릿의 종류 (1) 클래스 템플릿 (2) 함수 템플릿 1-3. 템플릿 선언 방법 template template 2. 함수 템플릿 2-1... 2022. 8. 18.

티스토리툴바