문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 내 스스로 풀지 못했다. DP문제인데, 식 세우는 게 아직도 .. 부족하다. 더 열심히 하자. 일단 이중 for문으로 모든 경우를 탐색하는 건 n이 최대 100,000이라서 불가능하다. arr[i-1] + arr[i]가 현재 원소 arr[i] 보다 크다면 최댓값이 계속 갱신되는 것이고, arr[i-1] + arr[i]가 현재 원소 arr[i] 보다 작다면, arr[i-1]이 음수라는 것이고, 그러..

문제 https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 풀이 문제 이해부터 하자면, 2-친구라고 말해서 좀 복잡한데 그냥 A-B가 친구이거나 / A-B가 친구가 아니여도 A, B에게 C라는 공통된 친구가 있으면 A-B가 친구가 된다. (A-C, B-C친구 -> A-B친구) 이 문제에는 다양한 풀이법이 있다. 아무래도 n이 최대 50이라 완전탐색, O(n^3)에도 문제 해결이 가능하다. BFS :여기 정리가 잘 되어있는데 나는 잘 이해가 안된다ㅠ.ㅜ ..

문제 https://www.acmicpc.net/problem/1987 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 풀이 왜 시간초과가 날까 DFS 연습하려고 고른 문제인데 DFS로 풀면 시초 뜬다.. 솔직히 BFS가 더 쉬울 것 같긴하고, 시초도 안뜰 것 같다. 그리고 dx,dy순서에 따라 시초 나는지 안나는지도 결정되니까 아무리 생각해도 DFS로 완탐하는 문제는 아닌 것 같다. pypy3로 해야 통과되기도 하고.. 코드 n,m = map(int,input().split()) arr = [list(map(str,input())) for _ in range(n)] dx = [-1,..

문제 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 풀이 DP문제이다. i번째 coins를 쓰는 경우, 안쓰는 경우를 비교한다. i번째 coins을 쓰면 dp[j-coins[i]] + 1이 점화식이다. 5원을 써서 11원 만드는 방법을 고안한다 하면, dp[11]과 dp[11-5] + 1을 비교한다. 어렵다.......................... dp어케하냐 코드 n,k = map(int,input()...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/181188?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 [그리디 + 정렬] 그니까 나는.. 그리디가 매우 약한 것 같다. 이런 논리력 어떻게 갖추나요.. 많이 푸는 게 답이겠지? 글씨는 .. 노답이지만 나름 혼자 이해하려고 열심히 노력했다. 1. 일단 e를 기준으로 오름차순 정렬을 한다. 왜냐면? e를 기준으로 비교를 해야한다! i-1번째 타깃의 e와 i번째 타깃의 s를 비교해야하는데, e를 기준으로 오름차순으로 정..

문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 스택+그리디 뒤에서부터 거꾸로 스택에 집어 넣는다. 만약 스택이 비어있다? 그럼 ans배열에 -1을 저장한다. 스택에 뭐가 있는데, 내가 지금 따지는 수가 스택의 맨 위에 것보다 작거나 같다? 그럼 계속 pop한다. 왜냐면 내가 필요한건 지금 내가 따지는 수보다 큰거니까. 그리고 내가 지금 따지는 수를 stack에 넣는다. 이걸 시험 때 떠올릴 수 있을까? 연습을 훨씬 더 해야겠지.. 코드 #in..

문제 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 LG 기출이랑 비슷하다. #17298과 비슷하게 stack + 그리디.. 하지만 값 출력하기 편하게 stack이 아닌 deque를 사용했다. 문자열의 이전 값들이 더 작으면 pop을 계속 해주고 k값을 감소한다. 72%정도에서 계속 틀렸습니다가 떴는데, 마지막 출력하는 과정에서 dq.size()-k을 꼭 해줘야했다. 그냥 auto써서 dq다출력하는게 아니라.. k를 빼줘야하는 이유는 뭘까..? 5 1 76543 의 예시를 생각해보자. k가 0보다 크고 dq도 비어..

문제 https://www.acmicpc.net/problem/7983 풀이 그리디 문제.. 처음엔 배열을 만들어서 배열에 해당 날짜에 체크를 하고.. 체크가 안된부분이 나온 처음 인덱스로 답을 정하려했는데 인덱스 오류가 났다ㅠㅠ 그래서 풀이를..보고... 풀어보았다. time>=end 마감일이 시작일보다 이른경우다. 쉽게 말해 이미 마감일에 다른일을 했으면 지금까지 저장된 time에서 걸리는 시간을 빼준 값을 time에 갱신해야한다.. 쉽지않네 코드 #include using namespace std; int n; vector v; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; int m = n; while (m--) { in..

문제 https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1 d[cur.second]) continue; 이 한줄 때문에 계속 25%에서 틀렸다고 했다.. cur.first!=d[cur.second]가 아니라 >로 비교해야하나보다.. 코드 #include using namespace std; int T, n, m; int pre[21]; int d[21]; vector board[21]; const int INF = 1e9 + 10; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> T; for (int tc = 1; tc > n >> m; ..

문제 https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 풀이 다시 C++로 오게된 이유는,,,, 최근 코테보는 기업들이 Python으로 시험을 못보게해서... C++은 자료형을 신경써야하는게 무척이나 귀찮다....확실히 파이썬이 편하지만 어쩌겠냐~ 이번 문제를 통해 다익스트라를 다시 한 번 공부했다. 개인적으로 다익스트라 너무 어렵지만.. 외우면 되니까 자주 풀어야겠다. 이번엔 역방향 그래프..