복습노트 복습노트

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 사재기를 해서 최대로 얻는 이익을 구하는 문제 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다. 첫 날에 1을 1개 구매 = -1 두번째 날에 2를 1개 구매 = -2 따라서 총 -3을 지불하고 세번째 날에 값이 3으로 올랐으므로 가지고 있는 2개를 팔면 (2 * 3 = 6) 이다. 따라서 6 - 3 = 3의 이득을 봤다. 구매는 최대 1개만 할 수 있다(안살 수도 있음) 판매는 언제든지 판매가 가능하다. 처음에는 주어진 매매가를 처음부터 차례대로 보면서 계산을 하려했지만 다음과 같이 주어..

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com S에서 시작해서 G까지 가는데 상하좌우 이동할 수 있다. 최소비용을 구하는 문제이다. 처음에는 bfs로 최소비용을 구하였지만, 지나온 경로를 체크하는 부분에서 의미가 없다고 생각해 풀지 못하였다. 이 문제는 최소 경로가 아니라 길을 돌아가더라도 최소비용을 구해야하는 것이다. 다음으로는 DP로 접근하였다. S에서 행 끝까지, 열 끝까지 누적합을 기준으로 dp를 진행하였다. 하지만 답이 틀려 다른 외부 사이트에서 영감을 얻었다. 단서는 bfs형태로 이동하면서 dp 형태로 푸는 것이다. bfs형태로 하면 지나온 경로를 체크해야하는데 이를 하지 않고 계속해서 최소비..

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 다음과 같이 입력이 주어질 경우 {123 1} 123을 1번 자리를 교환해 가장 큰 수를 만들어야 한다. 예시에서는 1과 3을 바꿔 321이 정답이다. {94 2} 일 경우 94 -> 49 -> 94 이다. 처음에는 단순히 백트래킹 기법으로 모든 자리를 교환해 그 중 가장 큰 수를 출력할려 했다. sol(st, change); //입력 받은 String 숫자배열, change는 교환할 수 있는 수 void sol(string s, int cnt) { if (cnt == 0) //cnt가 0이면 다 교환했다는 의미 이므로 최댓값을 갱신 { int temp = ..

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구명보트에는 최대 2명이 탈 수 있고, 몸무게가 limit을 넘으면 안됩니다. 구명보트를 최소로 하는 갯수를 구하라. 처음에는 단순히 people를 정렬해서 구하는 줄 알았지만, 시간초과가 나오게 되고 검색을 통해 투 포인터를 사용하는 것을 알게 되었다. 오름차순으로 정렬했기 때문에 가장 왼쪽에는 작은 몸무게, 가장 오른쪽은 큰 몸무게 이다. l, r을 사용했다. people[l] + people[r] limit 이면 가장 큰 몸무게는 혼자 구명보트를 타야하기 때문에 r--만 해주고 구명보트를 늘려준다...

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 위의 그림같이 건물 좌우 2칸씩 아무것도 없으면 view가 보인다. 위의 그림에서는 초록색으로 칠해진 곳이 view가 보이는 곳이다. 따라서 총 6개가 view가 보인다. A는 오른쪽으로 1칸때문에 안보이고 B도 마찬가지이다. C는 왼쪽으로 1칸때문에 안보인다. 맨 오른쪽, 왼쪽 2칸 씩은 건물의 높이가 0이다. 처음에는 스택과 큐로 접근 하였는데 계속 안풀려서 1시간 소비한 문제이다. 답지를 보면 정말 간단한것 을 알 수 있다. 일단 모든 건물의 높이를 다 배열에 담고 현재 인덱스로 부터 left(-2, -1), right(+1, +2) 인 곳을 찾아 둘 ..

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위와 같이 전화번호를 String형으로 주어지는데 각 전화번호를 비교해 접두어가 같은 String이 있으면 false를 return하고 그렇지 않으면 true를 return하는 것이다. 접두어는 맨앞의 글자만 같아도 접두어가 같은것이다. import java.util.*; class Solution { public boolean solution(String[] phone_book) { Mapm = new HashMap(); for(int i=0;i

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr BFS를 구현하는 기본 문제이다. 시작점은 (1, 1)이고, 끝점은 (행의 크기, 열의 크기)이다. import java.util.*; import java.io.*; class Solution { int []dx = {0, 1, -1, 0}; int []dy = {1, 0, 0, -1}; int answer = 0; public int solution(int[][] maps) { boolean [][]visited = new boolean[maps.length][maps[0].length]; Queue..

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 삼각형 꼭데기에서 시작해 바닥까지 가면서 숫자를 더해 최댓값을 구하는 문제이다. 내려갈때는 항상 대각선 아래로만 내려갈 수 있다. import java.util.*; class Solution { int [][]dp = new int[501][501]; public int solution(int[][] triangle) { for(int a[] : dp) //이차원 배열 모두 -1로 초기화 Arrays.fill(a, -1); dp[0][0]=triangle[0][0]; for(int i=1;i