세모

[백준/실버1] 백준 28117번 prlong longf - c++ (dp) 문제 모든 int가 longlong으로 바뀐 문자열이 주어진다. 가능한 원래 문자열은 모두 몇 가지인가? -> longlong을 int로 바꿀 수 있는데 만들 수 있는 문자열의 개수 문제 해설 long => A로 치환 int => B로 치환 AA -> B로 바꿀 수 있음 long의 개수 나올 수 있는 경우 경우의 수 A(1) / 0 X 1 AA (2) AA / B 2 AAA (3) BA / AB / AAA 3 AAAA (4) BAA / ABA / AAB / BB / AAAA 5 (2+3) AAAAA (5) BAAA / ABAA / AABA / AAAB BBA / BAB / ABB / AAAAA 8 (3+5) AAAAAA (6) ..

알고리즘/C++ 2024. 4. 11. 18:23

[백준/실버1] 백준 2502번 떡 먹는 호랑이 - c++ ( dp) 어렸을 때 풀었던 그냥 값을 무작정대입하는 방정식과 같은 문제다. 다른 dp문제는 점화식 세울 때 초기 값을 세우기 쉬웠는데 예) 피보나치 1 1 .. 이건 초기값이 하나밖에 주어지지 않았다. 그래서 거꾸로 가는 방식으로 채택해야하는데 이것도 초기값이 주어진게 하나밖에 없어서 쉽지 않았다. 그래서 어렸을 적 배운 방정식을 이용해보았다. 1 2 3 4 5 6 a b a+b a+2b 2a+3b 3a+5b 이렇게 나온다. 그래서 이걸 어떻게 구현해줄수 있을까... 고민하였다. 사실 저 식은 진짜 금방알아냈는데 이걸 코드로 어떻게 구현하고, 시간 초과가 되지 않을지 너무너무 고민되었다.. 스택으로 풀어야할지.. 그냥 단순하게 변수로 개수를 정..

알고리즘/C++ 2024. 4. 10. 11:52

[백준/실버4] 백준 1920번 수 찾기 -c++ 이분 탐색 / 자료구조 / 정렬 하나하나 비교해가면서 풀면 100% 시간초과가 날 것이다. 해당 문제는 이분 탐색의 교과서 같은 문제 이분 탐색은 맨 오른쪽, 왼쪽 점을 잡은 뒤 mid 를 정하고 또 이걸 반복해주는 것이다. 중요한 것은 "정렬"을 해줘야 한다는 점이다. 그래야 12345 라고 쳤을 때 mid인 3보다 목표 숫자가 작으면 그 앞에 있거나 없거나 하고 크면 뒤에 있거나 없거나 하면서 비교해볼 수 있기 때문이다. 1) 직접 구현 #include using namespace std; int n,m, num; vector v; int binary_search(int a){ int r=n-1, l=0; while(r>=l){ int mid = (r..

알고리즘/C++ 2024. 4. 4. 13:21

[백준/실버3] 백준 15649 N과 M(1) - c++ (dfs/ 백트레킹) N과 M 시리즈는 엄청 많아서 1을 통해 dfs랑 백트래킹을 익히는 것에 초점을 뒀다. 그리고 해당 코드를 암기해서 다른 것들에 응용하는게 수월할 것 같다. 코드 #include using namespace std; int n, m; int arr[9]; int arred[9]; void dfs(int idx){ if(idx == m){ for(int i=0; i dfs(2) -> if문 실행 > arred[2] =0; 2)(idx ==1 인 상태) arred[3] ==0 -> arr[1] =3 arred[3] =1; -> dfs(2) -> if문 실행 -> arred[3] =0; 3)(idx ==1 인 상태) arred[4]..

알고리즘/C++ 2024. 3. 23. 18:26

[백준/실버5] 백준 10814번 나이순 정렬 - c++ (정렬 알고리즘) 문제 해석/코드 설명 코딩테스트 타파하기 1주차 - 3번 문제 해석 1. 나이 순으로 정렬 2. 나이가 같으면 가입한 순 (값이 들어간 순서대로) 중요한 함수 sort() 기존 순서를 보장하지 않는다. stable_sort() 기존 순서를 보장한다. 문제에서 입력된 순서로 출력을 원했으니 stable_sort를 이용해줘야한다. vector v; // 에 값 넣는 법 cin >> age >> name; v.push_back(make_pair(age, name)); vector v(n); // -> 크기 지정 cin >> v[i].first >> v[i].second; 전체 코드 #include #include #include usi..

알고리즘/C++ 2024. 3. 14. 11:49

[프로그래머스/1단계] [1차] 다트 게임 - c++ 정말 어려웠던 문제 🥹 너무 복잡하게 생각하지 말라고, 공통된 요소들을 묶어서 바라보는 것이 좋음을 알게 해준 !! 알고가면 좋은 것들 n^a #include pow(n, a); if (isdigit(dartResult[i])) { // 현재 문자가 숫자인 경우 dartResult[i])-'0' 해주면 문자-> 숫자 풀이방법 : 주석 #include #include #include using namespace std; int solution(string dartResult) { int answer = 0; int score[3] = {0}; // 세 번의 점수를 저장할 배열 int idx = 0; // 현재 처리 중인 인덱스 for (int i = 0..

알고리즘/프로그래머스 1단계 2024. 3. 9. 12:02

[프로그래머스 1단계] 바탕화면 정리 - c++ 풀이방법 result : [시작 y좌표 , 시작 x 좌표 , 끝 y좌표, 끝 x좌표] 를 출력해줘야한다. 시작지점 x,y좌표(start_x,start_y) 는 제일 크기가 작아야 하니깐 제일 작은 것을 넣어준다 근데 0으로 초기화 하면 첫 값이 1 일때 값이 안들어가는 상황이 발생하므로 무조건 첫 수보다 큰 수인 1000으로 초기화 해줬다. 종료지점 x,y좌표(lastline_x,lastline_y) 은 제일 크기가 커야한다. 그래서 그냥 무조건 0보다 크니깐 0으로 초기화 해서 변수를 설정해줬다. 그리고 키포인트가 마지막에 lastline_x,lastline_y좌표에 +1을 해줘야한다는 것이다. 마우스 보면 #이 위치한 곳이 아닌, +1+1해준 (#을 포..

알고리즘/프로그래머스 1단계 2024. 3. 9. 11:51

[프로그래머스/1단계] [PCCE 기출문제] 10번 / 데이터 분석 - c++ 정답률이 되게 낮은 문젠데 다른 문제들보다 오히려 쉽게 풀렸다. 풀이방법 사실 조건이 다 나와있지 않아서 처음에는 어렵게 다가왔다. 날짜는 무조건 작은게 맞지만 다른 것들은 작아야하는지 .. 커야하는지 .. 안나와있어서 도박식으로 다 작다고 조건을 넣었다. 1. val_ext 조건에 맞는 데이터만 answer에 넣어준다. 2. 그 뒤 전역변수 num을 선언해줘서 내가 원하는 정렬 조건(sort_by)을 num에 넣어서 만들어준다. 3. num에 들어간 수를 바탕으로 index어디가 기준인지에 따라서 정렬해준다. bool compare(vector& a, vector& b) { return a[num] < b[num]; } ve..

알고리즘/프로그래머스 1단계 2024. 3. 7. 13:53