100세까지 코딩

문제 설명 ※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀기 전 생각 배열에 값을 다 넣은 후 최댓값(max)과 그에 해당하는 인덱스(maxIndex) 찾기 그 사이 원소의 갯수는 cnt = maxIndex - start 시작점(start)부터 최대값-1까지 값들을 sum에서 빼주기 그 후 최댓값일 때 판매로 벌어들인 수익 더해주기 (sum += cnt * max) 그다음..

동적 계획법이란? 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결하여 최종적인 복잡한 문제의 답을 구하는 것 동적 계획법을 푸는 팁 작은 문제로 나눌 수 있어야 하며, 점화식을 세운다. DP[](다이나믹 프로그래밍) 테이블에 값을 저장한다. 테이블 값을 재사용하여 시간을 단축한다. (메모이제이션 기법) 바텀 - 업 (반복문) OR 탑 - 다운(재귀 함수의 형태) 방식으로 푼다. 문제 설명 풀기 전 생각 점화식을 세울 때 D[N-2], D[N-1]을 먼저 생각 (초기부터 생각하는 바텀-업 방식) D[1] 일 때는 세로 1개 (|) 밖에 불가능하므로 D[1] = 1 D[2]일 때는 세로 2개 (||), 또는 가로 2개(=) 이므로 D[2] = 2 D[3]일 때는 세로 3개(|||) 또는..

조합 자체로도 자주 출제되며 동적 계획법을 이해하는데 중요 점화식을 도출하는 것이 매우 중요 기본 지식으로 i C k 이면, k는 (0 ~ i)까지 가능하며 k=0 또는 k=i 이면 1이다. 점화식 도출 특정 문제를 가정 모든 부분 문제가 해결되었다고 가정하고 지금 문제 생각 예시 5개 중에 3개를 고르는 5C3 (1,2,3,4),5가 있으면 괄호안은 이미 선택이 완료된 데이터 5를 선택한다면 이미 선택된 데이터 4개중 2개만 골라야 한다. 4C2 5를 선택하지 않는다면 이미 선택된 데이터 4개중 3개를 골라야 한다. 4C3 즉, 5C3 = 4C2 + 4C3 D[i][j] = D [i-1][j-1] + D [i-1][j] 문제 설명 풀기 전 생각 위에서 얻은 점화식을 활용하여 재귀함수 사용 재귀함수를 멈..

그래프란? 객체 사이의 연결 관계를 표현할 수 있는 자료구조 정점(vertex)과 간선(edge)들의 집합 종류는 무방향 그래프, 방향 그래프 문제 설명 강의 코드 import java.io.BufferedReader; import java.util.ArrayList; import java.io.InputStreamReader; public class Baek1707 { static ArrayList[] A; static int[] check; // 같은 집합인지 다른집합인지 구분 static boolean[] visited; // 방문 여부 static boolean IsEven; // 이분 그래프 인지 아닌지 T / F public static void main(String[] args) throws..

브루트포스 알고리즘이란? 완전 탐색 또는 무차별 대입 알고리즘 쉽게 말해 모든 가능한 숫자들을 대입해 보는 방식 선형 구조 : 순차 탐색, 비선형 구조 : 백트래킹, DFS, BFS 문제 설명 풀기 전 생각 무작정 대입 알고리즘이니 세 자릿수 100부터 999까지 List에 넣기 100부터 999까지 반복을 돌면서 정답과 같은 위치면 strikeCnt++ 그렇지 않고 포함만 돼있으면 ballCnt++ stikeCnt와 ballCnt가 힌트와 같지 않고 가능성 없는 수면 지우기 코드 import java.util.*; import java.io.*; public class Baek2503 { public static void main(String[] args) throws IOException { List..

에라토스테네스의 체란? 소수를 구할 때 자주 쓰이는 알고리즘 구하고자 하는 범위만큼 1차원 배열 생성 2부터 시작하여 현재 선택된 숫자의 배수에 해당하는 수를 배열 탐색하며 지우기 지워지지 않은 처음 선택된 숫자 = 소수 배열의 끝까지 위에 과정 반복 문제 설명 풀기 전 생각 배열 크기를 N+1로 잡고 0부터 index대로 대입 이중 반복문을 사용하여 바깥 반복문은 가장 작은 소수인 i=2부터 시작 안쪽 반복문은 j = i +1부터 시작하여 j가 i로 나눠떨어지면 arr [j] = 0으로 지우기 M~N까지 지워지지 않고 남아있는 소수들 출력 코드 import java.util.*; public class Baek1929 { public static void main(String[] args) { Scan..