기술 블로그

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가 있을 것이고, 입력시..

https://www.acmicpc.net/problem/3197 # 시간 초과 # 복습 # bfs # 이분 탐색 # 생각 # 아이디어 # queue # 팁 tip 깨달은 점 : 행과 열이 100 이상이면 퍼져나가는 시점을 기록하는 방법을 써보자. 얼음을 한 번 녹일 때마다, bfs로 탐색해서 검사하는 것은 시간 초과가 발생한다. 그래서 시간을 줄이려면 queue를 여러 개 사용해서 구현하거나 약간의 아이디어가 필요하다. 우선 내 코드에서의 핵심은 Map[행][열] 배열이다. 1. 우선 'L'이나 '.'를 melt_queue에 push하여, 최대로 얼음을 녹이는 시점을 구한다.(모든 얼음이 다 녹는 시점)2. 위에서 최대 시점을 구할 때, Map[행][열] 배열에 각 위치에 맞는 얼음이 녹이는 시점을 기..

https://www.acmicpc.net/problem/16957 # 시간초과 # 복습 # 구현 # 생각 # 아이디어 # 유니온 # 파인드 # Find # 경로 # 압축 # Union 처음 구현했을 때, 시간 초과가 발생했다. 이 문제의 핵심은 경로 압축(Path Compression)이다. 간단하게 말하자면, 30에서 계속 최솟값을 통해 가다가 2로 도착하였다면, 또 다른 숫자인 50에서 출발하여 최솟값을 통해 계속 진행하다가 30을 만나면 더이상 진행할 필요가 없다는 뜻이다. 즉, 30에서 이미 2로 도착하였기 때문이다. 이 문제는 Union-Find에서 Find를 활용하는 문제이다. 예제 1로 설명을 하겠다. 우선 예제 1을 1 3 45 6 78 9 2 이렇게 접근하지 말고, 아래와 같이 접근을 ..

https://www.acmicpc.net/problem/18511 복습 코테 백트래킹 dfs backtracking 추천 필수 코딩 처음에 dfs 구현할 때 숫자 비교를 string으로(stoi()) 하려다가 생각해보니 num과 ten 변수를 활용하여 n과 비교할 숫자를 만들 수 있었다. num = 0, ten = 1로 시작하면 n과 비교할 숫자를 만들 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738#include using namespace std; int n, k, ans;vector v; void dfs(int num, int ten){ if (num > n) { return; } ans = max(ans, num..

https://www.acmicpc.net/problem/16958 다익스트라 : https://hsdevelopment.tistory.com/389 # jh05013 # 복습 # 구현 # 생각 # 필수 # 아이디어 # 맨하탄 # 맨하튼 # 거리복습 필수 다익스트라 플로이드 코테 코딩 추천 bfs로 풀려다가, visit 방문 처리가 복잡할 것 같아서 다익스트라로 풀었다. vector p하고 우선순위 큐인 pq의 first, next 구분을 잘 하자. 또한, 무작정 텔레포트 시간을 넣는 것이 아니라 실질적인 거리와의 비교를 통해 더 작은 것을 넣어야 한다. 그런데, 다익스트라로 푸니 시간이 무려 1132ms나 걸렸다. 플로이드 와샬도 868ms나 걸렸다. 하지만 채점 현황을 보니 0ms 코드도 있었다. 더..