본문 바로가기

프로그래머스 풀이

 (90)
프로그래머스 - 자동차 평균 대여 시간 구하기 https://school.programmers.co.kr/learn/courses/30/lessons/157342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr SQL 문제는 가끔 기업 코딩테스트에서도 출제되고 실제로 백엔드 개발자라면 쿼리 작성할 일이 반드시 생기기 때문에 공부하기로 했다. * 주요 날짜 관련 함수 * DATE_ADD() : 날짜, 시간 더하기 DATE_SUB() : 날짜, 시간 빼기 DATEDIFF() : 두 기간 사이의 일수 계산 TIMEDIFF() : 두 기간 사이의 시간 계산 PERIOD_DIFF() : 두 기간 사이의 개월 수..
프로그래머스 - 단어 변환 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dfs/bfs 문제라는 것을 확인했기 때문에 쉽게 풀 수 있었다. 난 bfs방식을 택했다. 중요한 것은 하나의 단어에 도달하면 다른 단어들은 이 단어에 도달할 수 있어도 할 필요가 없음을 인지해야한다. 만약 지금 이 단어에 도달했는데, 다음으로 이 단어에 도달한다는 것은 결국 최단거리가 아니라는 의미이기 때문이다. 그러므로 방문표시를 하고 bfs 탐색을 하면 문제는 풀린다. 이 문제가 레벨3인 이..
프로그래머스 - 경주로 건설 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/67259# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 다익스트라를 응용하면 될 것이라 생각했다. DP배열을 만들고 계속 갱신해나가며 최적의 길을 찾으면 된다고 생각했다. 그러나 다익스트라가 가능하려면 한가지 강력한 전제 조건이 필요하다. 지금 dp값 보다 큰 값은 절대로 다시 체크하지 않아도 된다. 무슨말이냐면 지금 dp[2][2] = 30 이라하였을 때, 순회하다가 다시 dp[2][2]를 만났을 때 현재 값이 31이라면 가지 않겠다는 의미이다. ..
프로그래머스 - [1차]뉴스 클러스터링 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/17677 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근법 - 우선 소문자와 대문자를 구분하지 않으므로 모두 소문자 혹은 대문자로 바꿔줘야한다. 그리고 합집합과 교집합을 구하면되는 간단한 문제인데 은근히 조건에 맞는 문자열을 구성하는 구현 실력을 요구했고 기본적인 집합 공식인 A + B - A n B = A U B 를 알고있어야했다. 처음 접근했을 땐 set 자료구조에 모두 박아놓으면 합집합이 될 것이라 생각했으나 1 2 2 3 2 2 3 이라하면..
프로그래머스 - 거리두기 확인하기 (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 임을 눈치챈다면 쉽게 풀 수 있다. 이런 규칙을 찾는 문제는 손으로 써서 관찰하는 것이 규칙을 찾기 편하다. 물론 머리가 좋으면 바로 눈치챌 수도 있..
프로그래머스 - 다단계 칫솔(C++) https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 백엔드 직무 데브 매칭 기출 문제이다. 트리를 자식부터 반대로 타고 탐색해야하기 때문에 부모가 자식의 정보를 갖고 있게 하지 않고 자식이 부모의 정보를 갖고 있도록 해야한다. 그리고 각 노드의 이름이 문자열이기 때문에 문자열을 숫자로 변환하여 map으로 관리해주었다. 1. 문제 조건 - 돈을 번 노드부터 시작하여 그 노드의 최상단 부모까지 타고 올라가야한다. - 그러면서 번 돈을 분배하는 작업을 ..

티스토리툴바