본문 바로가기

전체 글

 (403)
백준 32176번 - 통신 시스템의 성능 저하(C++) https://www.acmicpc.net/problem/32176첫 풀이론 bfs를 통해 가장 가까운 K 개를 찾으려 했다. 경로 손실은 적을수록 좋기 때문이다. 그러나, 결국 이 방식도 K1 개의 모든 경우를 조합해보는 것과 다를바가 없다.그래서 이 문제는 최적화된 브루트포스가 정답이다.문제 조건을 봤을 때, Ex) N = 4, M = 14이면, K1 = 10, 11, 12, 13, 14 중 하나가 된다. 그리고 가능한 경우의 수는 14 combination 10, 14 combination 11, 14 combination 12, 14 combination 13, 14 combination 14 조합의 성질에 따라 14 combination 4, 14 combination 3, 14 combinat..
프로그래머스 - 2020 KAKAO BLIND RECRUITMENT괄호 변환 https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 재귀를 사용한 구현 문제이다.  stack을 사용해 괄호가 올바른지 확인하는 것에다가 추가적인 요소를 덧붙힌 문제이다.  카카오에서 요즘은 이런 문제가 안나오는거 같은데 예전엔 구현을 자주 시킨 것 같다. #include #include #include #include using namespace std;bool check(string s){ stack stk1; for(int i ..
프로그래머스 - 2018 KAKAO BLIND RECRUITMENT[3차] 방금그곡 https://school.programmers.co.kr/learn/courses/30/lessons/17683 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 시간을 정말 빡세게 잡았다면, 은근 귀찮은 파싱과 KMP나 라빈-카프 알고리즘을 사용해야했을 것이다. 하지만 이 문제는 그런 고급 문자열 검색 알고리즘까지 요구하진 않을것이다. 다만 C#, G# 같은 단어를 하나의 단어로 치환해주는 작업이 필요하다.  그런데 만약 여기서 음악이 나오는 시간을 00:00~23.59 라고 하면, 23 * 60 + 59 = 2,070,721 이고 이것을 O(N^2) 하면 ..
백준 6588번 - 골드바흐 추측 (C++) https://www.acmicpc.net/problem/6588 에라토스테네스의 체를 이용해 소수르 판별하고, 이후 완전탐색을 진행했는데 시간초과가 났다. 그래서 두번돌면 안되는 것을 확인했고,  i, n - i 가 둘 다 소수인 것을 찾아야한 다는 것을 생각해내었다. #include #include #define MAX 1000000using namespace std;vector primeNum;bool* check = new bool[MAX];int main(){ cin.tie(NULL); ios_base::sync_with_stdio(0); for(int i = 0; i > tmp; while(tmp != 0){ bool flag = false; ..
프로그래머스 - 2018 KAKAO BLIND RECRUITMENT[3차] 파일명 정렬 https://school.programmers.co.kr/learn/courses/30/lessons/17686 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 주어진 문자열을 조건에 맞게 HEAD, NUMBER, TAIL을 분리하고 그에 따른 정렬을 사용하면 된다. 그런데 중요한 것은  HEAD 와 NUMBER가 같을 경우엔 TAIL이 달라도 순서를 그대로 진행시켜야한다. 같은 우선순위를 가진 경우를 컨트롤하는 것이 문제의 관건이다.  C++ Algorithm의 sort는 불안정 정렬이다. 만약 A B C D 에서 sort했을 때 A와 B의 우선순위가 같다..
백준 25214번 - 크림 파스타(C++) https://www.acmicpc.net/problem/25214최솟값을 저장해두고, 현재 들어오는 값에서 뺀 값과, 이전 정답 값을 비교해가며 정답을 출력하면 되는 문제이다. 아이디어를 떠올리는 것이 생각보다 어려웠던 문제#include #include using namespace std;int dp[200001];int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; int minValue = 1000000001; int maxValue = 0; for(int i = 0; i > value; maxValue = max(maxValue, value); minV..
Spring Boot - RestClient 로 공공데이터 얻어오기 .
백준 5911번 - 선물 (C++) https://www.acmicpc.net/problem/5911 이 문제는 N이 1000이고 딱 하나의 물건만 할인할 수 있기 때문에 브루트포스 방식으로 모든 선물을 할인해볼 수 있다. 그래서 N * N으로 해결할 수 있다. 먼저 모든 선물을 하나씩 할인해보고 그 이후 비용이 덜 드는 순서대로 정렬하고 가능할 때 까지 선물을 보내보면 된다. 그리고 만약 여기서 할인할 수 있는 선물이 여러개가 된다면 https://www.acmicpc.net/problem/25947 이 문제가 된다. 할인할 수 있는 선물이 한개가 아니기 때문에 N * N 으로풀 수 없는 여러개의 조합이 되어버려 브루트포스는 사용할 수 없고 이 문제에선 먼저 정렬을 통해 오름차로 만들고 이후 막혔을 때 할인을 계속 해보면서 정답을 찾아간..

티스토리툴바