기록하는 습관

문제 백준 2839 설탕배달 https://www.acmicpc.net/problem/2839 풀이 문제에서 요구하는 것은 설탕을 정확하게 최소한으로 가져갈 수 있는 봉지의 수이다. 그렇다면 3Kg봉지와 5Kg봉지 중 5Kg봉지를 가장 많이 쓰는 것이 최적해가 될 것이다. 이 문제는 접근 방법에 따라 쉬울수도 어려울수도 있는 문제인 것 같다. 예를들면, N킬로그램을 구하기 위해 더하는 방법으로 접근한다면 경우의 수가 굉장히 많아져서 최적해를 찾아내기 어려워진다. 접근방법으로 N킬로그램부터 3Kg씩 빼면서 5Kg의 배수를 찾아내면 굉장히 쉽게 풀린다. 코드 import java.util.Scanner; /* 설탕 배달 */ public class baekjoon_설탕배달 { public static voi..

문제 백준 16236 아기상어 https://www.acmicpc.net/problem/16236 풀이 지도에 상어가 1마리 존재하고, 상어는 자신보다 작은 물고기를 먹을수 있다. 자신보다 큰 물고기 칸에는 갈 수 없고, 상어는 자신의 길이와 같은 수의 물고기를 먹으면 길이가 1만큼 증가한다. 상어는 가장 가까운 물고기부터 먹는다. 상어가 먹을 수 있는 모든 물고기를 먹었을 때 최소 시간을 구하는 문제이다. 조건이 까다롭지만 bfs탐색을 통해 풀수있다. 지도에서 9라는 값을 찾아 초기 시작 좌표를 획득하고 bfs탐색을 진행한다. 탐색을 통해 먹을 수 있는 물고기를 찾아 해당 좌표에 있는 값을 0(물고기를 먹었다는 뜻)으로 바꾸고 그 좌표를 기준으로 다시 bfs탐색을 수행한다. 먹을 수 있는 물고기가 여러..

문제 백준 7576번 토마토 https://www.acmicpc.net/problem/7576 풀이 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다. map에 입력받은 배열에 1인 값을 찾아 bfs 탐색을 시작한다. 방문하지 않은 배열이고 값이 0(익지않은 토마토) 일때, 값을 1(익은 토마토)로 바꾸고 방문처리 해준 후 큐에 다음 좌표를 담고 탐색을 계속 진행한다. 코드 #include #include using namespace std; struct POS{ int y,x,date; }; int n,m,ans; bool visited[1000][1000]; i..

문제 프로그래머스 전화번호 목록 https://programmers.co.kr/learn/courses/30/lessons/42577 풀이 ph에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하여 답을 출력하는 문제이다. find 함수를 이용하여 간단하게 해결했다. find 함수는 매개변수가 존재하면 0을 존재하지 않으면 -1을 리턴한다. check에 반환되는 값이 0일때 cnt를 1증가시키고 cnt의 값이 1 이상일 경우 접두어가 존재한다고 판단하게 된다. 코드 #include #include #include using namespace std; bool solution(vector ph) { bool answer = true; int n = ph.size(); for(int ..

문제 프로그래머스 피보나치 수 https://programmers.co.kr/learn/courses/30/lessons/12945 풀이 메모이제이션을 이용하면 간단하게 풀 수 있다. F(n) = F(n-1) + F(n-2) 수식을 그대로 적용하여 반복문을 통해 피보나치 수열을 구하면 된다. 코드 #include #include using namespace std; int memo[100000]; int fibo(int n){ memo[0] = 0; memo[1]= 1; for(int i=2;i

문제 프로그래머스 H-Index https://programmers.co.kr/learn/courses/30/lessons/42747 풀이 H-INDEX는 H번 이상 인용된 논문이 H개 이상일 때, H의 최대 값을 구하는 문제이다. 내림차순 정렬을 통해 인덱스와 값을 비교한다. 인용수가 index보다 큰 경우 answer+1 그 수가 index와 작거나 같아지는 순간 answer를 리턴해주면 된다. 코드 #include #include #include using namespace std; bool compare(int a, int b){ return a > b; } int solution(vector citations) { int answer= 0; sort(citations.begin(),citatio..

문제 프로그래머스 연습문제- 같은 숫자는 싫어 https://programmers.co.kr/learn/courses/30/lessons/12906 풀이 arr 배열안에 연속적으로 나타나는 숫자를 하나만 남기고 제거하는 문제이다. ans라는 배열에 arr의 첫번째 값을 초기값으로 넣고, 이후 수를 비교한다. ans의 -1번째 수, 즉 ans 배열의 마지막 원소를 arr[i]번째 수와 비교하여 답을 찾을 수 있다. 코드 def solution(arr): ans = list() ans.append(arr[0]) for i in range(1, len(arr)): if ans[-1] != arr[i]: ans.append(arr[i]) else: continue return ans

문제 프로그래머스 연습문제- 나누어 떨어지는 숫자 배열 https://programmers.co.kr/learn/courses/30/lessons/12910 풀이 주어진 배열을 divisor로 나누어 나머지가 0인 값만 ans배열에 넣는다. 만약 ans배열이 비어있다면, -1을 넣고 리턴한다. 코드 def solution(arr, divisor): ans=list() for i in range(len(arr)): if arr[i]%divisor == 0: ans.append(arr[i]) if ans == []: ans=[-1] ans.sort() return ans

문제 프로그래머스 2018 서머코딩- 숫자 게임 https://programmers.co.kr/learn/courses/30/lessons/12987 풀이 A,B를 내림차순으로 정렬을 하고, 각 A의 원소당 최소 차이가 나는 B를 선택한다. 만약 A의 값이 더 크다면 그냥 넘어가지만 A를 이기는 B가 있다면 그 값을 제거하고 answer을 1 증가시킨다. 코드 def solution(a, b): ans =0 a=sorted(a,reverse=True) b=sorted(b,reverse=True) for i in a: Min = i for j in range(len(b)): if b[j] > Min: Min = b[j] else: break if Min == i: continue else: b.remove..