프로그래머스 풀이/Lv 2 (30) 썸네일형 리스트형 프로그래머스 - 거리두기 확인하기 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근법 - 처음 봤을 때는 bfs 한번으로 해결하기 위해 고민했으나 각 P 별로 bfs를 돌아도 N이 워낙 작아서 시간초과가 나지 않는 문제이다. 플로이드-워셜도 생각이 났는데 플로이드 워셜은 행렬에서 사용해본적이 없고 간선의 비용이 주어지면 행렬로 표현하는 것이라 결이 다르다고 생각이 된다. 각 대기실은 5x5크기이기 때문에 bfs의 시간복잡도는 25이고, 모든 칸에 P가 존재하는 경우의 수를 .. 프로그래머스 - 피로도 (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가 불가함을 바로 알아챘어.. 이전 1 2 3 4 다음
