티스토리

꾸준히하자아자

검색하기

블로그 홈

꾸준히하자아자

gguzunhee.tistory.com/m

방학 기념 개발블로그 작성하기

구독자: 0

방명록 방문하기

주요 글 목록

[프로그래머스] 소수 찾기- level1 프로그래머스 문제 중 "소수 찾기"라는 문제를 푸는데 이렇게 풀었더니 몇몇 테스트케이스에서 오류초과가 났다. 구글링을 했더니 "에라토스테네스의 체" 라는 방법을 알게 되었다. "에라토스테네스의 체" 란? 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법. 1. 1은 제거 2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다. 3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다. 4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다. 5. (반복) 답 def solution(n): answer = set(range(2,n+1)) for i in range(2,n+1): if i in a.. 공감수 0 댓글수 0 2023. 3. 8.
[백준]15649번 N과 M(1) c/c++ baaaarking dog 님 알고리즘강의 백트래킹파트를 참고하여 작성한 글입니다. 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 설명 백트래킹이란?? 현재상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. 가지치기처럼 그러셔 모든 경우의 수를 따라 그려볼 수 있다 (상태공간트리 라고도 불린다) arr는 m개 만큼 원소를 담을 배열 isused는 1~N까지의 숫자가 사용되었는지 안되었는지 확인하는 배열 사용 - True.. 공감수 1 댓글수 0 2022. 8. 26.
[백준]1629번 곱셈 c/c++ baaaaarking dog님 알고리즘 강의를 참고한 내용입니당 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 설명 재귀 문제를 풀때 절차지향적 사고로 풀기보단 귀납적 사고로 푸는것이 좋다. (절차지향적 사고로 생각하려다가 머리속이 꼬일 수 있기때문에) 그럼 귀납적 방법이란게 뭐냐?? 1번 도미노가 쓰러진다 k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다. 이 문제는 b가 최대 21억 가까이 되기때문에 시간초과가 발생할 것이다. 이 사진의 로직을 이용하면 1승을 계산할 수 있다. k승을 계산했으면 2.. 공감수 0 댓글수 0 2022. 8. 25.
[백준]1431번 시리얼 번호 (sort 함수 응용) 문제 https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 코드 #include #include #include #include using namespace std; bool com(string& a, string& b) { int sum_a = 0; int sum_b = 0; if (a.size() != b.size()) //1. 길이가 다르면 짧은것 먼저 return a.size() < b.size(); for (int i = 0; i < .. 공감수 0 댓글수 0 2022. 8. 16.
[백준]1463번 1로 만들기 c/c++ 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 설명 이 문제는 DP로 풀 수 있다. 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정의하기 이 세가지 과정을 거쳐 문제를 풀 수 있다. 1. 테이블 정의하기 D[i]= i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값 2. 점화식 찾기 D[12] =? D[1]부터 D[11]까지의 값을 다 알고 있다고 가정하면 1, 2, 3, ..., 11을 1로 만들기 위한 최소 횟수를 다 알고 있다고 하면 이런 상황에서 D[12]를 구하는 방법은 12에서 할 수 있는 연산을 생각하면 된다. D[4], D[6.. 공감수 0 댓글수 0 2022. 8. 4.
[백준]2217번 로프 c/c++ 문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 설명 처음엔 이 문제가 이해가 잘 안갔다. 설명해보자면 만약에 18짜리 중량인 물체가 있다면 버틸수 있는 최대 중량이 6인 로프 3개로 물체를 들 수 있다. 반대로 위에서 말한 6짜리 로프 3개로는 로프 1~3개를 이용하여 6, 12, 18 짜리 중량인 물체를 들수 있는데 그 중에 최대 중량은 18이기 떄문에 답은 18이 된다. 로직을 생각해보면 만약에 버틸 수 있는 최대중량이 1,.. 공감수 0 댓글수 0 2022. 8. 2.
[백준]1931번 회의실 배정 c/c++ 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 설명 회의시간들을 끝나는시간이 빠른순으로 정렬하고 끝나는시간이 동일하다면 시작하는 시간이 빠른순으로 정렬한다. (회의시작과 끝나는시간이 같을수도 있기 떄문에!!) 따라서 시작하는 시간, 끝나는 시간을 pair 에 반대로 저장해주었다. t는 현재 시간이며, 0으로 초기화 해두고 제일 먼저 끝나는 회의시간을 t로 초기화 해두고 cnt값도 증가시킨다. for문을 돌리며 다음 회의 시작시간 > n; for (int i = 0; i > s[i].second >> s[i].first; }.. 공감수 0 댓글수 0 2022. 8. 2.
[백준]11047번 동전 0 c/c++ 문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 설명 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식이다. 그리디 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 왜 그리디 알고리즘 인가?? 이렇게 단순하게 거스름돈을 지불해야 하는 상황에서 큰 동전만을 생각하고 다른 동전은 생각하지 않기 때문에 매순간 최적이라고 생각되는 경우를 선택하는 그리디 알고리즘이라.. 공감수 0 댓글수 0 2022. 8. 2.
[백준]3273번 두 수의 합 c/c++ 문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i > n; for (int i = 0; i > arr[i]; } int x; cin >> x; int .. 공감수 0 댓글수 0 2022. 8. 1.
[백준]1475번 방 번호 c/c++ 문제 https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 코드 #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); // N=0 일때는 max 값은 1이므로 ans를 1로 둔다. int N, a[10] = {}, ans = 1; cin >> N; // 자리수 추출 while (N) { //정수 0을 제외한 값은 모두 1(true)의 값을 갖는다. a[N % 10]++; N /= 10; } for (int i = 0; i < 10; i++) {.. 공감수 0 댓글수 0 2022. 8. 1.
[백준]1926번 그림 c++ https://blog.encrypted.gg/941?category=773649 를 참고하였다. 문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 설명 구해야 하는것은 2가지 이다. 1. 그림의 개수 2. 그림중 넓이가 가장 넓은 것의 넓이 1. 을 구할땐 큐에서 pop을 몇번 했는지 세어주면 되고 2. 는 이중 for문을 돌려 bfs의 시작점이 될 수 있는지를 체크해주면 된다. 코드 #include #include #include #inclu.. 공감수 0 댓글수 0 2022. 7. 28.
[백준]11653번 소인수분해 c++ 문제 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 코드 #include using namespace std; int main() { int n; cin >> n; if (n == 1)return 0; for (int i = 2; i 공감수 0 댓글수 0 2022. 7. 19.
[알고리즘 개념] 동적 계획법 (Dynamic Programming) -(1) 인프런 강의 참고 동적 계획법 (Dynamic Programming) 이란 (출처 나무위키) 동적 계획법이란 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 이다. 즉, 답을 재활용!! 한다고 생각하면 쉽다. 기본적으로 분할 정복 알고리즘과 비슷하다. 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다. +동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 이름과는 달리 딱히 다이나믹하지도 않고 프로그래밍이라는 단어와도 큰 연관이 없다. 예시 피보나치 수열 //재귀함수를 이용한 피보나치 수열 함수 int fib(int n) { if (n == .. 공감수 0 댓글수 0 2022. 7. 19.
[알고리즘 개념] 삽입 정렬 (insertion sort) c++ 삽입정렬 삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. + 손 안의 카드를 정렬하는 방법과 같다. 새로운 카드를 정렬된 카드 사이의 알맞은 사이를 찾아 삽입해준다. 두번째 원소부터 시작하여 그 앞 원소들과 비교하여 삽입할 위치를 지정하고 원소를 뒤로 옮기고 그 자리에 원소를 삽입하여 정렬한다. 삽입정렬 GIF 이런식으로 두번째 원소부터 마지막 원소까지 정렬된 앞 원소들과 비교하여 알맞은 위치를 찾아 삽입한다. 역시 gif가 이해가 잘된다... C++로 구현 #include using namespace std; int a[10] = { 3,6,7,1,4,2,9,0,5,8 }; void insertion.. 공감수 0 댓글수 0 2022. 7. 19.
[알고리즘 개념] 버블 정렬 (bubble sort) c++ 버블 정렬 버블정렬 (bubble sort)란 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간복잡도가 O(n^2)로 상당히 느리지만 코드가 단순하기 때문에 자주 사용된다. (출처 위키백과) GIF 으로 개념이해 오름차순정렬을 하게되면 첫번째 원소와 두번째 원소를 비교하여 첫번째 원소가 두번째 원소보다 크면 두 원소를 교환하고 두번째 원소와 세번째 원소를 비교하고, 세번째 원소와 네번째 원소를 비교하고 이런식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 정렬한다. 이런식으로 1번 처음부터 끝까지 수행하게 되면(1회전 후) 배열의 가장 큰 원소가 맨 뒤로 이동하므로 2회전을 수행할때는 맨 끝에 있는 원소는 정렬에서 제외된다. 1회전을 할때 교환이 이루어지지 않으면 정렬이 된 상태라고 볼 수 있는.. 공감수 0 댓글수 0 2022. 7. 19.
[알고리즘 개념] 선택 정렬 (selection sort) c++ 선택정렬 선택정렬 (selection sort)은 제자리 정렬 알고리즘의 하나이다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 이 1,2,3을 계속 반복하는 알고리즘이다. 이런식으로 처음엔 첫번째 원소부터 마지막 원소중 최소값을 찾아 배열 맨 앞에 있는 원소와 교환하고 (정렬된 첫번째 원소를 제외한) 두번째 원소부터 마지막 원소중 최소값을 또 찾아 배열 두번쨰 원소와 교환하고 배열 마지막 원소는 자동으로 정렬되기 때문에 원소 개수 -1 만큼 반복해 주면 된다. C++ 로 구현 #include using namespace std; int a[10] = { 3,6,7,1,4,2,9,0,5,8 }.. 공감수 0 댓글수 0 2022. 7. 17.
[알고리즘 개념] 퀵 정렬 (quick sort) c++ 이후에 추가로 알게된 것들을 계속 추가 할 예정이다. 인프런 강좌 내용을 참고하였습니다, 퀵 정렬 (quick sort) 퀵정렬은 분할정복 방법을 사용합니다. 분할정복방법이란 순환적(recursive)으로 문제를 푸는 하향식(top-down) 접근방법입니다. 분할: 배열을 pivot 을 기준으로 pivot보다 작은 값들과 pivot 보다 크거나 같은 값으로 두 부분으로 나눈다. 정복: 각 부분을 순환적으로 정렬한다. 합병: nothing to do (필요x) 슈도코드 A배열의 첫번째 원소를 p, 마지막 원소를 r로 설정한다. 마지막 수를 pivot으로 뒀을때 그 pivot이 어디에 위치해있는지 구하는 partition 함수를 이용한다. 검사하려는 값이 pivot보다 클때, 결국 오른쪽에 있는 원소들 값이.. 공감수 0 댓글수 0 2022. 7. 16.
[백준]1978번 소수 찾기 c/c++ 문제 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 풀이과정 & 코드 디게 간단한데 쓸데없이 허우적거렸던 문제... #include using namespace std; int main() { int tc; cin >> tc; //테스트케이스 개수 입력 int result = 0; for (int i = 0; i > num; int cnt = 0; for (int j = 1; j 공감수 0 댓글수 0 2022. 7. 11.
[백준]1406번 에디터 c/c++ 문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제 설명 P ? : ?라는 문자를 커서 왼쪽에 추가 L : 커서를 왼쪽으로 한칸 옮김 (커서가 문장의 맨 앞이면 무시됨) D : 커서를 오른쪽으로 한칸 옮김 (커서가 문장의 맨 뒤면 무시됨) B : 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) - 커서를 기준으로 스택을 두개로 나눈다. #include #include #include using namespace std;.. 공감수 0 댓글수 0 2022. 7. 11.
[백준]9093번 단어 뒤집기 c/c++ 문제 https://www.acmicpc.net/problem/9093 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net 나의 해결방법 주석으로 설명하였다. 다른 분들의 풀이를 보고 해결책을 얻었다. #include #include #include using namespace std; int main() { int tc; cin >> tc; //테스트케이스 개수 cin.ignore(); //버퍼 제거 while (tc--) { string s = ""; getline(cin, s); s += ' '; /.. 공감수 0 댓글수 0 2022. 7. 11.
[백준]2750번 수 정렬하기 c/c++ 문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 해결방법 algorithm 헤더의 sort 함수를 이용하였다. vector 헤더를 사용해서 숫자를 저장해주었다. 코드 #include #include #include using namespace std; int main() { int tc, num; cin >> tc; vector v; for (int i = 0; i > num; v.push_back(num); } s.. 공감수 0 댓글수 0 2022. 7. 5.
[백준]1152번 단어의 개수 c/c++ 문제 https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열 www.acmicpc.net 해결방법 공백을 만날때 count값을 증가시킨다. 문자열이 공백으로 시작하거나 공백으로 끝날때는 count값을 하나 감소시킨다. 코드 #include #include using namespace std; int main() { string s; getline(cin, s); int count = 1; for (int i = 0; i < s.length(); i++) { if (s[i] .. 공감수 0 댓글수 0 2022. 7. 4.
[백준]2675번 문자열 반복 c/c++ 문제 https://www.acmicpc.net/problem/2675 2675번: 문자열 반복 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다 www.acmicpc.net 해결방법 이처럼 첫번째 for문은 test case 개수만큼 돌리고 두번째 for문은 문자열 s의 길이만큼 돌리고 세번째 for 문은 반복해줄 만큼 num만큼 돌린다. #include #include using namespace std; int main() { int tc; cin >> tc; for (int i = 0; i > num.. 공감수 0 댓글수 0 2022. 7. 2.
[백준]9613번 GCD 합 c/c++ 문제 https://www.acmicpc.net/problem/9613 나의 해결방법 유클리드 호제법 이용 https://velog.io/@minjukwak/%EB%B0%B1%EC%A4%80-1934-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98-1v1ja0y4 코드 #include using namespace std; int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } int main() { int t; cin >> t; int a[100]; for (int i = 0; i > n; //각 테스트케이스 마다 n개의 수 입력 for (int j .. 공감수 0 댓글수 0 2022. 7. 1.
[백준]1934번 최소공배수 c/c++ 문제 https://www.acmicpc.net/problem/1934 나의 해결방법 유클리드 호제법, 순환을 이용하여 풀이하였다. 순환을 이용하여 푸는 방법이 훨 간단하다. 반복을 이용한 풀이 : https://velog.io/@minjukwak/%EB%B0%B1%EC%A4%80-2609-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EC%99%80-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98 코드 #include using namespace std; int gcd(int a, int b) { if (b == 0) { return a; } else return gcd(b, a % b); } int main() { int n; ci.. 공감수 0 댓글수 0 2022. 7. 1.
[백준]10992번 별 찍기-17 c/c++ 문제 https://www.acmicpc.net/problem/10992 나의 해결방법 첫번째 for문은 출력해줄 줄의 수 - 1 두번째 for문은 파란색 / 기준으로 왼쪽에 있는 공백 분홍색 하이라이트 * 을 출력 세번째 for문은 공백 출력 (0,1,3,5...개) 초록색 하이라이트 * 을 출력 (첫번째 줄은 출력 안해주므로 i>1일때만) 마지막 줄은 입력해준 n의 2n-1개수의 \ 을 출력 코드 #include using namespace std; int main() { int n; cin >> n; for (int i = 1; i < n; i++) { //4를 입력해줬을때 3번째 줄까지만 출력 for (int j = 1; j 공감수 0 댓글수 0 2022. 7. 1.
[백준]10991번 별 찍기-16 c/c++ 문제 https://www.acmicpc.net/problem/10991 나의 해결방법 이렇게 /를 기준으로 두개의 구역으로 나눠서 따로 for문을 작성해주었다. 코드 #include using namespace std; int main() { int n; cin >> n; for (int i = 1; i 0; j--) { // /을 기준으로 왼쪽 cout 공감수 0 댓글수 0 2022. 7. 1.
[백준]2522번 별 찍기-12 c/c++ 문제 https://www.acmicpc.net/problem/2522 나의 해결방법 2445번과 동일한 방법으로 풀었다. 코드 #include using namespace std; int main() { int n; cin >> n; for (int i = 1; i 공감수 0 댓글수 0 2022. 7. 1.
[백준]2445번 별 찍기-8 c/c++ 문제 https://www.acmicpc.net/problem/2445 나의 해결방법 5를 입력했을때 1~5번째 줄 따로, 6~9번째줄을 따로 출력해준다. 코드 #include using namespace std; int main() { int n; cin >> n; for (int i = 1; i 공감수 0 댓글수 0 2022. 7. 1.
[백준]9012번 괄호 c/c++ 문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 코드 #include #include using namespace std; int main() { int tc; cin >> tc; //테스트케이스 string ps; for (int i = 0; i > ps; //문자열 입력 stack stk; //스택 초기화 for (int j = 0; j < ps.length(); j++) .. 공감수 0 댓글수 0 2022. 6. 27.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.