기술 블로그

https://www.acmicpc.net/problem/10800 백준 boj colorball 복습 필수 코딩테스트 코테 추천 Greedy 그리디 탐욕 탐색 배열활용 우선 내가 생각한 정답은 (집합이라고 생각하면 된다) 답 = 누적된 크기의 합 - (자신의 컬러에 맞는 크기의 합 + 자신하고 같거나 큰 크기들의 크기의 합) + 자신과 똑같은 칼라에서 자신의 크기와 같거나 그 이상의 크기들의 합 이라고 생각하였다. 계산된 식이 음수가 나오면, 0을 출력한다. 누적된 크기의 합 = sum자신의 컬러(c)에 맞는 크기의 합 = color[c]자신의 크기(s)보다 큰 크기들의 크기의 합 = clm[max_size] - clm[s - 1]자신과 똑같은 칼라에서 자신의 크기와 같거나 그 이상의 크기들의 합 = ..

https://www.acmicpc.net/problem/2589 3가지 시도를 했었다.1. 모든 'L'의 좌표를 vector에 담아 이중 for문으로 a정점에서 b점으로 가는 거리를 구하기 -> 시간 초과2. 어떤 한 정점에서 가장 멀리 떨어진 정점으로 이동하고, 그 정점에서 다시 가장 멀리 떨어진 정점과의 거리 구하기 -> 오답123454 4LLLLLWLWLLLWLWWWcs답 : 6오답 : 43. 한 정점 'L'에서 끝까지 퍼져 나가면서 최댓값 구하기 -> 정답 2번에 대한 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676..

https://www.acmicpc.net/problem/18513 boj 백준 샘터 18513 bfs 복습 실수 필수 long 자료형 그림을 잘 보면, 샘터를 기준으로 양 옆으로 하나 씩 집을 설치하면 되는 것을 알 수 있다. 이를 통해, 샘터를 기준으로 방문 처리를 하면서 1 씩 퍼져나가는 것으로 볼 때 필요한 알고리즘은 bfs임을 알 수 있다. 틀렸습니다를 받았길래 알고보니, 정답 범위가 long long이었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include using namespace std; int n, k;int d[..

https://programmers.co.kr/learn/courses/30/lessons/62050 programmers 프로그래머스 최소신장트리 mst sw역량테스트 코딩 코테 복습 구현 생각 필수java 자바 collections Collections 컬렉션 java vector sort 자바 프로그래머스 유니온 파인드 처음에 bfs로 접근하려다가, 순간 최소신장트리(mst) 문제임을 알았다.(아래의 문제를 풀었기 때문) 비슷한 문제 : https://hsdevelopment.tistory.com/416 나는 사이클 여부를 union-find를 활용하였다. 연결된 다리의 개수는 전체 정점의 개수 - 1 이어야만 한다. 참고로 Java에서 몇 개 틀렸었는데, p 배열을 초기화 할 때, 연결요소의 개수..

https://programmers.co.kr/learn/courses/30/lessons/42884 programmers 프로그래머스 우선 오름차순 정렬시켜준다. 모든 좌표를 (x, y)라고 생각하자. 2차원이 아니라 일직선 위에서 좌표를 단순히 표시하는 것임. 그 다음 나올 좌표는 (routes[i][0], routes[i][1])이다. 어차피 오름차순 정렬되어 있기 때문에 routes[i][0]은 x보다 무조건 크거나 같다.(작을 수는 없다.) 그래서 중요한 것은 그 전의 좌표(x, y)에서 y가 중요하다. y를 routes[i][0]과 비교해야한다. y < routes[i][0]일 경우에는 아예 겹치지 않으므로, 카메라를 1대 설치해야 한다.이때, y는 routes[i][1]로 갱신해야한다. 그게..

https://www.acmicpc.net/problem/15922 알고리즘 문제를 본격적으로 공부하기 시작한 단계에서 풀려고 했었던 문제로 기억한다. 당시에 너무 어려웠던 것 같아서 못 푼 기억이 있었는데 지금 다시 풀어보니 바로 풀었다. 나의 아이디어는 그 전 좌표를 [bx, by], 그 다음 좌표(이제 입력할 좌표)를 [x, y]라고 한다면 여기에서 중요한 것은 by이다. by의 위치는 3가지의 경우가 있다. 1. by x y2. x by y3. x y by 위의 3가지 경우를 잘 따져보고 구현하면 된다. 또한, 중요한 것은 by는 max(by, y)로 갱신해야 한다. by를 무조건 y로 변경하면 아래와 같은 테스트 케이스에서 15를 출력한다. 1234541 103 33 43 9cs 12345678..

https://programmers.co.kr/learn/courses/30/lessons/62049?language=cpp 프로그래머스 programmers 우선 오른쪽에서 왼쪽으로 무조건 접고 시작하므로, answer 벡터에서 가운데 값은 무조건 0임을 알 수 있다. 또한, 가운데를 기준으로 오른쪽, 왼쪽은 완벽히 포개어진다.(합쳐진다)가운데를 기준으로 종이를 폈다, 접었다 할 수 있다. 따라서, 완벽히 포개어지므로(합쳐지므로),∨∧ 의 합이 1이 되어야한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include using namespace std; vector solution(int n) ..

https://www.acmicpc.net/problem/16925 # 문자열 # find # 접두사 # 접두 # 접미사 # 접미 # prefix # suffix # 구현 # 복습 # 처리 # 필수 # 코테 처음에는 어떻게 구현할지 몰랐다. 알고보니, 문자열의 길이가 n - 1인 문자열 a, b를 활용하는 문제이다. 완성된 문자열은 1. a + b의 마지막 문자(a가 접두사, b가 접미사)2. b + a의 마지막 문자(a가 접미사, b가 접두사) 위의 2개 중 하나이다. 그리고, 처리해줘야 할 것은 접두사, 접미사 모두 해당할 때인데 이 경우에는 무조건 하나의 경우밖에 없다. 바로 어떠한 문자열 str이 이미 접두사로 사용된 경우다. abab일 경우, 접두사로 ab, 접미사로 ab가 있을 것이고, 입력시..