C++47

• 

  [c++] 다익스트라 알고리즘 (백준-최단경로 1753) 다익스트라 알고리즘이란? 다익스트라 알고리즘이란 한 지점에서 그래프 상의 나머지 모든 지점으로의 최단 경로를 구할 수 있는 알고리즘이다. 다익스트라 알고리즘은 그래프 상의 어느 한 간선의 가중치라도 음수가 존재하면 안된다. 이는 다익스트라 알고리즘이 현재 선택하는 것이 최선의 방법이라는 greedy를 기반으로 한 알고리즘이기 때문이다. 만약 음수의 가중치가 있다면 이 경로를 계속 지나갈수록 더욱 최선의 값을 가지게 되므로 다익스트라 알고리즘에 위배된다. (음수의 가중치를 가질 수 있을 때는 벨만 포드 알고리즘을 이용해야한다.) 다익스트라 알고리즘을 구현하기 위해서는 2가지의 과정을 반복해주면 된다. /* 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. -> 이를 위해 처음 배열을 무.. c++/알고리즘 2023. 1. 25.

• 

  [c++] 알고리즘 그래프 - 위상 정렬 - 백준 - 줄 세우기 2252 위상 정렬이란? 위상 정렬이란 어떤 집합에서 원소들의 우선 순위 정렬이라고 할 수 있겠다. 또한 위상정렬은 비순환 방향 그래프 즉 (DAG : Directed Acyclic Graph)에서 가능하다. 즉 그래프를 이루는 노드들 간의 순환이 존재하지 않게 방향이 존재할 때 가능한 정렬이다. DAG 위와 같은 DAG그래프를 선형적 그래프로 변경하는 것을 위상정렬이라고 한다. 위상정렬은 말 그대로 위상을 정렬한다는 뜻으로 이 정렬에는 각 노드들의 우선 순위가 중요하다. 또한 우선 순위만을 고려하기 때문에 최종 결과 값이 여러 개가 될 수 있다. 즉 위의 비선형 그래프는 다음과 같은 뜻을 내포한다. 1보다는 0이 선행되어야한다. 1보다는 4가 선행되어야한다. 2보다는 1이 선행되어야한다. 2보다는 4가 선행되어.. c++/알고리즘 2023. 1. 25.

• 

  [c++] 백준-제단 5626 문제 입력과 출력 사실 이 문제를 풀 때 DP를 이용해서 푸는 문제라는 것을 알고 있었기 때문에 쉽게 접근할 수 있었다. (물론 난이도 자체는 어렵다 매우) DP는 점화식을 세우면 끝나는 문제다. 문제를 파악해보면 다음과 같다. 문제 해설 우선 제단을 세울 수 있는 경우를 생각해보았다. x 가능 가능 x x 가능 가능 가능 가능 x 점화식은 대부분 memoization된 이전 상태에서 현재의 값을 찾아낼 수 있기에 두 가지의 경우만을 고려해보았다. 2층의 가능한 경우는 1층의 경우에 따라 가능할 수도 불가능할 수도 있다. 따라서 이는 현재 상태가 이전 관계에 영향을 받는 점화식으로 풀 수 있는 DP문제이다. 그렇다면 현재 상태는 이전 상태의 어떠한 영향을 받을까? 다음 세 가지 경우가 있을 수 있다. 현.. c++/알고리즘 2023. 1. 25.

• 

  [c++] 코딩테스트 준비 과정 중 자주 쓰는 STL 정리 _ string 처리 1. string 처리 1. substr string s; s.substr(0,1); s.substr(시작 인덱스, 끝 인덱스) 끝 인덱스까지 잘린다. 2. 아스키 코드 A = 65번, Z = 90번, a = 97번 z = 122번 3. find string s = "i like coding"; cout c++ 2023. 1. 2.

• 

  [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++ 프로그래머스] 문자열 압축 문제 프로그래머스 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++] 백준- 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.

• 

  백준-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.