1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 백준 1697번 숨바꼭질 문제이다. 백준에는 숨바꼭질 시리즈의 문제가 많은데, 이전 문제는 그리디, DP등 다양한 알고리즘으로 해결이 가능했다. 이 문제 역시 여러 해결 방안이 있지만 타겟 알고리즘은 너비우선탐색(BFS)이다. 문제에서 주어진 예시를 보면 수빈이의 위치는 5이고 동생의 위치는 17이다. 수빈이는 1초후에 위치-1, 위치+1, 위치*2 의 위치로 이동할 수 있다. 5의 경우, 4, 6, 10 으로 이동할 수 있는 것이다...
백준 7662 번 이중 우선순위 큐 문제이다. 우선순위 큐의 성질을 문제에 적용시킨 것인데, 우선순위 큐와 다른 것은 가장 큰 값과, 가장 작은 값이 모두 손쉽게 삭제가 가능 하다는 점이다. 이 문제에서 주어지는 k값의 범위가 10000정도만 되어도 list를 고려해 볼 수 있었지만, 범위가 넓은 관계로 다른 컨테이너를 사용해야한다. 여기서 사용할 수 있는 컨테이너는 map과 multiset을 사용할 수 있다. map을 사용하면, 첫 번째 인자는 값 자체를 넣어주고, 두 번째 인자는 값의 개수로 설정해서 동일한 key값이 삭제될 경우 두 번째 인자의 값을 줄이는 식의 풀이를 할 수 있다. multiset을 사용하면 key값의 개수를 일일이 줄여줄 필요가 없기 때문에 map으로 구현하는 것 보다 쉽게 구현..
📕Facts(한 것) 백준 문제 풀기 프로그래머스 문제 풀기 C++ 책 읽으며 공부하기 스프링 복습 📕Feeling(느낀 점) #include #include #include #include #include using namespace std; bool solution(vector phone_book) { bool answer = true; sort(phone_book.begin(), phone_book.end()); smatch m; regex e; for(int i = 0; i < phone_book.size()-1; i++){ e = phone_book[i]; if(regex_search(phone_book[i+1], m, e) && (m.suffix().length() + m.length()) =..
📕그리디 알고리즘이란 ? 그리디 알고리즘은 코딩테스트에 자주 나오는 단골 문제이면서, 알고리즘 문제에 널리 사용되는 알고리즘이다. 그리디 알고리즘은 무엇일까? 그리디 알고리즘의 정의는 다음과 같이 말할 수 있다. "A greedy algorithm always makes the choice that looks best at the moment" 그리디 알고리즘은 '지금 당장 좋은 것을 고르는 방법'이다. 즉, 선택의 순간이 왔을 그때, 가장 좋은 것을 선택하는 것이다. ('Greedy'라는 이름을 보더라도 탐욕적인 것을 알 수 있다.) 📕 Greedy algorithm vs Dynamic programming 그리디 알고리즘과 다이나믹 프로그래밍을 언뜻 보면 비슷하다고 생각할 수 있다. 절차적으로 해결법..
1.Facts(한 것) 백준 문제 풀기 HTML공부하기 학교 수업 듣기 swift 기본 문법 공부하기 2.Findings(배운 것) C++17에서는 라이브러리에서 최대공약수와 최소공배수를 위한 함수가 존재한다. gcd와 lcm이 바로 그것인데, 기존에는 gcd와 lcm을 재귀적으로 호출해서 구현해야 했던 반면, 이제는 단순히 함수 호출만으로 쉽게 문제를 풀 수 있게 되었다. swift 에서는 Optional이라는 변수가 있다. 값이 있을 수도 있고, 없을 수도 있다니... C에서는 값을 설정하지 않고 프린트를 하면 쓰레기 값을 출력하지만, Swift에서는 nil(없음)을 출력한다. 당연할지 모르는 말이지만, Optional 변수를 다른 변수에 할당할 수는 없다. 옵셔널 변수가 있을지 없을지 모르니까 말이..
백준 9012번 괄호 문제이다. 실버4의 문제. 스택의 활용 정도 되는 문제이다. 스택의 기본구조인 선입후출의 개념과 stack.empty(), stack.top() 등의 개념을 활용하여 풀 수 있는 문제이다. 이 문제의 핵심은 닫는 괄호 ')' 의 짝이 있는가를 찾는 것이다. 처음부터 닫는 괄호가 들어오면 당연히 NO를 반환해야 하는것이고 닫는 괄호와 여는 괄호의 갯수가 같아도, 짝이 맞지 않으면 해결할 수 없다. 아래의 코드를 살펴보자. #include #include #include using namespace std; int main() { int testcase; cin >> testcase; // 몇 번 돌지 입력받음 while(testcase--) { stack st; string s; ci..
백준 10828 스택 문제이다. solve.ac에서 제공하는 실버4 문제이다. 문제를 읽어보면 단순히 스택을 구현하라는 문제이다. 물론 이 문제를 어떤 언어로 푸느냐에 따라서 문제 난이도가 천차만별이지만, 대부분의 하이레벨 언어에서는 기본 라이브러리에서 스택을 지원하기 때문에 문제를 푸는 것은 어렵지 않다. 물론 C를 사용해서 풀면, 스택을 다 구현해야 하기 때문에 상당히 복잡하다. 아래는 c++ 코드 전문이다 #include #include #include #include #include using namespace std; // //14 //push 1 //push 2 //top => 2 //size =>2 //empty => 거짓 => 0 //pop => 맨위 => 2 //pop => 맨위 => 1..
1.Facts(한것)프로그래머스 알고리즘 문제풀기c++ STL 복습하기2.Findings(배운것)최대공약수와 최소공배수를 구하는 방법은 여러가지가 있지만 그 중에서도 유클리드 호제법이 으뜸이다.queue자료구조에서는 queue.back(), queue.front()등으로 앞뒤의 원소를 바로 반환 할 수 있다.queue에서 삭제는 역시 q.pop()으로 가능하고, 당연히 선입선출이다.3.Feeling(느낀점)당장 내일이 코딩테스트인데 공부를 하면 할수록 모르는게 자꾸 튀어나온다. 프로그래머스 기준 레벨 1에서 쉬운 2정도 나오면 풀 수 있겠지만 그 이상으로 넘어가면 어렵다. 붙으면 좋고, 떨어지면 경험한거다 아직 3학년 2학기인데... 조기졸업하기엔 듣고 싶은 수업도 많고 이렇게 대학생활 끝내고 싶지도 않..
