[1]. 그룹 단어 체커(1316)- C++ 똑같은 스팰링이 연속해서 나타나면 그룹으로 만들고, 같은 스팰링이 떨어져 있다면, 그룹 단어가 아니기에 그룹 단어의 개수에 포함하지 않는다. [1.1] 구현aabbbccb 는 bbb, b의 같은 b의 그룹 단어가 2개 있으니 개수에 포함하지 않게 구현하면 된다.map을 이용했다. 알파벳이 소문자로 되어 있으니 크기가 26인 배열을 만들어서 arr[word[i] - 'a'] 형태로 구현하여도 된다.반복문(for) 안에서 첫 i 가 0 일 경우에는 i-1을 하지 못하지 처음 m[word[0]] = true로 초기값을 설정하여 i가 1을 시작하게 만들게 했다.#include using namespace std;int t, cnt = 0;string word;int..
알고리즘/문제
[1]. 차이를 최대로 (C++) [1.1] 문제 N개의 정수로 이루어진 배열 A가 주어진다, 적절히 정수의 순서를 바꿔 최댓값을 찾는 문제 [1.2] 해설 DFS 알고리즘을 적용해서 풀어보았다. 배열의 크기가 3이고, 배열의 값이 [1, 2, 3 ] 일 경우를 생각하면 아래와 같이 총 3가지의 경우를 생각하면 구현하기 편하다. 방문한 경우, 방문하지 않은 경우, 탐색이 트리의 끝에 방문한 경우의 DFS Tree 를 생각하며 코드를 구현하면 편하다. (1). 방문한 경우 빨간색은 이미 배열에 있는 경우이기 때문에 방문할 필요가 없다, 따라서 해당 빨간색 트리는 탐색하지 않는다. (2). 방문하지 않는 경우 파란색은 방문하지 않았기에 방문하여 경우에 수를 계속해서 계산한다. (3). 탐색이 트리의 끝에 방..
ATM 1. 문제 줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는 데 걸리는 시간 P가 주어졌을 때, 각 사람이 돈을 인출하는데, 필요한 시간의 합의 최소값을 구하는 프로그램을 만들어야 한다. 2. 해설 정렬이 안된 경우와 오름차순으로 정렬된 경우를 비교하면 해답을 찾을 수 있다. (1). 정렬이 안된 경우 5명의 사람일 때, 핵심은 정렬이 안된 배열일 경우인 [5, 1, 2, 3, 4]를 생각해 보면 1번 사람 -> 5 = 5분 2번 사람 -> 5 + 1 = 6분 3번 사람 -> 5 + 1 + 2 = 8분 4번 사람 -> 5 +1 + 2 + 3 = 11분 5번 사람 -> 5 + 1 + 2 + 3 + 4 = 15분 5 + 6 +8 + 11 + 15을 더하면 45분을 기다려야 한다. (2). 오름차..
Longest Substring Without Repeating Characters 첫번째 풀이 O(n2) 처음 접근 처음 접근법은 abcabcbb, 이중 반복문을 통해서 첫번째 문자열과 일치하는지를 확인하고, 일치하면, 거기서 break를 걸어서 문자열 대치를 진행했다. 문제점은 첫번째 문자열만 일치한다는 점이였고, 2, 3 ... 이어지는 문자열이 존재하는지는 확인하지 못했다. 따라서 수정한 접근, Hash Map을 활용한 Brute Force - O(n2) 그래서 HashMap을 따로 생성하여, 반복적으로 확인하는 문자열마다 HashMap에 존재여부를 판단하여, 진행한다. a := "abcabcbb" var ans, tmp int = 0, 0 var hMap = make(map[rune]int) f..
LeetCode TwoSum 예제 Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. 내가 푼 풀이 func twoSum(nums []int, target int) []int { resultValue := make([]int, 2) for i := 0; i < len(nums); i++ { for j := 0; j < len(nums); j++ { if i == j { continue } if nums[i]+nums[j] == target { resultValue[0] = i resultValue[1] = j return resultValue } } }..
문제링크 https://www.acmicpc.net/problem/9012 시사점 해당 문제에서 조심할 점이 있었다. ))(( 의 경우 괄호의 갯수는 같으나 매칭이 되지 않습니다. 이점을 고려하지 않으면, 시간이 복잡도가 올라갈 경우가 많습니다. /****** * Author : Jiung * Filename : 9012-괄호.cpp * Version : Apple clang version 12.0.0 (clang-1200.0.32.27) * Date : 2021-02-24 * Copyright : Free */ #include using namespace std; /* * 괄호가 정확히 매칭되는지 확인하는 함수 */ void checkString(string check) { int a=0; /* * s..
시사점 문제에서 1번, 2번, 3번의 세 장의 색종이가 순서대로 놓인다고 합니다. 따라서 해당 다음 색종이가 전의 해당 색종이 위에 덮여졌을 때를 고려하고 문제를 푸는 것이 포인트입니다. 함수 리스트 -- process 문제를 푸는 과정인 함수 -- output 결과 값을 출력하는 함수 -- main 함수를 불러오는 main 소스코드 /****** * Author : Jiung * Filename : 10163.cpp * Version : Apple clang version 12.0.0 (clang-1200.0.32.27) * Date : 2021-02-16 * Copyright : Free */ #include #include using namespace std; struct paper { int N,..
문제 링크 www.acmicpc.net/problem/1316 /****** * Author : Jiung * Filename : 1316.cpp * Version : Apple clang version 12.0.0 (clang-1200.0.32.27) * Date : 2021-02-12 * Copyright : Free */ #include #include using namespace std; /* global variables */ int N, Words, DeferWord = 0; string tmp; /* * function GroupWordChecker * * bool check 배열을 이용해서 * 문제를 풀었습니다. */ void GroupWordChecker() { while(N) { cin..
팩토리얼은 수학에서 그 수보다 작거나 같은 모든 수의 곱을 말합니다. 기호는 !을 쓰이며, 팩토리얼이라고 말합니다. 만약 5라는 팩토리얼 수의 답을 알고 싶을 때, 느낌표의 기호를 붙여서 5! 라고 말합니다. N! = N * (N-1) * (N-2) * (N-3) * (N-4) 5! = 5 * (5-1) * (5-2) * (5-3) * (5-4) - 5! 의 공식 C++로 팩토리얼 구하는 방식으로는 반복문, 재귀로 주로 쓰곤 합니다. 재귀 이용 방법 int Factorial(int A){ if(A == 1) { return 1; } return A * (Factorial(A-1)); } 재귀를 구조적으로 생각해봤을 때, A가 1에 수렴했을 때 if statement에 걸려서 1을 리턴합니다. 5 * 4 ..
10845 큐 문제링크 https://www.acmicpc.net/problem/10845 문제풀이 및 주석 /****** * Author : Jiung * Filename : jiung.md * Version : Apple clang version 12.0.0 (clang-1200.0.32.27) * Date : 2021-02-10 * Copyright : Free */ #include // 입출력 사용 #include // 문자열 사용 #include // deque 구현 사용 using namespace std; // 표준 문자 사용 #define endl "\n"; // endl을 "\n"으로 정의 /* global variable * 명령어 갯수 N * push에 쓰일 변수 PushNum * d..
