Algorithm 개념 및 문제풀이17 Leetcode 5번 문제 풀이 개요 Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다. 문제 : 5. Longest Palindromic Substring 주어진 문자열 내에서 팰린드롬인 문자열을 찾아 반환해야 함. 풀이1 : Brute force 설명 Brute force(무차별 대입) 방식으로 풀 경우, 문자열 내 모든 문자마다 접근해서 팰린드롬인지 확인하여야 한다. 이 경우 시간 복잡도는 O(N^3) 이 나온다 ** 시간 복잡도가 O(N^3) 인 것은 루프로 각 문자마다 접근을 하고, 팰린드롬인지 검사를 위해 이중 루프를 돌기 때문이다. (이중 루프를 어떤 방식으로 도는지에 대해선 정확히 모르고, 좀 더 자료조사가 필요) 그러므로 무차별 대입보다 좀 더 나은 방법이 필요하다. 다른 방법으로 DP.. 2020. 1. 12. Leetcode 3번 문제 풀이 개요 Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다. 문제 : 3. Longest Substring Without Repeating Characters 문자열내에서 중복이 없는 가장 긴 문자열의 길이를 반환해야 함. 풀이1 : Brute force 설명 Brute force(무차별 대입) 방식으로 풀 경우, 주어진 문자열 내 모든 문자들을 검사하여 풀 수 있다. 각각의 문자별로 루프를 돌아서 가장 긴 substring의 길이를 반환한다. 구체적으로는 다음과 같다. 전체 문자열 길이만큼 루프를 돌면서 조건에 따라 임시 문자열에 각 문자를 대입한다 조건 1 : 만약 임시 문자열이 비어 있으면 최초 문자를 대입한다 조건 2 : 만약 특정 문자와 임시 문자열을 중복 체크하여.. 2020. 1. 9. C++ 개념 살짝 정리(8958 문제) 문제 URL : https://www.acmicpc.net/problem/8958 1. string 을 char 와 비교하려면 single quote(') 을 사용해야 함. double quote(") 을 사용하면 에러가 발생함.s[i] == 'O' (OK)s[i] == "O" (NO) 2. 연산자 중 전위, 후위 연산자의 우선순위는 += 보다 높다. 3. for 문을 반복할 때 종결조건이 참이면 계속 반복한다.이에 따라 문자열이 str = "OOOOO"; 와 같이 있는데 종결조건을 str[i]과 두어도 마지막 문자('\0') 를 만나기전 까지 5번 반복한다.=> for(int i=0; str[i]; i++) 와 같이 있을 때 각 요소가 참이므로 마지막 문자('\0')를 만나기 전까지 문자열의 길이(5).. 2019. 3. 7. 17번 string 과 map 을 사용해서 품 p.s 40은 영어로 fourty 가 아니라 forty 다 (영어 20년 넘게 쓰면서 처음 앎) 2018. 9. 3. 오일러 16번 2^1000 값의 자리수들을 모두 더한 값을 구하는 문제이다. 2^1000 을 display 할 수 없으므로 c 언어로는 풀기가 까다로운 면이 있다. 머리를 많이 굴려봤지만 별수가 떠오르지 않았다..한가지 떠오른 건 13번 문제처럼 숫자를 문자로 치환하면 큰 값들을 처리할 수 있고 풀 수 있지 않을까라고 생각했다. 정답을 찾아 제출하고 다른 사람들이 푼 방법들을 봤는데 문자열을 이용해 풀고 동적할당하는 방식이 가장 이상적으로 보여 아래와 같이 풀었다. 1. 이중 for문을 사용하는데 바깥 for문은 2를 1000번 곱하는 큰 과정이고 내부 for문은 각 자리수들을 처리하기 위한 for문이다, 내부 for문의 횟수는 문자열 배열의 크기만큼 반복을 하게 된다. 2. digit, temp[j], carry 라.. 2018. 8. 14. 오일러 15번 단순한 dynamic pr 문제라고 생각했는데, 수학적인 지식을 요구하는 문제였다(euler 문제들이 전부 그렇지만!) 또 조합으로도 풀 수 있는 문제이다. dynamic 문제 유형과 유사하여 기억을 되살려 풀려고 했지만 실빼.. 검색을 해보면서 다른 분들은 어떻게 풀었는지 참고를 하였다. 그 중 dynamic 으로 푼 블로거 분이 계셔서 이를 참조하였는데 정답이 long long int로 꽤 큰 값이 나왔음에도 빠른 시간안에 수행이 되었다. 이 후 코드리뷰를 진행하는데, for (int i = 0; i < N+1; i++) { arr[N][i] = 1; arr[i][N] = 1; } 위 부분이 이해가 되지 않았다..검색을 좀 더 해보니 아래 블로그가 top으로 떠 참고를 해보았다 아래 블로그가 원본 코.. 2018. 8. 8. Problem 12 이전에 올렸던 글에서 그 다음으로 어려웠던..약수의 갯수가 500이 넘는 최소 값을 찾는 문제 삼각수를 구하는 방식에 약수를 구하는 반복문을 같이 쓰니 시간이 엄청 오래 걸려 값을 구하지 못했다. 좀 더 빠른 시간내에 구할 수 있는 방법은 소인수 분해를 사용하는 것이다, 그리고 삼각수를 구하는 공식을 매크로 함수를 이용해 하는 것도 좋다 이렇게 하면 컴퓨터가 연산하는 시간을 줄이는 데 도움을 준다. 소인수 분해를 통해 약수를 구하는 공식은 다음과 같다. 이를 코드로 옮기는 과정을 적어보았다. 1. 먼저 삼각수를 소인수 분해해주는 함수로 넘겨준다. 2. i=2부터 삼각수의 크기만큼 반복해 약수가 있는지 판별한다. 3. 약수라면 그 때의 i로 n을 나눠주고 지수 값을 증가시켜준다. 4. 증가시킨 지수 값에 .. 2018. 8. 1. Problem 10 문제출처 : http://euler.synap.co.kr/prob_detail.php?id=10 첨으로 오일러 문제들 중 정리하게 된 문제 이백만 이하의 소수들을 모두 더해 출력하는 문제이다 브루트 포스로 풀게 될 경우 약 14분 이라는 시간을 잡아먹게 되므로 시간적으로 비효율적인 방법이다. 이를 수학적으로 접근하게 되면 빨리 풀 수 있게 되는데 에라토스테네스의 체라는 방법을 이용할 수 있다. 기본적으로 그 방법에 대해 알고는 있지만 제대로 사용해본 적이 없어서 다른 블로그의 글을 통해서 제대로 이해할 수 있었다. https://m.blog.naver.com/PostView.nhn?blogId=leejuesong&logNo=220398206365&proxyReferer=https%3A%2F%2Fwww.g.. 2018. 7. 25. 이전 1 2 다음
