개발 노트/백준, 프로그래머스 풀이165 백준 4375/c++ )) 1 모듈러 연산에 대한 이해 1 , 11, 111, 1111, 11111 식으로 늘어나는 수 중에 입력한 a의 수의 배수인(a으로 나눠서 나머지가 0인) 최소값의 자리수를 구하는 문제이다 c++의 경우 표현할 수 있는 숫자의 크기가 정해져있으므로 자리수도 무한정 늘릴 수 없다 자리수가 올라갈때마다 자리수 nu에 ++ 해주고, 규칙에 의해 자리수가 올라가고 새로 취한 수는 모듈러 연산을 이용하여 나머지 값만 취하고 a의 배수인지 확인, 나머지가 0이면 배수이므로 그때의 자리수를 출력, 그렇지 않으면 다시 일정한 규칙으로 수를 기존 나머지값에 적용하여 반복하여 구하는 문제이다 입력의 경우 끝나지 않고 계속 받으므로, "cin.eof() 입력의 끝" 이 "아니다 ! " 가 참일 동안 while 을 통해 입력을 계속 유지하였다 while(.. 2022. 6. 17. 백준 1629/c++ )) 곱셈 - divde and conquer, 재귀함수 그대로 주는대로 계산하면 연산시간이 너무 길어서 시간 초과하는 문제이다 재귀 함수로 분할정복 divde and conquer를 사용하여 연산 수를 줄이고, 각 입력의 최대값이 int 의 최대치 값 이므로 long long 을 사용하여 결과값의 오버플로우를 1차로 막는다 분할한 값을 합칠때 큰 수끼리의 곱셈을 해야하므로 long long 뿐 아니라 %c 로 모듈러 연산을 해줘서 2차로 오버플로우를 막아야 하는 문제이다 재귀함수라지만 내가 gr로 작성한 부분이 gr=gr*gr 이고 gr=gr*a%c 이라는 부분에서 왜인지 이해하느라 머리가 터졌고 시간도 몇시간을 걸려서 이해했지만, 이해했으니 비슷한 유형도 이제 익숙해질것이다 내일을 공부를 위해 더 늦기전에 자자... #include using namespa.. 2022. 6. 17. 백준 1940/c++ )) 주몽 - 투포인터 사용 처음엔 총 합을 구해서 특정 수로 나눈 답을 카운트 하는 너무너무 간단한 문제인줄 알았는데 그럼 그렇지 너무 쉽다 했다 투 포인트를 써서( 두개의 포인터 알고리즘) 풀면 답이 쉽고 빠르게 나온다 투포인터는 사용한 값은 제외하고, 순서 상관없이 두개의 합이나 중복되는 구간합을 구할때 사용하는것 같다 처음 마주한 개념이라 이해와 에러 잡기가 상당히 시간이 걸렸다 아래에 투포인트를 써서 푼것과 이중 for문을 쓴 것 모두 올려보겠다 투 포인터 사용해본 코드 #include using namespace std; int n, m; int main(){ int cnt=0; int sum=0; int a[15004]; cin >> n; cin >> m; // 시작 요소 인덱스 int ptS=0; // 마지막 요소 인.. 2022. 6. 16. 백준 3986/c++ )) 좋은 단어 - 스택 사용 개선답 이전 풀이는 수열의 규칙을 찾아서 풀려고 하다가 반례가 나와서 실패했다 스택을 통해서 테트리스처럼 새 단어와 stack 맨 위의 단어가 같으면 top을 pop 해서 없애주고 top과 새 단어가 다르면 stack 에 push 하여 쌓는 과정을 통해서 쉽게 코드를 짤 수 있었다 느낀점 : 문제에 맞는 최적의 자료구조를 이용하여 로직을 짜야 시간낭비도 적고, 정확도도 높은 코드를 작성가능하다 #include using namespace std; int n; string s; int main(){ int cnt=0; // 여기에 스택 선언 시, 아래 for문에서 돌때마다 스택안 값들이 남아있어서 에러가 난다 cin >> n; for(int i=0; i> s; // 한번 돌때마다 새로 stk 를 선언, 새 스택을.. 2022. 6. 16. 이전 1 ··· 36 37 38 39 40 41 42 다음
