본문 바로가기

Algorithm283

[BOJ]17822번: 원판 돌리기 문제: https://www.acmicpc.net/problem/17822 시뮬레이션 문제입니다. 원판의 숫자와 인접한 컴포넌트를 확인할 때 1번인덱스와 M번 인덱스의 숫자도 4방향 탐색을 할 수 있도록 인덱스를 조정하는 게 중요합니다. 또한, 평균값은 실수로 구해줘서 대소비교를 해주도록 하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ17822.cc 2020. 5. 15.
[코딩테스트 연습] 지형 편집 문제: https://programmers.co.kr/learn/courses/30/lessons/12984 문제 풀이법은 아래의 상도님 블로그 포스팅을 보면 잘 나와있습니다. https://sangdo913.tistory.com/140 X값이 증가하는 방향을 기준으로 2차 함수는 1. 미분한 함수의 기울기가 계속 증가한다는 점 2. 기울기가 0인 점에서 최소가 나온다는 점 이 두 가지 성질을 활용해서 x, x+1 좌표에 대해 결과값으로 y, y+1을 구하고 이 둘의 값을 비교해가면서 이차 함수를 탐색하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter11.cc 2020. 5. 13.
[코딩테스트 연습] 스티커 모으기(2) 문제: https://programmers.co.kr/learn/courses/30/lessons/12971 DP 문제입니다. DP의 의미를 아래와 같이 정의합니다. DP[N] = N번째 칸까지 스티커를 모았을 때 최대 점수 그러면 다음과 같은 점화식이 성립합니다. DP[N] = max(DP[N-1], DP[N-2] + sticker[N]) 단, 원형판이라는 특수한 조건이 있으므로 값을 한 번 더 분기해줘야 합니다. 첫 번째 칸의 스티커를 뗀 경우와 떼지 않은 경우입니다. 첫 번째 칸의 스티커를 뗀 경우라면 마지막 칸의 스티커는 떼면 안됩니다. 첫 번째 칸의 스티커를 떼지 않은 경우라면 마지막 칸의 스티커를 포함시킬 수 있습니다. 이렇게 BOTTOM-UP 형식으로 구해주면 됩니다. 코드: https://.. 2020. 5. 13.
[코딩테스트 연습] 소수 만들기 문제: https://programmers.co.kr/learn/courses/30/lessons/12977 조합을 통해 50 combination 3을 구현해준 뒤, 뽑힌 수에 대해서 소수판별을 해주면 됩니다. 소수 판별을 해줄 때 해당 숫자의 제곱근까지만 탐색을 하면 소수 유무를 알 수 있습니다. 왜 그런지 이해가 안가신다면 '에라토스테네스의 체' 관련 포스팅을 찾아보시면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter09.cc 2020. 5. 12.

티스토리툴바