Dolphins의 HelloWorld

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42891 정답률 : 정확성 42.08% / 효율성 5.52% 풀이 결국 효율성 부분을 잡아야하는 문제이다. 만약 정확성만 고려한다면 매 초마다 처리해주어 시간은 오래걸리지만 정답은 맞는 코드를 짤 수 있을것이다. 아무튼 맨 처음에 한 것은 vector tmp(size) //size는 food_times의 크기 이것을 선언해 주어 food_times와 그 index를 넣어준 것이다 이후 이것을 food_times의 오름차순으로 정렬하였다. 만약 1 3 5 7 9 라고 정렬이 되었다 치면 처음에는 1*5 -> 5초를 한번에 처리할 수 있고, 다음엔 (3-1)*4 -> 8초를 한번에 처리할 수 있다. 이런..

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42889 정답률 : 55.57% 풀이 정렬을 활용하는 법을 확인하는 문제로 보인다. 스테이지의 번호가 담긴 배열 stages를 내림차순으로 정렬한 후 반복문을 통해 만약 N이 5라면 stages에서 5의 갯수를 세고 총 도전자의 수는 누적해나가면서 실패율을 계산한 후 vector에 집어넣고 N이 0이 되기 전까지 이 과정을 반복하였다. 이런 과정을 거치고 나면 vector함수에 실패율,stage가 함께 저장되어있는데 실패율은 내림차순, stage는 오름차순으로 배열할 수 있도록 cmp함수를 따로 정의하여 마지막 처리를 해준후 return 해주었다.

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42888 정답률 : 59% 풀이 이 문제를 풀기위해 내가 쓴 핵심개념은 map과 queue이다. 일단 채팅창에 남는 메세지를 순서대로 저장하기위해 queue를 사용했으며 큐에는 Enter혹은 Leave와 uid를 함께 삽입하였다. 또한 map을 통해 uid에 대한 닉네임을 최신화시켜줌으로써 큐에서 하나씩 꺼낼 때 가장 최신화된 닉네임으로 메세지를 출력하도록 하였다. #include #include #include #include #include using namespace std; vector solution(vector record) { vector answer; queue q; map m; for..

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42898 풀이 기존의 동적계획법을 통해 푸는 문제와 거의 유사한 형태이다. 다만 주의할 점은 여기서 물에 잠긴 지역을 표시하는 (m,n)이 배열로 표시할 때는 n과 m을 바꿔서 arr[n][m] 이런식으로 사용해야한다는 점이다. 여기서 함정에 빠지지만 않는다면 어렵지않게 풀 수 있을것이다.

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42840?language=cpp 풀이 배열에 1번,2번,3번 사람이 찍는 패턴을 저장한 후 정답과 일일히 대조하면 된다. 오히려 마지막에 return하는 방식에 대해 고민을 했는데 cmp함수를 따로 생성해서 일단 점수 내림차순으로, 만약 점수가 같다면 사람번호가 오름차순으로 정렬되도록 하였고 정렬된 첫번째 사람부터 점수가 같은 사람은 순서대로 answer벡터에 삽입하여 return하였다.

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42747?language=cpp 풀이 먼저 인용횟수를 저장한 vector함수에 대해 내림차순으로 정렬하였다. 입출력 예시를 정렬했다 치면 {6, 5, 3, 1, 0}이 되고 for (int i = 0; i < citations.size(); i++) { if(citations[i] < i+1) return i;} 여기서 i+1은 인용된 논문의 수인데 이렇게 인용 횟수가 인용된 논문의 수보다 작아지는 순간이 H-Index보다 1 커지는 순간이며 고로 그 전의 index를 return하면 답을 도출해낼 수 있다. 마지막까지 조건문에 안걸리는 경우도 있는데 이 경우 답이 나올 경우의 수는 H-index가 ..

문제링크 : https://www.acmicpc.net/problem/1525 풀이 이 문제의 핵심은 2차원 배열을 마치 1차원 배열처럼 생각하고 문제를 풀어야한다는 점이다. 이렇게 한 이유는 이차원 배열을 통해 bfs로 문제를 풀었을 때 이미 했던 경우의 수를 check하기가 까다롭기 때문이다. 만약 이차원 배열이 아니라 문제에 있는 이런 퍼즐을 193425786 (0은 9로 바꿔서 넣음) 으로 생각하고 문제를 풀 때 map을 이용하면 방문했는지 여부와 횟수가 어떻게 되는지를 동시에 알 수 있다. 아래의 코드와 주석을 보면 어떻게 풀었는지 이해할 수 있을것이다. #include #include #include #include using namespace std; int move_x[] = { 1,-1,..

문제링크 : https://www.acmicpc.net/problem/9019 풀이 전형적으로 BFS를 사용하는 문제이다. 처음에 이 문제를 풀 때 'L'연산과 'R'연산을 하는 과정에서 비효율적으로 코드를 짜서 문제해결에 성공하지 못했는데 'L'연산의 경우 int tmp = (x % 1000) * 10 + x / 1000; 'R'연산의 경우 int tmp = (x / 10) + (x % 10) * 1000; 이렇게 식 하나로 정리했더니 문제를 해결할 수 있었다. #include #include #include #include #include using namespace std; bool visit[10000]; char cmd[] = { 'D','S','L','R' }; int main() { int ..

문제링크 : https://www.acmicpc.net/problem/1963 풀이 어떻게 풀어야하나 고민을 많이 했는데 결론적으로는 큐를 이용해 일일히 다 검사하면서 문제를 풀었다. 먼저 해결해야 하는것은 4자리 수중에 소수들을 가려내는 작업이다. 이 작업은 에라토스테네스의 체를 이용하여 소수들을 선별해놓으면 편하다. 에라토스테네스의 체에 대해 자세히 모른다면 http://dolphins-it.tistory.com/105?category=771381 을 참조하자 아무튼 이러한 방식으로 소수를 판별했다면 자릿수 별로 숫자를 바꿔주면서 해당 자릿수의 숫자를 바꿨을 때 소수이면서 방문하지 않은 숫자라면 큐에 삽입해서 원하는 수가 나올 때까지 계속 반복해주도록 한다. #include #include #incl..

문제링크 : https://www.acmicpc.net/problem/1697 풀이 문제 분류가 DFS, BFS로 되어있고 실제로 정답을 맞춘 사람들의 풀이를 보면 큐를 이용해서 푼 사람들이 대부분이지만 난 그냥 Dynamic Programming 으로 풀었다. Dynamic Programming으로 푼다고하면 아마 초기값 설정에서 애매하게 느낄 수 있겠지만 난 그냥 수빈이 위치 이전값들은 걸어서 이동하는 것 밖에 방법이 없으므로 수빈이 위치를 0으로 놓은 상태에서 1씩 증가시키면서 일일히 다 넣어주었다. 그런다음 수빈이 위치 + 1 부터 동생의 위치 + 1까지 for문을 통해 반복문을 진행하면서 만약 인덱스 i가 짝수라면 다음과 같이 arr[i] = min(arr[i / 2] + 1, arr[i - 1..