기록하는 습관

문제 백준 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..