나도 공부한다/알고리즘38 [프로그래머스] 석유 시추 (PCCP 기출문제) (C++) KeyDFS를 활용한 간단한 문제 같지만, 시간복잡도를 고려해서 잘 풀어야한다. Idea가장 먼저 생각난 아이디어는 '열부터 탐색하면서 열이 바뀔 때마다 DFS로 석유 덩어리 구하기' 이다.하지만 이 방법을 쓰게되면 열이 바뀔 때마다 방문 배열을 초기화해야하고, 시간복잡도가 n*m*n*m라서 시간초과가 발생한다. 하지만 난 시간초과가 된다는 걸 알면서도 그냥 이 방법으로도 코드를 짜보고 싶었다. 이유는 없다.. 아래는 정확성은 통과하지만 효율성은 모두 통과하지 못하는 코드이다.#include #include #include using namespace std;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};bool visited[500][500]={false,};int cnt=.. 2024. 9. 12. [프로그래머스] 뉴스 클러스터링 (2018 카카오 신입 기출) (C++) Key문자열 문제이기 때문에 문자열 관련 내장 함수를 어느정도 알고 있어야한다. Idea문제 조건을 따라 구현하면 끝이다. 내가 푼 방식은 다음과 같다. 1. for문으로 str[i]값과 str[i+1] 값이 알파벳인지 검사한 후 둘 다 알파벳이 맞다면 대문자로 변경 후 벡터에 넣기- 만약 둘 중 하나라도 알파벳이 아니라면 해당 쌍은 버린다 & 대소문자를 신경쓰지 않는다는 조건에 부합- toupper 함수 사용 (char형식을 대문자로 변경해줌) 2. 이렇게 만들어진 v1(str1 문자들이 담긴 벡터)와 v2(str2 문자들이 담긴 벡터)를 비교해서 같은 원소가 있는지 찾아낸다.- 이 때 주의해야할 점은 중복값이 허용된다는 것이다. 만약 v1에 "AA"가 있고 v2에 "AA", "AA"가 있다면 교집합.. 2024. 8. 11. [프로그래머스] 합승 택시 요금 (2021 카카오 채용 기출) (C++) Key플로이드워셜 또는 다익스트라 문제. Idea"두 사람이 어느 지점까지 같이 가야 택시 요금이 최소가 될까?" 각자의 도착 지점이 a, b, 출발 지점이 s, 중간에 각자 가기 시작하는 지점이 k라고 했을 때 요금은 다음과 같다.graph[s,k] + graph[k,a] + graph[k,b]어느 지점까지 같이 가야 요금이 최소가 되는지 모르기 때문에 모든 노드(k)를 돌며 최소값을 갱신하면 끝이다. 다익스트라 알고리즘으로도 풀 수 있지만, 노드 개수가 최대 200개밖에 안되기 때문에 플로이드 워셜 알고리즘을 사용했다. 기본 플로이드워셜 알고리즘에 아이디어 한줄만 추가하면 되는 문제이기 때문에 아이디어를 생각해냈다면 크게 어렵지 않다. 이 때 주의해야할 점이 있다. 요금이 100,000라고해서 INF.. 2024. 7. 28. [프로그래머스] 광물 캐기 (C++) Key그리디로 풀 수 있는 구현문제조건을 꼼꼼히 고려해야한다.특히 곡괭이로 채굴 가능한 범위보다 광물 수가 더 많을 수 있다는 점을 유의해야한다. Idea1. minerals 배열을 5개 단위로 끊고 광물별 가중치를 줘서 그룹별 가중치 합을 구한다. (getScore 함수)2. 그리고 그룹별 가중치 합과 시작 인덱스(5개 단위 그룹의 시작인덱스)를 group에 저장한다.3. 가중치 합을 기준으로 내림차순 정렬한다. 이렇게 하면 캐기 어려운 광물이 많은 그룹일수록 앞으로 오게 된다.4. 이제 그룹을 탐색하며 그룹의 시작 인덱스를 기준으로 minerals 배열에서 5개 단위로 피로도를 계산하면 된다. 캐기 어려운 광물이 많은 그룹이 앞으로 왔으므로 좋은 곡괭이부터 쓰면 최소한의 피로도가 보장된다. 주의할 점.. 2024. 7. 23. [프로그래머스] 수식 최대화 (C++) (2020 카카오 인턴십 문제) Key연산자에 우선순위를 부여해서 최대값을 만드는 문제이다. 이 때 연산자는 +, -, *이다.입력이 string으로 주어진다.문자열 + 스택 + 순열(백트래킹)이 합쳐진 문제 같았다. Idea내가 떠올린 방법은 다음과 같다. 1. 우선순위를 매기기 위해 순열을 구한다. 이 때 순열은 중복되면 안된다. 2. 연산자를 우선순위와 쌍으로 묶어서 저장한다 - map 사용 3. stack과 출력 리스트를 사용하여 주어진 식을 후위표현식으로 변경한다. - 피연산자는 출력 리스트에 바로 추가한다.- 연산자의 경우 스택의 top과 비교하여 스택의 연산자의 우선순위가 더 높거나 같으면 스택에서 출력 리스트로 이동시킨다. 반대의 경우 현재 연산자를 스택에 추가한다. 현재 연산자를 스택에 추가할 수 있을 때까지 반복한다... 2024. 7. 22. [백준] 팩토리얼 0의 개수 (C++) KeyN은 최대 500이고, 500!을 감당할 수 있는 자료형이 없다. 따라서 직접 팩토리얼 수를 계산하는 방식을 사용할 수 없다.0의 하나면 10의 배수라는 뜻이다. 10은 2*5이다. 100은 2*2*5*5이다. 즉, 0의 개수는 2와 5 쌍의 개수와 같다는걸 알 수 있다. 10!을 예로 들면, 10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 이다. 여기서 2의 배수는 총 5개, 5의 배수는 총 2개. 따라서 결과값 뒤에는 00이 붙어있을 것이다. 계산기로 계산해보면 3628800이므로 0 두개가 맞다. IdeaN을 이루고 있는 2와 5쌍 개수를 세야하는데, 이 때 5의 배수가 몇개인지만 고려하면 된다. 왜냐하면 2는 모든 짝수에 포함되기 때문에 어떤 수라도 무조건.. 2024. 7. 16. 이전 1 2 3 4 ··· 7 다음
