Algorithm

    BFS, DFS 탐색 팁
    Algorithm

    BFS, DFS 탐색 팁

    저는 항상 BFS 문제를 풀 때 구현을 다한 뒤 테스트 케이스를 다 통과하고 맞왜틀을 정말 많이 겪었습니다. 한 번 갇힌 사고에서는 탈출하기 정말 어려운 게 알고리즘 문제이고 이러한 경우를 어떻게 하면 줄일 수 있을까 정말 많이 고민했습니다. 그래서 저의 안좋은 습관을 찾고자 노력하였고 치명적이 안 좋은 습관을 한 가지 찾았습니다. 안 좋은 습관은 BFS 탐색의 조건절에서 저는 "찾고자 하는 경우"를 조건으로 넣어주는 습관을 가지고 있었습니다. "이게 뭔소리냐 찾고자 하는 경우를 조건으로 넣는 게 왜 안 좋은 습관이냐?"라고 하실 수 있습니다. 하지만 찾고자 하는 경우를 찾는 것보다는 안 되는 경우를 찾는 게 더 쉽고 정확합니다. 밑에 문제로 예시를 들어보겠습니다. 백준 https://www.acmicp..

    [#3-13]동적계획법-문제: 두니발 박사의 탈옥(문제 ID: NUMB3RS)
    Algorithm

    [#3-13]동적계획법-문제: 두니발 박사의 탈옥(문제 ID: NUMB3RS)

    문제출처 algospot.com :: POLY 폴리오미노 문제 정보 문제 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로 algospot.com 문제 코드 NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코드입니다. - NamHyeop/AlgorithmProblem github.com

    [#3-12]동적계획법-문제: 폴리오미노(문제 ID: POLY)
    Algorithm

    [#3-12]동적계획법-문제: 폴리오미노(문제 ID: POLY)

    문제출처 algospot.com :: POLY 폴리오미노 문제 정보 문제 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로 algospot.com 문제 코드 NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코드입니다. - NamHyeop/AlgorithmProblem github.com

    [#3-11]동적계획법-문제: 비대칭 타일링(문제 ID: ASYMTILING)
    Algorithm

    [#3-11]동적계획법-문제: 비대칭 타일링(문제 ID: ASYMTILING)

    벽돌의 사이즈, 가로로 보기.... 문제출처 https://algospot.com/judge/problem/read/ASYMTILING algospot.com :: ASYMTILING 비대칭 타일링 문제 정보 문제 그림과 같이 2 * n 크기의 직사각형을 2 * 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은 algospot.com 문제 코드 NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코드입니다. - NamHyeop/AlgorithmProblem github.com

    [#3-10]동적계획법-예제: 장마가 찾아왔다(문제 ID: SNAIL)
    Algorithm

    [#3-10]동적계획법-예제: 장마가 찾아왔다(문제 ID: SNAIL)

    문제출처 algospot.com :: SNAIL 달팽이 문제 정보 문제 깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 � algospot.com 문제 코드 NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코드입니다. - NamHyeop/AlgorithmProblem github.com

    [#3-9]동적계획법-예제: 삼각형 위의 최대 경로 개수 세기(문제 ID: TRIPATHCNT)
    Algorithm

    [#3-9]동적계획법-예제: 삼각형 위의 최대 경로 개수 세기(문제 ID: TRIPATHCNT)

    문제출처 algospot.com :: TRIPATHCNT 삼각형 위의 최대 경로 수 세기 문제 정보 문제 9 5 7 1 3 2 3 5 5 6 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 � algospot.com 문제 코드 NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코드입니다. - NamHyeop/AlgorithmProblem github.com

    [#3-8]동적계획법-예제: 타일링 방법의 수 세기(문제 ID: TILING2)
    Algorithm

    [#3-8]동적계획법-예제: 타일링 방법의 수 세기(문제 ID: TILING2)

    문제출처 algospot.com :: TILING2 타일링 문제 정보 문제 2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있 algospot.com 문제 코드 NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코드입니다. - NamHyeop/AlgorithmProblem github.com

    [#3-7]동적계획법-문제: Quantization(문제 ID: QUANTIZE)
    Algorithm

    [#3-7]동적계획법-문제: Quantization(문제 ID: QUANTIZE)

    진짜 말도 안 되는 문제였다. 장담하는데 이거 일주일 동안 풀라고 시간을 줘도 못 풀었을 거 같다. 문제에 대해서 어떻게 하면 최적의 방식을 찾을지 규칙은 찾았으나 이것을 수식을 세워서 점화법을 세우는 단계까지는 못갔다. 꼭 다시 풀어봐야 하는 문제. 전체적인 이해는 했으나 코드가 흘러가는 재귀적 구조가 완벽히 들어오지 않는다. 하루 동안 고민하다가 스스로 화가 나서 포기하고 다음날 책을 다시 보니까 이해가 갔다. 역시 멘탈이.... 안 풀리거나 막히면 그냥 바람을 씌거나 산책을 하든가 잠시 쉬는 게 좋은 방법이라는 걸 깨달았다. 그냥 붙잡고 쳐다본다고 이해가 가지는 않는다. 문제출처 algospot.com :: QUANTIZE Quantization 문제 정보 문제 Quantization (양자화) 과..

    [#3-6]동적계획법-문제: 원주율 외우기(문제 ID: PI)
    Algorithm

    [#3-6]동적계획법-문제: 원주율 외우기(문제 ID: PI)

    문제출처 algospot.com :: PI 원주율 외우기 문제 정보 문제 (주의: 이 문제는 TopCoder 의 번역 문제입니다.) 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용�� algospot.com 문제 코드 NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코드입니다. - NamHyeop/AlgorithmProblem github.com

    [#3-5]동적계획법-문제: 합친 LIS(문제 ID: JLIS)
    Algorithm

    [#3-5]동적계획법-문제: 합친 LIS(문제 ID: JLIS)

    문제출처 algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 algospot.com 코드 NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코드입니다. - NamHyeop/AlgorithmProblem github.com

    [#3-4]동적계획법-예제: 최대 증가 부분 수열(문제 ID: LIS)
    Algorithm

    [#3-4]동적계획법-예제: 최대 증가 부분 수열(문제 ID: LIS)

    문체출처 algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. algospot.com 코드 NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코드입니다. - NamHyeop/AlgorithmProblem github.com

    [#3-3]동적계획법-예제: 삼각형 위의 최대 경로(문제 ID: TRIANGLEPATH)
    Algorithm

    [#3-3]동적계획법-예제: 삼각형 위의 최대 경로(문제 ID: TRIANGLEPATH)

    문체출처 algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 �� algospot.com 코드 NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코드입니다. - NamHyeop/AlgorithmProblem github.com

    [#3-2]동적계획법-문제:와일드카드(문제 ID: WILDCARD)
    Algorithm

    [#3-2]동적계획법-문제:와일드카드(문제 ID: WILDCARD)

    문제출처 algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 algospot.com 코드 구현1-완전탐색기법 NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코드입니다. - NamHyeop/AlgorithmProblem github.com 구현2-동적계획기법 NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코드입니다. - NamHyeop/AlgorithmProble..

    [#3-1]동적계획법-예제:외발 뛰기(문제 ID: JUMPGAME)
    Algorithm

    [#3-1]동적계획법-예제:외발 뛰기(문제 ID: JUMPGAME)

    문제: https://algospot.com/judge/problem/read/JUMPGAME# algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상�� algospot.com 코드 https://github.com/NamHyeop/AlgorithmProblem/blob/master/Algospot/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95/JUMPGAME NamHyeop/AlgorithmProblem 백준알고리즘,프로그래머스,알고스팟 등의 문제풀이 사이트에관한 문제들의 문제풀이 코..

    [#2-5]분할정복-문제: 팬미팅(문제 ID: FANMEETING)
    Algorithm

    [#2-5]분할정복-문제: 팬미팅(문제 ID: FANMEETING)

    코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126..

    [#2-4]분할정복-문제: 울타리 잘라내기(문제 ID: FENCE)
    Algorithm

    [#2-4]분할정복-문제: 울타리 잘라내기(문제 ID: FENCE)

    문제코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#includeiostream>#includevector>#includealgorithm>using namespace std;int solve(vectorint> &h, int left, int right){    //기저사례: 판자를 다 분해한 경우    if (left == right)        return h[left];    //[left,mid],[mid +1, right]의 두 구간으로 문제를 분할한다.    int mid = (left + right) / 2;    //분할한 문제를 다시 ..

    [#2-3]분할정복-문제: 쿼드 트리 뒤집기(문제 ID: QUADTREE)
    Algorithm

    [#2-3]분할정복-문제: 쿼드 트리 뒤집기(문제 ID: QUADTREE)

    문제 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include #include using namespace std; string reverse(string::iterator &it) { char head = *it; ++it; if (head == 'b' || head == 'w') //전체가 블랙이라면 b, 전체가 화이트라면 w, 그렇기에 최소로 쪼개지는 단위이며 아닐시 다음 노드에 x로 출력하고 다시 분해 return string(1, head); string upperLeft = reverse(it); // 위에서 왼쪽 자리 -> 밑에서 ..

    [#2-2]분할정복-예제: 카라츠바의 빠른 곱셈 알고리즘
    Algorithm

    [#2-2]분할정복-예제: 카라츠바의 빠른 곱셈 알고리즘

    러시아의 Karatsuba가 만들어서 Karatsuba(이름이 너무 어려워;;) 알고리즘이라고 한다. Karatsuba의 빠른 곱셈 알고리즘이 대단한 이유는 간단히 설명하면 보통 곱하기를 코딩으로 작성할 때 이중 포문으로 곱해서 자릿수 올림을 사용하여 계산한다고 생각한다. Karatsuba는 이것보다 더 빠른 알고리즘(4번 곱할걸 3번으로!)을 작성하였다. Karatsuba의 빠른 곱셈 알고리즘은 일단 곱할려는 두 수 a, b를 둘 다 반으로 쪼갠다. 여기서 Karatsuba는 이걸 곱해서 4개의 조각으로 만들 생각을 하였다. 그렇게 나온 식이 밑에 사진이다. 그런데 이 상태에서 분할정복을 실행할 경우 시간 복잡도가 O(n^2)이 나오기 때문에 분할 정복을 사용하는 의미가 없어 Karatsuba는 고민을..

    [#2-1]분할 정복-예제: 수열의 빠른 합과 행렬의 빠른 제곱
    Algorithm

    [#2-1]분할 정복-예제: 수열의 빠른 합과 행렬의 빠른 제곱

    분할 정복의 첫 번째 예제이다. 책 앞에 분할 정복에 대한 설명은 자세히 설명되어 있으므로 생략하겠다. 첫 번째 예제인 수열의 빠른 합과 행렬의 빠른 제곱을 구하는 문제인데 우리는 이 문제를 분할 정복으로 풀기 위해서 1+2+.... N까지의 합을 반으로 쪼갤 것이다. 그러면 이렇게 보기 좋은 식이 나온다. 그런데 우리는 분할정복을 해야 하니까 기저 사례로 가서 1로 만나면 분할이 완료가 되었다고 코딩을 해야 하는데 저렇게 되어버리면 ((n/2)+1).....+ N) 부분이 a부터 b까지의 합 형식으로 표현이 되어 있어서 분할 정복으로 사용하기 불편하므로 식을 바꿔주어야 한다. 위에 나온 식을 첫 번째 사진 fastSum(x) 형식으로 바꾸어 주면? 이렇게 식이 정리되고 밑에 사진처럼 정의할 수 있다. ..

    Algorithm

    [#1]완전탐색-n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘

    일주일 만에 겨우 한 단원을 끝냈다. 말도 안 되는 공부 효율성이다. 일단 이 책을 읽는 순간 나의 두뇌에 대한 남 탓과 자괴감이 동시에 생기며 분노가 차오른다. 하지만 변태적 성향인지 이 책을 읽는 동안 재미가 없었던 순간이 없었고 끝까지 읽을 수 있을 거라는 확신이 든다. (시간에 대한 효율성은...) 이 단원에서는 완전탐색을 다루며 전체적으로 재귀 함수의 사용법과 시력을 향상한다. 사고 향상에 엄청난 도움을 주었다. 첫 번째 문제 n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #inclu..

    Algorithm

    이분탐색 구현 팁 및 반환값 줄이기(부제: 공부하며 정리하는 생각들)

    공부하면서 참조한 자료 1.종만북 2. https://blog.naver.com/jinhan814/222156334908 이분 탐색, 파라메트릭 서치 안 헷갈리는 TIP 예전에 종만북을 읽으면서 아래 글을 쓴 적이 있습니다. 아래 글에는 반복문 불변식을 이용해 lower_bound,... blog.naver.com 이분탐색은 문제에서 주어지는 탐색 값의 기준을 찾는 것이 문제이다. 예를 들어 1부터 10억cm의 길이의 자를 분할해서 최소 5개의 개수로 나누고 싶은데 이 때 "분할하는 경우에 가장 큰 분할 길이를 구하시오" 같은 문제에서 분할하는 길이를 구하면 되는 문제이다. 알고리즘에 관련된 설명과 강의는 나보다 뛰어나신 분도 너무 많고 작성하시는 분도 너무 많기에 넘어가고 이분탐색을 구현할 때 구현의 ..

티스토리툴바