본문 바로가기

프로그래머스 풀이/Lv 2

 (37)
프로그래머스 - 피로도 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 순서를 1 2 3, 2 1 3, 3 1 2 등 어떤식으로 진행해야할지 정하는 문제. 그리디하게 생각할 수 없고 모든 것을 해보는 것이 정답인 경우이다. 겨우 N이 8까지 밖에 없는 경우라서 가능하지만 숫자가 더 커지면 다른 방법을 찾아야한다. 이 문제는 dfs로 순열을 만드는 문제와 유사하다. dfs로 순열 조합을 다룰 줄 알아야한다. #include #include #include using n..
프로그래머스 - 행렬의 곱셈 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/12949 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 행렬의 곱셈은 DP를 사용해서 최적화 할 수도 있다. 물론 이건 2개만곱하는 거니까 이런것 까지는 필요 없지만 DP포함이 되었다면 레벨 2가 아니겠지. 행렬의 곱셈을 할 때, answer[a][d] = A[a][b] * B[c][d] 에서 b = c 임을 눈치챈다면 쉽게 풀 수 있다. 이런 규칙을 찾는 문제는 손으로 써서 관찰하는 것이 규칙을 찾기 편하다. 물론 머리가 좋으면 바로 눈치챌 수도 있..
프로그래머스 - [1차]캐시 LRU가 무엇인지 알아야 풀 수 있는 문제다. 컴퓨터구조, 운영체제, 데이터베이스 등 필수 과목에서 한번씩 나오는 개념인데 가장 사용한 지 오래된 것을 캐시에서 빼내겠다는 뜻이다. 캐시는 매우 유용하지만 너무 커지면 오히려 느려지고 무엇보다 비용이 많이든다. 예를들어, 캐시의 크기가 3이고 캐시에 A B C 순서로 들어왔다고 하자, 그리고 D가 들어왔다. -> 가장 사용한지 오래된(들어온지 오래된) A가 빠지고 B C D 형태가 될 것이다. 그런데 D가 아니라 A가 들어왔다면, 캐시 히트로 캐시에는 변화없다. 그 다음 D가 들어왔다면? -> A는 들어온지 가장 오래되었지만 방금 캐시 히트로 썼기 때문에 사용한지 가장 오래됐고 사용한적 없는 B가 빠진다. 그러므로 A C D 형태가 된다. 이 알고리즘을 작..
프로그래머스 - 카카오 프렌즈 컬러링북(C++) 기본적인 그래프 탐색 문제이다. 각 좌표에서 그래프 탐색 후 방문체크를 한다. bfs를 해도되지만 각 타일에서 다음 타일과 비교해야하는 부분도 있으니 dfs로 풀이했다. 그러나 bfs로 풀이해도 문제없다. 유사한 문제 - https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net #include using namespace std; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int M; int N; int ar..
프로그래머스 - N개의 최소공배수(C++) https://tigerfrom2.tistory.com/70 유클리드 호제법(Euclidean algorithm) - 최대공약수, 최소공배수 알고리즘 최대공약수는 암호학에도 자주쓰이고 알고리즘 문제를 풀 때도 자주 등장합니다. 우리가 초등학교 때 배웠던 최대공약수 구하는 법은 ex) 4 8 이라 하면 두 수가 공통으로 나누어질 것 같은 수를 tigerfrom2.tistory.com 이 글을 참고! 어차피 몇개가 들어오던 (1,2,3,4) 라고 하면 1, 2의 최소공배수 a, a와 3의 최소공배수 b, b와 4 의 최소 공배수 c 라고 순차적으로 구해나가면 그게 정답이다. 수학적 증명은 하지않았지만 뭐 맞았다. #include #include using namespace std; int gcd(int a,..
프로그래머스 - 삼각 달팽이(c++) 처음보면 되게 난해할 수 있는 문제이다. 방법이 있긴한가 싶었다. 처음 생각한 풀이는 DP였다. 그러나 DP는 최적의 값을 찾는 것인데 단순 배열 채우기가 DP?는 아닐거라 생각했다. 그다음은 dfs였는데 하삼각행렬만 가능하다고 치고 방향을 계속 바꿔주면 될 것 같았다. 이런 식으로 계속 규칙이 있음을 알 수 있다. 어차피 방향은 3가지뿐이라 재귀만 잘 따지면 가능할 것 같았다. dir 이라는 방향을 저장해두는 변수를 하나 만들고 dir = 0 이면 아래방향 dir = 1 이면 오른쪽 dir = 2 이면 왼쪽 대각선 으로 이동하게 만들고 각 방향마다 몇번 이동해야하는지 정해두었다. 그런데 그림으론 저렇지만 코딩을하고나니 첫번째때 0,0 에서 시작하니까 첫 아래방향에 cnt = n - 1 이 되는 것을 알..
프로그래머스 - 마법의 엘리베이터(C++) 처음 문제를 읽고 바로 BFS구나! 싶어서 bfs로 코딩했다. 얼마 전 워딩이 거의 비슷한 문제를 만났어서 더욱 그랬다(아래 첨부) 그러나 시간초과에 틀렸습니다가 무더기로 나왔다. 잘 읽어보니 저 위의 100까지의 숫자 외에도 1000 10000까지도 나갈 수 있는 것이었다. 그래서 주어진 숫자의 자릿수까지만 bfs 할 수 있도록 했는데도 38점 밖에 받지 못했다. 너무도 당연하게 bfs가 맞다고 생각하고 있어서 내 코드가 어디가 잘못된 건지 갈피를 못잡고 있었다. 이 풀이가 잘못된건가? 라고 생각했을 땐 이미 늦었다. 이것과 비슷한 문제를 풀어본적이 있는데도 풀이를 바로 떠올리지 못한 것이 참 아쉽다. 아직까지도 시간복잡도 계산을 잘 못하는 것이 컸다. 시간복잡도를 통해 bfs가 불가함을 바로 알아챘어..
프로그래머스 - 짝지어 제거하기(C++) 문제 설명 처럼 2개 짝짓고 제거하면 시간초과로 풀 수 없다. 첫 풀이는 다음과 같았다. 먼저 abcc 이런식으로 a, b가 홀수개이면 절대 문장은 제거되지 않는다. 그렇기 때문에 먼저 원소들의 개수를 세는 작업을 했고 이 작업을 통과하였을 때 제거 연산을 해봤다. 그러나 별짓을 다 해도 저 3개의 효율 테스트를 통과할 수가 없었다... 결국 아이디어를 구하기 위해 질문하기를 보았는데 답은 "스택" 이었다. 최대 크기가 100만일 때 부터 알아봤어야하는데 나는 아직 멀었다. 85점까진 받았기 때문에 코테나 대회였다면 바로 넘겼을 문제이기는 하다. 스택을 사용한다. ex) dcaabbcd 가 들어왔을 때 1. d를 꺼내 c와 비교한다. 둘은 다르다! 그러므로 꺼낸 d를 또다른 서브 스택에 넣어둔다 . 현재..

티스토리툴바