전체 글

개발 등 공부기록용 블로그입니다
https://school.programmers.co.kr/learn/courses/30/lessons/258712 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr #해설 본문을 그대로 따라서 구현하면 되는 문제 1. 여기서 선물주는 기록이 문자열로 주어지기 때문에 sstream을 통해 문자열 분리 입력받고 2. 2차원 배열을 각 이름에 맞게 만들어 주기 위해서 각 이름과 인덱스를 map을 이용해 맵핑해주기 3.주고받은 선물 수 비교 후 같으면 선물지수로 비교후 최대값 갱신 4. 끝 #코드 #include #include #include #include #..
· [백준]/C++
https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net #문제 해결 방법 간단하게 생각해보자 일단 시간복잡도를 계산하고 브루트 포스는 안된다는 결론을 내릴 수 있다. 그렇다면 dp를 사용해야 하는데 dp는 큰 문제를 작은문제로 쪼갤 수 있으며 작은 문제를 통해 큰 문제를 풀 수 있어야 한다 즉 dp[i][j] 는 i번째 동전을 사용해서 j 의 값을 만드는 횟수인데 이 횟수는 i번째 동전을 사용하지 않은 문제로부터 답을 구할 수 있다. ..
· [백준]/C++
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net #문제 해결 방법 투 포인터를 사용해서 두 값을 선택해서 더한값이 0보다 작다면 start++ 0보다 크다면 end-- 를 해서 0과 가장 같은값을 구할 수 있겠지만.. (n) 나는 일단 이분탐색을 생각했고 두 값을 더한값이 0보다 작다면 low = mid +1 해서 더 큰값을 찾고 0보다 크다면 high = mid -1 해서 더 작은 값을 찾는 방식을 사용했다 ..
· [백준]/C++
https://www.acmicpc.net/problem/13422 13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마 www.acmicpc.net #문제 간단 정리 슬라이딩 윈도우를 이용해서 푼다 #문제 해결 방법 우선 슬라이딩 윈도우는 인자가 두개인 for문을 사용하면 쉽게 구현할 수 있다. 여기서 주의해야될 점은 집이 원형으로 연결되어있기 때문에 모듈러 연산으로 원형으로 탐색하게 끔하고 N == M 인 경우에는 슬라이딩 윈도우 크기가 N 과 같기 때문에 존재하는 구간이 하나임에도 불구하고 같은 구간을 여러번 탐색하게 되므로 N == M 인경우는..
· [백준]/C++
https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net #문제 간단 정리 #문제 해결 방법 성원이의 현재 몸무게를 x, 기억하고 있는 몸무게를 y라고 할 때, 주어진 조건은 x^2 - y^2 = G입니다. 이 식은 (x + y)(x - y) = G로 변환할 수 있으며, 우리는 x와 y의 모든 가능한 쌍을 찾아야 합니다. 그러나 주어진 조건에 따라 x와 y는 모두 자연수여야 하며, x > y 조건을 만족해야 합니다 여기서 자연수임을 확인하는 방법은 구한 y^2 값을 ..
· [백준]/C++
https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net #문제 해결 방법 이 문제를 해결하기 위한 로직은 '슬라이딩 윈도우' 기법을 사용합니다. 이 기법은 일정 범위의 데이터를 순차적으로 이동시키면서 연산을 수행하는 방법입니다. 구체적으로, 문제의 해결 로직은 다음과 같습니다: 초기화: maxVisitor: 최대 방문자 수를 저장하는 변수입니다. 이를 0으로 초기화합니다. nowVisitor: 현재 윈도우(즉, 연속된 X일)의 방문자 총합을 저..
· [백준]/C++
#문제 간단 정리 dp 를 사용해서 풀어야한다 #문제 해결 방법 문제 상황 먼저, 문제 상황을 이해해야 합니다. 여기서는 가로로 2칸, 세로로 N칸인 우리가 있고, 사자들을 배치하는 문제입니다. 조건은 다음과 같습니다: 사자들은 가로나 세로로 붙어 있을 수 없습니다. 사자를 한 마리도 배치하지 않는 경우도 포함합니다. 동적 프로그래밍 이해하기 DP는 큰 문제를 작은 문제로 나누어 푸는 방법입니다. 이 문제에서는 'N번째 칸까지 사자를 어떻게 배치할 수 있는가'를 작은 문제로 삼습니다. 각 칸에 대해 다음과 같은 세 가지 경우를 생각해볼 수 있습니다: 사자를 배치하지 않는 경우. 사자를 첫 번째 칸에만 배치하는 경우. 사자를 두 번째 칸에만 배치하는 경우. DP 배열 설정 DP를 사용하기 위해 각 상태를 ..
· [백준]/C++
https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net #문제 해결 방법 슬라이딩 윈도우를 사용하자 #전체 코드 #include #include using namespace std; int main() { int N, d, k, c; cin >> N >> d >> k >> c; vector sushi(N); vector sushiCount(d + 1, 0); for (int i = 0; i < N; i++)..
· [백준]/C++
https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net #문제 해결 방법 투 포인터를 사용하자 #전체 코드 #include #include using namespace std; int main() { int n; cin >> n; string s; cin >> s; int st = 0, en = 0; int maxLength = 0; int curType = 0; int alpha[26] = { 0, }; while (en < s.length()) { if (..
· [백준]/C++
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net #문제 간단 정리 위상정렬을 사용해 문제를 풀자. #전체 코드 #include #include #include #include using namespace std; int main() { int T; cin >> T; while (T--) { int N, K; cin >> N >> K; vector build_time(N + 1, 0); vector indegree(N + 1, 0); vec..