전체 글

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 분석 보석이 N개 있고, 해당 보석의 정보인 무게 M, 가격 V가 주어진다. K개의 가방이 있고, 가방은 각각 C만큼 담을 수 있다. 이때, 가방에 보석을 하나씩만 넣을 수 있다고 할 때, 가져갈 수 있는 최대 보석의 가격을 구하는 문제. dp나 그리디 정도가 떠올랐고, 그리디로 푼다면 보석의 가격이 가장 큰 순서대로, 가방의 무게..

https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr DP를 잘 활용하고, 인덱스와 조건을 유심히 다룬다면 원활하게 풀 수 있는 문제 ! 아래는 오답 분석 및 문제 해결 접근 방법이다. 문제 풀이 모든 문제를 풀기 위해 달성해야하는 알고력, 코딩력의 최대값에 도달해야한다. 위 목표에 도달하기 위해서 a[알고력][코딩력]이라는 배열을 만들어주고, 해당 index에 도달하기 위한 최단 시간을 업데이트하며 dp를 진행한다. 오답 분석 처음에 여기까지 ..

프로그래머스 2022 kako tech internship 두 큐 합 같게 만들기 풀이 중, vector로 푸니까 24번에서 자꾸 시간 초과 나는 오류 발견. 결론은 deque로 구현하면 되고, 나름대로의 분석을 해봤다. 아래와 같이 각 큐의 합을 비교하는 프로세스로 코드를 짜주었다. while(sum1!=sum2){ if(sum1

배경 1) next에서 svg파일을 Image태그로 감싸서 사용하고 있었다. 2) 그러던 중 색상을 props에 따라 변경해줘야하는 상황이 발생했다. (isClick에 따라서 색상 변경) 3) 조건에 따라 다른 색을 가진 svg파일을 렌더링하는 방법도 있었겠지만 색상으로 컨트롤 해보고 싶었다. 검색 결과.. svgr을 통해 svg 파일을 컴포넌트처럼 사용할 수 있다는 걸 알았다. 사용 방법 1. 설치 yarn add -D @svgr/webpack 2. next.config.js 수정 /** @type {import('next').NextConfig} */ const nextConfig = { // 웹팩을 통해 svg 파일을 리액트 컴포넌트로 변환하는 설정이다 webpack: (config) => { co..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 분석 제시된 배열이 있을 때, 배열의 구간합을 구하는 문제. 하지만, 1) 시간 초과가 빡세고 2) 중간에 배열을 update한 뒤에 구간합을 구해야해서 일반적으로 구할 수 있는 구간합 문제는 아니다. 따라서 자식의 노드의 합을 노드로 갖는 segment tree 자료구조를 이용해 풀어야한다. 이때 segment tree를 이용해 ..

시간복잡도 팁 - 1억의 연산 당 1초가 걸린다고 생각하자. - log(1,000,000,000)는 log 안의 0의 개수가 3개면 2^10이라고 가정한다. 즉,log(1,000,000,000)은 2^30(2^10 * 2^10 * 2^10) 번만큼의 연산을 하게 된다. 공간복잡도 팁 - 입력의 제한 조건에 따라 공간 복잡도를 계산한다. - 배열이나, 메모리를 관리할 때 공간복잡도를 차지한다고 생각하면 된다. 이를 유의해서 메모리 초과를 조심하자. 1,000,000,000 | | | G---M---K byte - 만약 출력 값이 100,000 * 100,000이 넘을 경우, long long 자료형을 생각해봐야한다. char : 1byte int : 4byte (100,000,000) long long :..

https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 문제 분석 배열 A와 B가 주어졌을 때, 각 배열의 부분 배열의 합을 더해 원하는 숫자가 되도록 하는 문제. 문제 풀이 처음에는 각각 A, B를 가리키는 투 포인터로 문제를 해결해보려고 했지만, 생각보다 이중 투 포인터를 하는 방식이 까다로워 다른 블로그를 참고해 이중탐색으로 풀었다.이중 탐색은 하나의 요소를 O(lo..

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제 분석 N개의 단어가 주어지고, K개의 글자(알파벳)을 가르칠 수 있을 때 K개의 알파벳으로 배울 수 있는 글자 개수의 최대값을 구하는 문제. 이때 모든 글자는 "anta"로 시작되고, "tica"로 끝나기 때문에 가르칠 수 있는 K개의 글자엔 a, c, i, n, t가 포함되어 있다. a부터 z까지 알파벳을 순회하면서 가르칠 수 있는 단어를 구하는 완전탐색이라고 생각했지만, 의외로 문..