Realuda의 블로그

https://school.programmers.co.kr/learn/courses/30/lessons/12984 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr Lv4인가? 싶을정도로 아이디어는 쉬웠지만 효율성 테스트에서 벽을 느끼고 말았다. 문제 자체는 이분 탐색으로 쉽게 풀 수 있다. 임의의 높이 h에서 지형 편집 비용을 그래프로 나타낸다면 위와 같을 것이다. 꼭 이런 형태가 아닐수도 있지만, 대충 이런 형태다. 여기서 임의의 높이 h를 정한다. 해당 위치에서 그래프의 기울기를 구한다. 만약 기울기가 양수라면, 즉 비용이 높아지고 있다면, h를 왼쪽으로 움직인다. 만약 기울기가 음수라면, 즉 비용이 낮..

https://school.programmers.co.kr/learn/courses/30/lessons/118669?language=csharp 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 아우... 다익스트라를 변형해서 풀 수 있었다. 문제에서 뭐 복잡하게 설명을 했지만, 굳이 등산로를 왕복할 필요는 없고 gate에서 summit으로 가는 임의의 경로들 중에서 intensity가 최소인 경로를 찾으면 된다. 일반적인 다익스트라 알고리즘은 출발지에서 다른 정점들까지의 최소 비용을 구할 수 있다. 이 문제에서는 출발지에서 다른 정점들까지의 최소 비용을 구하는 대신 최소 intensity를 구해주면 된다. ..

https://school.programmers.co.kr/learn/courses/30/lessons/42893 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 정규식을 적극적으로 활용해서 문제를 풀었다. 평소에 문자열 다루는걸 싫어해서 피해왔는데, 이정도로 문자열을 다루기는 처음인 것 같다. javascript의 정규식을 이용해서 비교적 간단하게 풀었지만, 만약 c나 c++이나 c#으로 풀었다면 어떻게 했을지 상상만 해도 끔찍하다. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/RegExp RegExp - Ja..

https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 다익스트라 알고리즘으로 풀 수 있었다.다만 경주로 부지 한칸에도 4가지 경주로가 들어설 수 있기 때문에, N*N*4 만큼의 배열이 필요했다. 똑같은 경주로 부지라도, 상하좌우 네 방향에서 이어지는 도로가 건설 될 수 있기 때문이다. 먼저 부지에 건설될 도로의 비용을 기록할 cost 삼중배열을 준비한다.cost[0][0]을 초기화해준다. cost[0][0]은 네 방향 모두에서 비용이 0이다. 다익스트라 알고리즘을 수행하기 위한 큐를 준비한다.도로의 비용을..

https://school.programmers.co.kr/learn/courses/30/lessons/60062?language=javascript 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 오랜만에 코딩 문제를 풀었다. 길이가 n인 원형 리스트로 주어진 외벽에서 최대 10군데의 약점이 주어진다. 한번에 d만큼의 길이를 커버할 수 있는 친구들의 목록 dist가 주어질 때, 친구들을 최소한으로 사용해서 모든 약점을 커버해야한다. 기본적으로 백트래킹 방식으로 풀 수 있다고 판단했다. 주어진 n, weak, dist에서 한명의 친구를 배치하는 백트래킹 함수 foo를 정의한다. foo는 dist에서 친구를 한..

https://school.programmers.co.kr/learn/courses/30/lessons/118670 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr은근히 어려운 문제였다.핵심 아이디어를 떠올리지 못하면 효율성 테스트를 통과하지 못할 것 같다. 정확도 테스트만 있었다면 단순하게 모든 원소를 일일이 이동하도록 구현해도 통과할 수 있었을 것이다. 그러나 효율성 테스트를 통과하려면 그래서는 안된다. 핵심 아이디어는 회전 명령을 수행하기 위해 행렬의 테두리만을 따로 관리하는 것이다. 행렬의 제일 왼쪽 열, 제일 오른쪽 열, 제일 윗 행, 제일 아랫 행을 각각 큐로 관리하면 회전 연산을 O(1)만에 처..

https://school.programmers.co.kr/learn/courses/30/lessons/60059?language=javascript 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 열쇠를 돌려가며 자물쇠에 끼우는 문제 n과 m의 크기가 작으므로 무식하게 풀기로 했다 자물쇠의 크기를 n*n, 열쇠의 크기를 m*m이라고 할 때, 열쇠를 1-m, 1-m부터 n, n까지 미끄러트리면서 자물쇠가 풀리는지 확인한다. 자물쇠를 푸는데 열쇠가 모두 들어갈 필요는 없기 때문이다. 따라서 먼저 두개의 for문으로 감싸준다.const n = lock.length;const m = key.length;for (l..

https://school.programmers.co.kr/learn/courses/30/lessons/77886 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문자열이 싫다 주어진 문자열 x를 앞에서부터 순회하며 "111"을 찾은 뒤, 가장 가까운 "110"과 위치를 바꾸는 방법으로 풀려고 했는데 틀렸다. 테스트 케이스는 모두 맞았고, 반례도 떠오르지 않았으나 막상 제출했을 때 모든 문제가 실패가 떴다. 그래서 다른 방법으로 풀었다. x를 한 글자씩 스택에 넣는다. 스택에 0이 들어갈 때, 스택을 3개 꺼내서 문자열이 "110"인지 확인한다. "110"의 갯수를 모두 세고, 마지막에 남은 문자열에 "110..

https://school.programmers.co.kr/learn/courses/30/lessons/49190 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀고보니 Lv5였던 문제 풀이 처음 문제를 보고 든 생각은 bfs? 하지만 인덱스의 범위가 불분명하고 심지어 음수가 될 수도 있어서 배열은 쓸 수 없다고 생각했다. 문제를 살펴보니 주어진 그림은 항상 한붓그리기이고, 선을 그리다 다른 선을 만나면 방이 하나 생긴다는 것을 직감적으로 알게 되었다. 이 점에 착안해서, arrow를 따라 선을 그리면서 새로 그린 선이 기존의 선과 만나는지 체크해주기로 했다. 그러기 위해서 간선 목록 edges가 필요했다. e..

https://school.programmers.co.kr/learn/courses/30/lessons/131703?language=csharp# 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 사실상 1행과 1열만 보면 된다. 문제에서 보여주는 예시이다. 주어진 동전을 무턱대고 뒤집기보다는, 어떤 동전을 뒤집어야하는지를 먼저 파악해두자. 동전의 시작 배치와 목표 배치의 차이만을 기록하는 2차원 불리안 배열 bool[ , ] diff를 만들어준다. diff의 각 (i, j)요소에는 beginning[i, j] == target[i, j]를 담는다. 즉, diff[i, j]가 false이면 (i, j)의 동전을..