programming/알고리즘 (4) 썸네일형 리스트형 [programmers] 250136번 - PCCP 기출문제 2번(BFS, PCCP 기출문제) 1. 문제 및 예제 Level 2 문제들을 쭉 풀어가던 도중 PCCP 기출문제 두 문제가 공개되어 바로 풀어보았다. BFS 알고리즘이 핵심이지만, 더 빠른 알고리즘을 위해 범위를 저장하는 부분이 필요하였다. https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 시간 복잡도 때문에 BFS로는 풀 수 없다. O(N^3)이기 때문에 다른 방법을 생각해야 했다. 내가 생각한 방법은 다음과 같다. 아래와 같은 입력이 주어졌다고 가정하자. 이렇.. [알고리즘] C++을 활용한 후위 표기법의 계산 1. 이론 이 알고리즘은 중위 표기법에서 후위 표기법으로 전환한 후에 후위표기법을 실질적으로 계산하는 알고리즘이다. 이 부분은 전에 포스팅한 중위 표기법의 후위 표기법 변환 알고리즘보다는 훨씬 간단하다. 예외와 구현이 나름 쉬웠다. 이 부분은 학교 수업으로 공부하였다. - 후위표기식의 계산 알고리즘 후위표기식의 계산 알고리즘은 다음과 같다. 숫자가 나오면 무조건 스택에 Push 연산자가 나오면 스택에서 두개의 피연산자를 꺼내 계산한다. 연산자가 뺄셈 혹은 나눗셈인 경우 순서를 생각해야 한다. 이런 경우를 대비해 스택에서 나중에 꺼내진 연산자로부터 먼저 꺼내진 연산자에 대한 연산을 실행한다 계산된 연산자는 다시 스택에 넣어준다. 후위 표기식이 다 끝났다면 스택에 남아있는 피연산자가 식의 답이다. 이전 포스.. [알고리즘] C++을 활용한 중위 표기법의 후위 표기법 변환 1. 이론 작년쯤에 공부했던 알고리즘을 교내 수업에서 만났고, 내가 얼마나 공부를 부실하게 했는지도 알게 되었다. 대충 이론만 기억나는 상태여서 처음부터 다시 손으로 쓰면서 공부했다. 많은 책과 인터넷 자료들을 참고 하였으며 최대한 예외를 예상하여 작성하여 알고리즘을 써내려 갔다. - 중위 표기법 중위 표기법이란 이름 그대로 피연산자들 사이에 연산자가 있는 표기법을 말한다. 우리가 기존에 알고있는 수식이 전부 중위 표기법이다. 다음 식을 보자. 17 + 5 위의 간단한 식을 보면 두개의 피연산자 (숫자) 사이에 연산자 (계산 기호) 가 있다. 연산자 옆의 두개의 피연산자로 계산을 하는 방식이 중위 표기법이다. - 후위 표기법 후위 표기법은 중위 표기법과는 다르게 피연산자들 뒤에 연산자가 있는 표기법을 말.. [알고리즘] C++ vector을 활용한 정렬 구현(버블, 삽입, 퀵) 1. 이론 알고리즘 중에 제일 대표적인 '정렬' 알고리즘이다. 알고리즘을 전부 공부한 것은 아니지만 아마 알고리즘을 공부할 때 가장 기초적으로 공부하는 알고리즘인 것 같다. (C언어를 공부할 때도 나왔으니......) 버블과 삽입은 어려운 알고리즘은 아니라고 생각했지만(이미 완성된 알고리즘을 구현하는 것 밖에 하지 않았지만......), 퀵의 구현을 공부할 때는 "대체 어떤 천재가 이런걸 만든거지?" 라는 생각이 들 정도로 감명받았다. 다음은 각각의 알고리즘의 이론이다. - 버블 버블알고리즘의 이름이 '버블'인 이유는 밑에서 부터 큰 숫자들이 마치 거품처럼 보글보글 올라오는 모습과 비슷하다고 하여 만들어진 이름이다. 최대값을 하나씩 가려내는 알고리즘이라고 생각하면 이해하기 쉬울 것이다. 다음과 같이 순서.. 이전 1 다음
