공부한것을 잊지말자!

2022. 11. 15. 10:41 Problem Solving/프로그래머스

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고) 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 s는 길이 1 이상 200 이하인 문자열입니다. s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다. 숫자는 단어의 첫 문자로만 나옵니다. 숫자로만 이루어진 단어는..

[프로그래머스] - 최댓값과 최솟값(C/C++)

2022. 11. 14. 14:07 Problem Solving/프로그래머스

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] 문자열 s에는 공백으로 구분된 숫자들이 저장되어 있습니다. str에 나타나는 숫자 중 최소값과 최대값을 찾아 이를 "(최소값) (최대값)"형태의 문자열을 반환하는 함수, solution을 완성하세요. 예를들어 s가 "1 2 3 4"라면 "1 4"를 리턴하고, "-1 -2 -3 -4"라면 "-4 -1"을 리턴하면 됩니다.제한 조건 s에는 둘 이상의 정수가 공백으로 구분되어 있습니다. 입출력 예 s return "1 2 3 4" "1 4" "-1 -2 -3 -4" "-4 -1" "-1 -1" "-1..

[프로그래머스] - 햄버거 만들기(C/C++)

2022. 11. 7. 00:59 Problem Solving/프로그래머스

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] 햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 ..

[백준 1786번] - 찾기(C/C++)

2022. 11. 7. 00:55 Problem Solving/백준

1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net [문제 설명] [문제 풀이] 해당 문제는 KMP알고리즘을 이용하여 문자열 패턴 매칭을 하는 문제이다. 따라서 KMP 알고리즘에 대한 이해가 필요하다. 혹시 해당 알고리즘에 대해 잘 모른다면 아래 포스트를 참고하길 바란다. [Algorithm] - 문자열 탐색 알고리즘 : KMP 이론 KMP 알고리즘이란, 문자열 탐색 알고리즘으로써 알고리즘을 만든 사람들(Knuth-Morris-Pratt)의 앞글자를 딴 것이다. 웹페이지에서 ctrl + F를 이용하여 문자열..

[Algorithm] - 문자열 탐색 알고리즘 : KMP

2022. 11. 7. 00:43 Problem Solving/Algorithm

이론 KMP 알고리즘이란, 문자열 탐색 알고리즘으로써 알고리즘을 만든 사람들(Knuth-Morris-Pratt)의 앞글자를 딴 것이다. 웹페이지에서 ctrl + F를 이용하여 문자열을 검색할 때, 특정 단어를 검색엔진에서 검색할때도 사용될 수 있다. 해당 알고리즘의 시간복잡도는 O(N+M)을 가진다. 구현 KMP 알고리즘은 접두사(prefix)와 접미사(suffix)의 개념을 활용하여 실패함수 테이블을 만들고, 테이블을 활용하여 반복되는 문자열을 건너뛰면서 패턴을 찾는 알고리즘이다. 접두사와 접미사에 대해 간단하게 정리해보고자 예를 들어보겠다. "abacabab"라는 문자열이 있다고 가정하자. 우리는 각 문자의 길이에 따라 접두사와 접미사가 일치하는 최대 길이를 테이블에 저장할 것이다. 실패함수 테이블을..

[Algorithm] - 문자열 검색 알고리즘 : Naive String Search

2022. 10. 21. 05:54 Problem Solving/Algorithm

이론 문자열 검색 알고리즘이란, 어떤 문자열 S에서 패턴 P가 있는지 찾아내는 알고리즘이다. Naive String Search 알고리즘은 문자열 검색 알고리즘 중에 효율이 좋지 않지만, 가장 구현하기 쉽고 작은 입력이라면 충분히 고려해볼만 한 알고리즘이다. 전체 문자열 S의 길이를 N, 찾고자하는 패턴 P의 길이가 M이라고 할때, 최악의 경우 O((N-M)*M)의 시간 복잡도를 갖는다. 구현 전체적인 흐름은 아래와 같다. 1. 문자열 S의 첫번째 문자와 패턴 P의 첫번째 문자를 비교하여 같다면 다음 문자를 비교한다. 2-1 다음 문자가 같다면 그 다음 문자를 비교한다. 2-2 다음 문자가 같지 않다면, 패턴 P를 한칸 밀어서 문자열 S의 두번째 문자와 패턴 P의 첫번째 문자를 비교한다. 3. 위와 같은..

SourceTree : Invalid username or password Error 관련

2022. 10. 20. 23:05 Development/etc

SourceTree를 사용하여 Push할때 발생하는 에러인 Invalid username or password Error에 대해 해결 방법을 찾아서 블로그를 작성한다. Push 할때 아래와 같은 창이 뜨면서 에러가 발생하는 경우가 있다. 이런 에러가 발생하는 이유는 아이디나 비밀번호를 잘못 입력해서인데, SourceTree는 굉장히 불친절하게도 한번 입력하면 다시 비밀번호를 입력하는 창이 발생하지 않는다. 이럴때는 SourceTree의 인증정보를 찾아서 삭제해주고 다시 푸쉬를 하면 비밀번호 입력하는 창이 다시 발생한다. 비밀번호를 계속 틀리면 계속 삭제하고 다시 인증하면 된다. 해당 파일은 아래의 경로에 있다. C:\Users\username\AppData\Local\Atlassian\SourceTree..

[백준 2252번] - 줄세우기(C/C++)

2022. 10. 14. 09:55 Problem Solving/백준

2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net [문제 설명] [문제 풀이] 이 문제를 풀기전에 위상정렬 알고리즘에 대해 알고 있으면 쉽게 풀 수 있다. 위상정렬 알고리즘에 대해 잘 모른다면 아래 포스트를 읽고오면 푸는데 도움이 될 것이다. [Algorithm] - Topology Sort(위상정렬) 위상정렬(Topology Sort) 란 ? 위상(Topology)이란, 노드들을 물리적으로 연결해 놓은것을 의미한다. 위상 정렬이라는것은, 위 처럼 노드들을 연결해놓은 ..

[C++] Lock(std::lock_guard, std::unique_lock)

2022. 10. 14. 01:37 Development/C++

저번 포스트에서 멀티 쓰레드 프로그래밍시 race condition에 의해 공유 자원을 사용하는 critical section에 자원을 동시에 접근했을때 문제가 생기는것을 알아보았다. 이런 상황을 방지할 때 사용할 수 있는 mutex라는것에 대해서도 알아보았다. 이번 포스트에서는 아래와 같은 것에 대해 공부해보고자 한다. 1. mutex.lock()을 걸어두고, mutex.unlock()을 해주지 않았을때 어떠한 문제가 발생하는지 2. 위의 문제를 방지하기 위한 유용한 것들 mutex unlock을 해주지 않았을때 발생하는 문제점 저번 포스트에서 mutex를 공용 화장실에 자물쇠에 비유했었다. 동일하게 mutex를 자물쇠라고 생각했을때, lock()을 한 상황은 어떤 한 사람이 화장실에 들어가서 문을 잠..

[Algorithm] - Topology Sort(위상정렬)

2022. 10. 12. 08:41 Problem Solving/Algorithm

위상정렬(Topology Sort) 란 ? 위상(Topology)이란, 노드들을 물리적으로 연결해 놓은것을 의미한다. 위상 정렬이라는것은, 위 처럼 노드들을 연결해놓은 그래프를 방향을 거스르지 않도록 나열하는 것이다. 아래 그림을 참고하자. 위상정렬을 가장 잘 설명해줄수 있는 예로 대학교의 선수과목 구조를 예로 들 수 있다. 만약, 특정 과목을 듣기위해 필요한 선수 과목이 있다면, 그 선수과목부터 수강해야 한다. 이때 위상정렬을 사용하면 올바른 강의 순서를 찾아 낼 수 있다. 그래프의 구조에 따라 여러개의 정렬이 나타날 수도 있다. 위상정렬을 사용하기 위해선 시작노드를 특정하기 위해 DAG(Directed Acyclic Graph)여야만 한다. DAG는 사이클이 존재하지 않고, 하나의 방향만을 가지는 그..

[C++] Mutex

2022. 10. 8. 01:28 Development/C++

이전 포스트에서 std::thread를 이용하여 멀티 스레드를 사용해보았다. 포스트의 마지막에 말했던 멀티 스레드 프로그래밍을 하면서 주의해야 할 점에 대해 알아보려고 한다. thread를 처음 사용시 예상하지 못하는 문제점 우선, thread는 process와 다르게 스택 메모리를 제외한 나머지 힙, 코드, 데이터 영역을 공유한다. 아래와 같은 코드를 작성하고 출력되는 결과를 한번 예상해보자. #include #include #include using namespace std; int num; void addNum() { num++; } int main() { vector vThread; for(int i = 0; i < 5; i++) { vThread.push_back(thread([]() { for..

[프로그래머스] - 네트워크(C/C++)

2022. 10. 7. 00:00 Problem Solving/프로그래머스

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 soluti..

티스토리툴바