c++60

• 

  [c++] Floyd의 알고리즘 - 가중치가 다른 길찾기 문제는 다음과 같다. 가중치가 같은 최단 경로의 알고리즘으로는 BFS를 사용할 수 있지만 이 같은 경우에서는 경로마다 가중치가 다르기 때문에 BFS로 접근하면 안된다. 대신 DP 다이나믹 프로그래밍을 사용하여 부분 최적해를 구해가며 진행할 수 있겠다. 1. map만들기 우선 배열에 map을 만들어주어야 한다. 이 때 중요한 것은 갈 수 없는 방향에 대해서는 infinite한 값- 매우 큰 값으로 이루어져야 한다는 것이다. 따라서 위의 그래프를 이용해 map을 만들면 다음과 같다. int w[6][6] = { {0,0,0,0,0,0}, {0,0,1,1000,1,5}, {0,9,0,3,2,1000}, {0,1000,1000,0,4,1000}, {0,1000,1000,2,0,3}, {0,3,1000,1000,.. c++/알고리즘 2022. 5. 25.

• 

  [c++]조합 1. 조합 조합이란 수학에서 우리가 흔히 쓰는 combination이다. 즉 순서와 상관없이 전체n개 중 k를 뽑는 서로 다른 경우의 수를 의미한다. 조합과 순열은 알고리즘에서 완전탐색 문제를 해결하는데 많이 사용된다. 그렇다면 이러한 조합을 재귀함수로 구현하는 경우를 살펴보며 재귀함수의 동작원리 또한 살펴보겠다. 2. 구현 #include #include #include using namespace std; int n = 5; int k = 3; int a[5] = { 1,2,3,4,5 }; vector b; void print(vector b) { for (int i = 0; i return -> combi(4,b)나머지(pop)->.. c++/알고리즘 2022. 5. 13.

• 

  [c++ DP] 다이나믹 프로그래밍 - 예제 1. Dynamic Programming이란? 동적계획법이라고도 하며, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하고 다시 그 결과를 이용하여 큰 문제를 해결 할 때 사용하는 방식으로 프로그래밍 기법 중 하나이다. 그렇다면 위의 설명대로 결과를 저장할 공간이 있어야한다. 이렇게 되면 공간 복잡도 적인 측면에서 손해를 봐야하는데 왜 이러한 방법을 이용하는 것일까? 답은 간단하다. 조금의 공간 복잡도를 포기하더라도 시간 복잡도적인 측면에서 큰 이득을 볼 수 있기 때문이다. 알고리즘 문제를 풀다보면 엄청나게 큰 시간복잡도를 요구하는 문제들이 존재한다. 예를 들면 O(n!)이나 O(n^n)같은 알고리즘이다.(즉, 완전탐색과 같은 경우이다.) 하지만 Dynamic Programming즉 동.. c++/알고리즘 2022. 5. 11.

• 

  [c++ 프로그래머스] 문자열 압축 문제 프로그래머스 KAKAO 2020 Blind문제이다. 여기에서 나는 c++을 이용하여 작성했으며 for문을 두 번 돌며 문제를 해결하여 O(n^2)으로 해결하였다. 핵심은 substr함수를 얼마나 잘 사용하느냐와 인덱스의 이동을 얼마나 수학적으로 잘 표현할 수 있는가 였다. 처음에 테스트 케이스를 돌릴 때 계속 3개가 틀려서 왜일까 고민했는데 처음에 중복되는 문자의 개수가 1자리 수일 때만을 고려해서 실패한 사례가 존재하는 것이었다. int solution(string s) { int m = s.size() / 2; string temp; string copy = s; int si = 1; int minlength = copy.length(); for (int i = 1; i c++/알고리즘 2022. 5. 8.

• 

  [C++] 백준- 1189 컴백홈 (완전탐색 + DFS) 1. 문제 2. 조건 여기에서 내가 고민했던 점은 이 문제는 기존의 최단거리만을 구하던 BFS문제들과는 다르다는 점이다. 이동하는 거리는 상관이 없고 그저 제약 조건이라고는 T로 표시된 곳은 지나가지 못한다. 또한 갔던 곳은 지나가지 못한다는 점이다. 따라서 출발점에서 도착점까지 이동할 수 있는 모든 경우의 수를 탐색하여 거리를 구하고 내가 원하는 거리에 해당하는 경로의 수를 출력해야하는 완전탐색 문제였다. 그래서 나는 재귀함수를 이용해서 이 문제를 해결하였다. 3. 풀이 #include #include #include using namespace std; int R, C; int K; char map[10][10]; int visited[10][10]; int dx[4] = { -1, 0, 1, 0 }.. c++/알고리즘 2022. 5. 1.

• 

  [C++]완전탐색 1. 완전탐색이란? 제목에서도 알 수 있듯이 가능한 모든 경우의 수를 탐색하는 것을 의미한다. 알고리즘 문제에서는 크게 6가지 유형 정도가 있다. 1)Brute Force 진짜 말 그대로 가능한 모든 방법을 단순히 찾는 방법이다. 흔히 패턴매칭 같은 곳에서 사용되는데 예를 들어 txt파일에서 abcd라는 패턴을 찾을 때 텍스트 파일의 첫 번째부터 찾다가 패턴이 매치가 안되는 순간 두 번째로 이동하여서 다시 비교하고 아니라면 세번째 문자부터 시작하여 다시 비교하는 무식한 알고리즘을 의미한다. 또한 4자리의 비밀번호를 푸는 문제에서 brute force알고리즘을 적용하게 되면 가능한 모든 경우의 수는 10 * 10 * 10 * 10 = 10000번을 비교해야 풀리는 그런 방식이다. 2) 백트래킹 백트래킹은 .. c++/알고리즘 2022. 4. 29.

• 

  [c++] 백준- 1436 영화감독 숌 문제는 위와 같았다. 사실 처음에 문제를 보고 많은 고민을 했다. 처음에는 엥 걍 숫자 증가시키면서 뒤에 666만 붙여주면 되는 거 아닌가? 했다가 6660 6661 .... 등의 존재를 깨달으며 이거 뭐지..?하는 심정이었다. 그 후 패턴이 있을까하며 아이패드로 계속 찾아가보면서 패턴을 찾으려했지만 무의미한 발악이었다. 때로는 이러한 패턴을 찾는 거보다 컴퓨터를 쓰는 이유는 단순 무식한 작업을 놀라운 속도로 하기 때문이잖아! 라는 생각이 들어서 그냥 i를 하나씩 증가시켜보면서 666이라는 패턴을 찾으면 횟수를 1 감소시키는 방법은 어떨까?라는 생각을 하게 되었다. 따라서 막막해보이던 문제 풀이 방법이 떠올랐고 처음 생각했을 때 뭐 6을 만나면 다른 처리를 해주고 자리수에 따라서도 다르게 해주어야하나.... c++/알고리즘 2022. 4. 28.

• 

  [c++] Huffman Algorithm - 파일 압축 알고리즘 1. Huffman Algorithm이란? 우리가 흔히 파일을 네트워크를 통해 전송할 때 전송되는 파일의 정보 양을 줄이기 위해서 zip파일이라는 형식의 파일로 압축을 하여 보낸다. 현재 zip파일의 알고리즘 Deflate알고리즘이라는 것을 사용해서 파일을 압축하고 있지만 자세히 들여다보면 Deflate알고리즘이란 LZ77알고리즘과 Huffman Algorithm의 혼용이다. 나는 그 중 huffman algorithm을 c++로 구현해보았다. 컴퓨터 상의 정보는 0과 1두가지가 존재한다. 하지만 파일 안에 들어있는 내용들은 'a', 'b'와 같은 문자들이 들어있는데 컴퓨터는 다시 이 문자들을 아스키 코드라는 컴퓨터가 문자를 숫자로 표현하는 방식으로 바꿔서 알아듣는다. 따라서 우리는 문자를 어떠한 숫자로.. c++ 2022. 4. 28.

• 

  [c++] BFS, DFS(너비 우선 탐색. 깊이 우선 탐색) 1. 그래프에서 탐색 알고리즘 문제를 풀다보면 많은 그래프들을 마주하게 된다. 대표적인 예가 미로에서 최단거리를 찾는 문제나 연결되어 있는 컴포넌트를 찾는 문제에서이다. 우리는 이렇게 그려져있거나 가상의 그래프를 탐색해야하는데 컴퓨터는 일정한 알고리즘에 의해 이러한 그래프들을 탐색한다. 그 중 대표적인 예가 DFS(깊이 우선 탐색 Depth-First-Search)와 BFS(Breadth-First-Search 너비 우선 탐색)이다. 2. DFS (깊이 우선 탐색)이란? 그래프가 위와 같이 존재할 때 다음 분기로 넘어가기전 해당 분기를 완벽하게 탐색한 후 넘어가는 탐색 방식이다. 위의 그림을 보면 한 번 이동한 줄기의 마지막에 도착할 때까지 그 분기를 탐색한 후 다음 분기로 넘어가는 것을 확인할 수 있다.. c++/알고리즘 2022. 4. 27.

• 

  [c++]백준-3474 교수가 된 현우 1. 문제 문제는 다음과 같다 나는 처음에 그저 brute force한 방법으로 값을 구한 뒤 substr함수를 이용해서 0을 잘라내려 했으나 굉장히 무모한 도전이었다. 왜냐하면 100!의 값만 하더라도 컴퓨터가 출력해낼 수 있는 값인 long long자료형의 범위마저 훌쩍 뛰어 넘어버리기 때문이다. 따라서 좀 더 고민을 하던 중 뒤가 0이 나오는 경우를 생각해보았다. 이 때 0이 나오는 경우는 2와 5가 결합된 경우 밖에 없다는 사실을 알게 되었다. 따라서 두 번째 생각한 방법이 만약 5를 입력받았으면 5 4 3 2 1의 수를 모두 소인수 분해한 다음 2와 5의 개수를 세서 더 작은 값을 출력하는 방법이었다. 이러한 방법으로 작성한 나의 코드는 다음과 같다. #include #include #inclu.. c++/알고리즘 2022. 4. 26.

• 

  백준-4659 비밀번호 발음하기 문제는 다음과 같다. 이 때 문제에서 고려할 것은 3가지이다. 모음이나 자음이 3번 연속으로 오면 안된다. e나 o를 제외한 같은 글자가 2번 연속으로 오면 안된다. 모음(a, e, i, o, u)을 하나 이상 포함해야 한다 나의 코드는 아래와 같다. #include #include #include #include using namespace std; string password = ""; bool vowel = 0; bool seq = 0; int vow = 0; int con = 0; stack charStack; bool isVowel(char a) { if (a == 97 || a == 101 || a == 105 || a == 111 || a == 117) return true; else ret.. c++/알고리즘 2022. 4. 6.

• 

  [C++] odd-Even Transposition Sort odd -even transposition Sort란? 홀 수인덱스 차례에는 홀수 인덱스와 홀수 인덱스 +1이 짝수 인덱스 차례에는 짝수 인덱스와 짝수 인덱스 + 1이 같은 실행 타임에 정렬한 후 합치는 과정이다. 그림으로 나타내면 다음과 같다. GPU를 이용해 병렬 처리가 가능한 경우 여러 개의 task를 나누어 그 나눈 task들을 한 번에 처리함으로써 sorting을 더 빠르게 처리할 수 있다. 하지만 cpu는 한 번에 하나의 task밖에 처리하지 못하니 병렬 처리를 하기 위해서는 GPU를 사용해야하는데 cpu에서도 병렬 처리처럼 보이게 프로그래밍을 할 수 있다. 바로 thread 개념을 이용해서이다. Thread란? thread란 하나의 프로세스 안에서 실행되는 여러 흐름의 단위라고 생각하면된다... c++/알고리즘 2022. 3. 29.