Dolphins의 HelloWorld

빅 오 분석 : 입력 값의 개수에 따라 알고리즘이 수행되는 데 걸리는 시간을 바탕으로 알고리즘의 효율성을 판단하는 실행 시간 분석법 빅 오 분석법에서는 입력 값의 개수(크기)를 n개라고 가정한다. 빅 오 실행시간 분석은 다음과 같이 이루어진다. 1. 입력 값을 확인하고 n을 어떤 값으로 놓아야 할지 결정.2. 알고리즘에서 수행해야 할 연산 횟수를 n으로 이루어진 식으로 표현3. 차수가 제일 높은 항 남기기.4. 모든 상수 인수를 없앤다. 성능이 좋은 것부터 나쁜 것까지 순서대로 알고리즘 종류를 나열해보면 다음과 같다. O(lg n) > O(n) > O(n lg n) > O(n^c) > O(c^n) > O(n!)(lg는 밑이 2인 로그함수를 의미) 왼쪽이 성능이 가장 좋은것이고 오른쪽으로 갈 수록 나빠지는..

문제링크 : https://www.acmicpc.net/problem/1406 풀이 만약 시간제한이 없다면 간단하게 생각될 수 있는 문제이다. 각 명령어에 따라 조건문을 작성하고 string혹은 배열을 이용하여 명령어를 실행하면서 커서를 밀고 당기면서 문자열을 계속 새롭게 만들면 되기 때문이다. 나 같은 경우 string과 substr명령어를 사용해서 문자열을 계속 재배치했는데 역시 시간초과에 걸리고 말았다. 어떤 자료구조를 이용해서 이 문제를 효율적으로 풀어야할지 생각해내는 것이 이 문제의 핵심이다. 나는 stack자료구조를 썼는데 left스택과 right스택을 만들어 커서를 기준으로 왼쪽에 있으면 left 스택에, 오른쪽에 있으면 right스택에 문자들을 집어넣는다면 쉽게 풀 수 있다. 예를들어 ab..

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42883 풀이 level 2 인 것 치고 생각보다 풀기 어려웠던 문제였다. 일단 주어진 숫자에서 k개의 수를 빼 나간다고 가정했을 때 큰 숫자를 만들기 위해서는 앞쪽에 큰 숫자를 배치해야하며 만약 동일한 숫자가 연달아 나온다면 큰 수를 만들기 위해 뒤쪽에 있는 숫자를 빼야함을 알 수 있다. 이런 문제를 해결하기 위해 stack을 써서 이 문제를 해결하였으며 주어진 number를 스택에 쌓으면서 예를들어 첫 예제인 "1924"를 처리한다고 가정하였을 때 일단 첫 숫자인 1을 스택에 쌓고 다음 숫자인 9 같은경우 스택에 있는 1보다 크기 때문에 1을 제거한 후 9를 스택에 넣으며 다음 숫자인 2 같은 경..

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42860 풀이 이 문제를 복잡하지 않게 풀기 위해서는 조이스틱으로 이름을 만드는 경우의 수가 2가지라는 것을 먼저 파악하는 것이 중요하다. 이 2가지 경우의 수에는 맨 처음 문자를 수정한 뒤 맨 끝으로가서 이름을 만들기 시작하는 경우와 맨처음부터 그냥 순서대로 끝까지 이름을 만드는 경우가있다. 난 이 2가지를 모두 구현하고 두 방법중 조이스틱을 움직인 횟수가 적은걸 return하도록 하였다. 유의할 점으로는 예를들어 'ABCAA'라는 문자를 처음부터 순서대로 만든다고 했을 때 'C'를 만든뒤 뒤에 있는 문자들은 모두 'A'이기 때문에 이대로 더이상 조이스틱을 움직이지 않아도 된다는 것을 반영해야 한다..

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42862/solution_groups?language=cpp 풀이 먼저 여분의 옷을 가지고 있는 친구와 잃어버린 친구를 쉽게 구분하기 위해 다음과같이 map을 써서 저장해 놓았다. for(int i=0; i

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42841 풀이 완전탐색을 이용해 이 문제를 풀 수 있다는 것을 알아낸다면 그렇게 어려운 문제는 아니나 이를 깨닫지 못해 꽤 오랫동안 풀었던 문제이다. 가능한 답이 되는지 검사해볼 수는 모든 세자리 수 이므로 대충 900개라고 하고 질문은 최대 100개까지 할 수 있으므로 최대한 검사해도 90000번 검사를 수행하며 고로 완전탐색이 가능하다. 만약 문제가 잘 안풀린다면 반복문을 수행할 때 0이 나오는 경우를 배제하지 않았을 경우가 있으므로 이에 유의하도록 하자. #include #include #include using namespace std; int solution(vector baseball) {..

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/43162 풀이 DFS/BFS 중 어떤 방법을 써서 풀어도 상관없는 문제이다. 일단 computers 벡터에 들어있는 수들을 처리하기 쉽게 다시 벡터함수에 저장하였다. for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (computers[i][j] == 1) { v[i].push_back(j); v[j].push_back(i); } } } 이와같이 처리하였는데 이렇게 처리했을 때 노드별로 이어져 있는 노드들만 저장이 된다. 예를들어 1번노드가 2,3번 노드와 연결돼있다면 v[1][0] = 2 , v[2][0] = 1v[1][1] = 3 , ..

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/43104 풀이 처음으로 이런 문제를 만나면 당황할 수는 있겠지만 숫자들을 쭉 나열하고 규칙성을 찾아보면 생각보다 쉽게 풀릴 수 있다. 타일의 길이들을 처음부터 쭉 나열하면 1 1 2 3 5 8 13..... 이 되고 여기서 memo배열에 이 수를 저장한다고 했을 때 memo[i] = memo[i-3] + memo[i-2] + memo[i-1] 이런 식을 통해 길이가 도출됨을 알 수 있다. 둘레도 마찬가지 인데 가로 세로가 만들어지는 걸 관찰하다 보면 한 변 a = memo[N-2] + memo[N-1] 이 되고b = memo[N-1] + memo[N]이 되어 2 * (a + b) 를 하면 답을 도출할..

문제링크 : https://www.acmicpc.net/problem/2606 풀이 같은 집합에 대해서 하나로 묶어주고 찾고자 하는것이 해당 집합에 포함되어 있는지 찾을 수 있는 유니온파인드 자료구조를 사용하였다. 자세한 방식에 대해서는 http://dolphins-it.tistory.com/223 를 참조하자. #include using namespace std; int computer[101]; int find(int x) { if (x == computer[x]) return x; else { int y = find(computer[x]); computer[x] = y; return y; } } void merge(int x, int y) { int a = find(x); int b = find(y..

유니온파인드란? 유니온 파인드는 상호 배타적 집합이라고도 하며 누군가 어떤 집합에 속해있는지 알아내기위해, 또는 집합끼리 합치기 위해 사용하는 자료구조이다. 구현 트리를 통해서 이 자료구조를 구현하게 되는데 기본은 각 원소마다 배정된 배열에 자신의 index를 넣는것이다 즉 arr[i] = i로 초기화하는 것이다. 이것을 풀어서 설명하면 i의 부모노드는 i 라는것을 의미한다. 먼저 x가 어떤 집합에 포함되어 있는지 찾는 연산인 find함수에 대해 설명하겠다. 다음과 같이 구현이 되어 있다. 일단 if문을 보면 가장 상위 노드까지 올라가면 그 노드를 반환하는 식으로 되어있다. 그렇다면 else문에서 그냥 find함수를 호출하기만 하면 되는데 arr[x] = y라는 과정을 추가했을까 그 이유는 실제로 활용할..