코딩테스트43

• 

  [삼성 SW] 테트로미노 14500번: 테트로미노 (acmicpc.net)문제 풀이는 유튜브 영상을 참고하였다. 1) 완전 탐색테트로미노가 될 수 있는 모든 경우를 모두 탐색하여 합을 갱신한다. 시간 복잡도는 최대 500 * 500 * 5(테트로미노 가짓수) * 4(회전) * 4(대칭) = 25 * 10^6 정도라 완전탐색을 진행해도 시간복잡도가 넘지 않는다.import sysN, M = map(int, input().split())arr = [list(map(int, input().split())) for _ in range(N)]# 가능한 모든 패턴의 회전/대칭 좌표를 저장한다.tet = [[(0, 1), (0, 2), (0,3)], [(1, 0), (2, 0), (3, 0)], # | (회전) [(0, 1), (1, .. 코딩테스트 2024. 8. 8.

• [카카오] 추석 트래픽 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 날짜와 시간 정보가 있는 요청시간에 따라 초당 처리량의 최대값을 구하는 문제다. 시간만 주어졌다면 단순히 시간을 초로 변환해 구했겠지만 날짜 정보까지 들어와 계산하고 비교하는 게 까다로워 datetime 모듈을 사용했다. 문제에서 9월 15일 하루의 로그 데이터를 분석한다고 했으므로 시간만 비교해도 된다 ㅎㅎ 그래도 날짜가 나올 수 있으니 datetime모듈을 사용해서 비교하겠다. datetime 모듈에서 특히 주목해야할 메써드는 두 가지다. datetime.timedeltadatetime/date 인스턴스 간의.. 코딩테스트 2024. 6. 18.

• 

  [카카오] 외벽점검 https://youtu.be/yYc2KiCSIoA?si=UY_QFNsKxskUUjiE 해당 영상을 참고하여 포스팅했습니다! 동그란 모양의 외벽에 취약한 지점이 있다. 취약 지점을 점검하기 위해 친구들을 보내는데, 이때 점검 시간은 1시간이며 친구들 제각각 1시간동안 이동하며 점검할 수 있는 거리가 있으며 친구를 최대한 적게 보내야 하는 것이 문제의 관건이다. 주목해야할 것은,1. 외벽이 원형이라 취약지점 간 거리를 구할 때 외벽 길이를 두 배로 늘려서 확인을 편리하게 하는 것2. 어떤 취약지점을 우선 방문하느냐, 어떤 친구를 먼저 보내느냐에 따라 보내는 친구 수를 달리할 수 있다는 것3. 친구를 보내 취약지점을 방문할 때 점검 가능한 거리를 벗어날 때 해당 지점은 방문할 수 없다는 것.(+ 추가로 시계.. 코딩테스트 2024. 6. 11.

• [dp] 도둑질 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 연속된 두 집을 선택하지 않으면서 합의 최대를 구하는 것이 관건인 문제다. 현재 훔쳐야할 집이 i번째 집이라면 i번째 집을 훔칠지 말지 경우를 나눠 dp를 구할 수 있다. i번째집을 훔칠 수 있는 경우는 i - 1번째 집을 훔치지 않았을 경우이며 이를 식으로 나타내면, dp[i] = max(dp[i - 2] + money[i], dp[i - 1]) 로 나타낼 수 있다 이때 dp는 선형일 경우로 진행하기 때문에 원형인 구조인 지금 상황에서는 첫번째 집을 훔쳤는지 안 훔쳤는지에 따라서 두 번 경우를 나눠 최대값을.. 코딩테스트 2024. 4. 16.

• 

  [해시] 베스트 앨범 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr c++ 문법이 익숙하지 않으면 엄청 해맬 수 있는 문제.... 장르별로 재생 횟수의 합과, 해당 장르의 목록들 각각 정렬하는 문제라 좀 헷갈려서 오래 걸렸다.. 장르 별로 재생 횟수의 합으로 정렬된 배열과, 해당 장르의 목록을 정렬한 배열이 필요하다 hashmap으로 들어가기 때문에 정렬 시 vector의 도움이 꼭 필요하다는 점..... 명심하자ㅠ 그리고 재생횟수가 같을 경우 더 작은 값을 return해줘야 한다는 것도 꼬옥 기억..~ #include #include #include #include usin.. 코딩테스트 2024. 4. 1.

• [SQL] 오프라인/온라인 판매 데이터 통합하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 각 물건(product_id)마다 판매량을 합해야 하는 줄 알고 outer join 을 하기 위해 삽질 깨나 했던 문제다. 물건은 온라인, 오프라인 둘 다 있을 수 있고 하나만 있을 수도 있다. 하지만 판매량을 합하지 않는 이상(ㅎㅎ;;) 굳이 join을 하지 않고 두 물건 중 하나만 체크하면 되기에 join이 아닌 union 연산이 필요하다. 이때 오프라인은 user_id가 없으므로 null값으로 대체해 추가해야하는 것을 잊지 말자~ (select date_format(off.SALES_DATE, "%Y-%.. 코딩테스트 2024. 3. 31.

• 

  [힙] 이중우선순위큐 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 우선 순위 큐를 이용해서 주어진 연산을 하는 문제 연산은 더하기 빼기가 있으며, 덧셈은 경우 없이 더해주면 되고, 뺄셈의 경우 최댓값을 빼는 경우와 최솟값을 빼는 경우를 생각해주면 된다. 최댓값을 꺼낼 때와 최솟값을 꺼낼 때 이중 우선순위 두 개를 사용해서 연산을 해주면 되는데, 이때 최댓값을 빼는 경우(pop) 최솟값은 빼지 않기 때문에 이미 pop한 숫자를 다시 한번 pop할 경우가 있다. 따라서 이 경우 몇 개의 숫자가 남아 있는지 count를 해주어야 한다. 빼기 연산을 할 때 카운트가 0만 아니라면 .. 코딩테스트 2024. 3. 31.

• [SQL] 대장균들의 자식의 수 구하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr SELFT JOIN으로 푸는 문제다. JOIN말고 냅다 그냥 두 테이블을 엮어서 헤맸는데 SLEFT 조인을 통해 부모 ID를 기준으로 LEFT JOIN을 해서 COUNT를 해주면 된다! select p.id, count(c.parent_id) as CHILD_COUNT from ECOLI_DATA p left join ECOLI_DATA c on c.parent_id = p.id group by p.id; 코딩테스트 2024. 3. 28.

• [그래프] 가장 먼 노드 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 인접 노드로 그래프를 구하고 BFS로 최단 거리의 노드의 개수를 구하는 문제다. 자칫하다가 DFS풀 여지도 있는데 DFS로 풀게 되면 최대한 깊이 우선 도달하기 때문에 최단 경로가 나오지 않는다. BFS를 진행하면서 이전 경로의 값을 더해주면서 해당 노드까지 걸리는 거리를 구하고, 다 구했다면 MAX값을 구해 RETURN을 해주면 된다. 이때 주의할 점은 VECTOR를 인자로 넘겨줄 때 주소값을 넘겨줘야한다는 것이다. 아무 생각 없이 벡터 그대로 넘겨줬다가 계속 답이 틀리길래 ㅠㅠ 거의 한 시간은 헤맨 것 같.. 코딩테스트 2024. 3. 28.

• [그리디] 조이스틱 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그리디라기엔 구현 문제 같았던 문제ㅜㅜ 조이스틱을 최소한으로 움직이며 원하는 글자를 만들어야 하는 문제다. 위 아래 방향의 경우 가운데 문제인 M을 기준으로 아래 방향을 할지 윗방향을 할지 횟수를 구할 수 있다. 이때 아스키 코드의 차이로 구할 수 있다. M보다 클 경우 아래 방향으로 가는 것이 효율적이므로 'Z'에서 값을 빼준 뒤 1(A에서 Z로 가는 횟수)을 더해주고, M보다 작을 경우 A에서 값을 빼주면 된다. 관건은 좌우 방향이다. 단순히 n - 1을 하는 게 아니라 A가 나올 경우 왼쪽 방향을 가는게.. 코딩테스트 2024. 3. 27.

• [SQL] 상품 별 오프라인 매출 구하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr SELECT PRODUCT_CODE, SUM(PRICE * SALES_AMOUNT) AS SALES FROM OFFLINE_SALE off INNER JOIN PRODUCT pro ON off.PRODUCT_ID = pro.PRODUCT_ID GROUP BY off.PRODUCT_ID ORDER BY SUM(PRICE * SALES_AMOUNT) DESC, pro.PRODUCT_CODE; 코딩테스트 2024. 3. 23.

• 

  [이분탐색] 징검다리 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이분탐색문제다. 뭘 어떻게 비교해야 하는지 헷갈려서 감이 안 올 수도 있는데 기준만 명확히 잡으면 금방(????) 풀 수도 있는 문제다. 우선 이분탐색의 범위는 바위 사이의 거리의 최소값이다. 바위 사이의 거리의 최소값 middle을 기준으로 middle보다 거리가 작으면(최소값보다 작으면 안 되니까!!) 제거할 바위의 개수를 늘려준다. 이때 주의할 점은 다음에 비교할 바위를 이전에 제거한 바위의 거리와 합해서 생각해야 한다!!! 처음으로 2를 제거해보자 2를 제거했으므로 다음 순서는 11이다. 하지만 2가 .. 코딩테스트 2024. 3. 23.