생각 투 포인터를 사용해서 풀 수 있다. st, en 두 포인터를 둔다. 1. 수들을 입력받아 배열에 저장한다. 2. 수의 합을 저장하는 변수 total은 arr[0]을 더 해주고, 줄의 길이를 저장하는 변수 len은 최대한 큰 수로 둔다(0x7fffffff). 3. en을 0으로 둔다. 4. en이 n보다 작고 total이 s보다 작다면 en을 한 칸 오른쪽으로 옮긴다. 5. 그러고도 en이 n보다 작다면 total에 arr[en]을 더 해준다. 6. 계속 더하다보면 total이 s보다 커진다. 7. 그러면 그 때 en-st+1이 len보다 작다면 len에 en-st+1을 저장한다. 8. st가 다음 칸으로 넘어가기 전에 total에서 arr[st]를 빼준다. 9. 만약 s보다 큰 부분합을 찾지 못했다..
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 생각 투 포인터를 사용하여 문제를 해결 할 수 있다. (투 포인터에 대해서 궁금하다면 밑의 링크를 클릭해서 바킹독님의 강의를 보면 된다. 이 문제에 대한 풀이도 해주신다!) https://www.youtube.com/watch?v=I_0aAKzu0m8&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=21 포인터 두 개 st, en을 둔다. 1...
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 생각 이분탐색을 이용해보자. 1. 나무의 높이들을 입력받아 벡터에 넣고 그 벡터를 오름차순으로 정렬한다. 2. 잘라진 나무의 높이의 합을 입력받는 변수(cnt)를 하나 생성한다. 3. 벡터의 루프를 돌면서 잘라진 나무의 합을 구한다. 4. 처음(st)을 1, 끝(en)을 벡터의 back()으로 놓는다. 5. mid = (st + en + 1) / 2로 놓는다..
https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 생각 페이지를 단순히 읽어나가면서 계산하면 당연히 시간초과가 발생한다. 하지만 아무리 생각해도 내 실력으로는 해결할 수가 없었다. 따라서 밑의 블로그 내용을 참고했다. (그림도 그려가면서 상세히 설명해주셔서 더욱 이해하기에 편리했다.) https://restudycafe.tistory.com/489 [백준/BOJ] 1019번 : 책 페이지 (수학, Counting) (+ Class 6 획득) 이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BO..
현재 노마드코더의 'ReactJS로 영화 웹 서비스 만들기' 강의를 듣고 있습니다. https://nomadcoders.co/react-for-beginners ReactJS로 영화 웹 서비스 만들기 – 노마드 코더 Nomad Coders React for Beginners nomadcoders.co 강의를 따라가면서 create-react-app을 사용하기 위하여 Node.js를 설치하고 명령 프롬프트에서 원하는 폴더로 이동해서 'npx create-react-app .'을 입력했지만, 자꾸 오류가 떴다. 그래서 처음에는 Node.js 버전이 문제인가 싶어서 버전 16으로 다운그레이드도 해보고, 학교 와이파이라서 그런가 싶어서 집으로 이동해서 다시 설치도 해보았다. 하지만 오류는 고쳐지지 않았다. np..
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 생각 그리디 알고리즘을 이용해서 풀어야되는 문제이다. 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. (출처: 나무위키) 현재 선택한 회의가 있다고 가정하자. 그러면 다음에 있는 회의 중에서 가장 종료 시간이 빠른 회의를 선택해야 최대한 많은 회의를 진행할 수 있다. 1. 회의를 종료 시간이 가장 빠른 순서로 정렬한다. (만약 종료 시간이 같다면 시작 시간이 더 빠른 ..
생각 처음에는 BFS나 DFS를 사용하면 될 것 같다고 생각했는데, 이것만 이용하면 시간 초과가 뜬다. 다이나믹 프로그래밍(DP)를 사용해야 되는데, 다이나믹 프로그래밍은 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘이다. 다이나믹 프로그래밍을 사용하려면 세 가지 과정을 거쳐야 하는데, 바로 테이블 정의하기 점화식 찾기 초기값 정하기 이다. 출처: https://blog.encrypted.gg/974 [실전 알고리즘] 0x10강 - 다이나믹 프로그래밍 안녕하세요, 이번 시간에는 다이나믹 프로그래밍을 다룹니다. 직전까지 막 재귀, 백트래킹, 정렬 이런 것들로 되게 고통받으셨을텐데 오늘껀 개념도 그렇게 어렵지 않고 구현 난이도도 낮아서 blog.encrypted.gg..
생각 구조체를 사용해서 풀면 될 것 같다. 문제를 풀 때 시행착오를 겪었는데, 처음에는 struct s s1[100005]로 구조체 배열을 선언했었는데, 그러면 코드가 잘 실행되지 않는다. -> 스택 오버플로우가 발생하기 때문! 구조체 배열을 동적 할당하자. 그리고 정렬을 할 때 그냥 sort를 썼었는데, 그냥 sort를 쓰면 동일한 우선순위를 가진 원소들 사이의 상대적인 순서가 보존되지 않는다. -> sort가 아닌 stable_sort를 써야한다. 코드 #include using namespace std; struct s { // 구조체 선언 int age; string name; }; bool compare(const s& s1, const s& s2) { // 나이가 적은 순서대로 정렬 retur..
생각 수의 개수가 천만개까지 주어진다. 일반적인 방법을 썼다가는 분명히 시간이든 메모리든 초과가 뜰 것 같다. 그래서 그냥 sort는 안될 것 같고, merge sort를 써보기로 하였다. -> merge sort를 사용해도 메모리 초과가 되었다. 그래서 그냥 sort를 써보았다. -> 당연히 안됐다. 왜 자꾸 메모리 초과가 뜰까? 배열을 천만개를 선언해서 그런가? 그러면 벡터를 써볼까? -> 그래도 안됐다. 그렇다면 주어진 수는 10000보다 작으니, 주어진 수를 10000 크기의 배열에 넣고 그 배열을 순회하면서 배열에 들어간 수만큼 그 숫자를 출력한다. -> 몇번의 실패끝에, 드디어 성공했다. 코드 #include typedef long long ll; // 큰 수가 쓰이므로 int 대신 long ..
밑 내용은 노마드코더의 'ReactJS로 영화 웹 서비스 만들기' 강의 중 일부 내용을 포함하고 있습니다. React에 대해서 자세하고 친절하게 가르쳐주셔서 만족하면서 듣고 있습니다. (밑에 링크로 들어가면 수강할 수 있습니다. 무료 강의 입니다.) https://nomadcoders.co/react-for-beginners ReactJS로 영화 웹 서비스 만들기 – 노마드 코더 Nomad Coders React for Beginners nomadcoders.co 이 강의을 듣다보면 Super Converter를 만들게 되는데, Super Converter는 React의 State를 활용해서 시간/분 , 킬로미터/마일 중 변환하고 싶은 것을 골라 데이터를 입력하면 변환을 시켜주는 프로그램이다. 코드 실행..
