목록분류 전체보기 (365)
백준 - 소수의 연속합(1644)
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 기본기가 중요한 문제였다. 뭔가 기업코테에 출제할만한 문제라고 생각한다. 에라토스테네스의 체로 소수의 수열을 구해주었다. 그 후 투포인터로 수열의 합을 구했다. 수열의 합을 구할때는 시간을 더 아끼기 위해 누적합을 이용했다. q가 오른쪽 포인터 p가 왼쪽포인터로 구간을 나타낼 수가 있으며 q가 올라가면 더해주고 p가올라가면 원래 자리에 있던 수를 빼준다. #include #include #include using namespace std; int main() { int n; cin >> n; if (n == 1) {..
백준 - K번째 최단경로 찾기
https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 $n$, $m$, $k$가 주어진다. ($1 ≤ n ≤ 1\,000$, $0 ≤ m ≤ 2\,000\,000$, $1 ≤ k ≤ 100$) $n$과 $m$은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이 www.acmicpc.net c++복습할 겸 풀어보았다. 당분간 c++로 풀 것 같다. 다익스트라를 변형해서 푸는 문제이다. 지속적으로 최단거리를 가져와 최신화를 하는 게 정석이지만 이번에는 거리 데이터를 끝까지 가져가며 관리를 해준다. 정석 다익스트라는 거리 조건문을 통해 큐에 넣었으나 이번에는 k를 이용해서 다익스트라를 진행하게 했다. #inc..
프로그래머스 - 상담원 인원
https://school.programmers.co.kr/learn/courses/30/lessons/214288 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2023 현대모비스 알고리즘 경진대회 예선 문제 푸는데 하루를 썼다. 첫 구상은 상담원 배치를 재귀로 돌려 완전탐색 했다. 근데 시간 초과가 나서 product로 구했다. 각 상담원 배치 수를 이용해 계산을 진행한다. 1번 예제로 설명하면 (1, 1, 1) (1, 1, 2) (1, 1, 3) (1, 2, 1) (1, 2, 2) (1, 2, 3) (1, 3, 1) (1, 3, 2) (1, 3, 3..
프로그래머스 - 산 모양 타일링
https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2024 KAKAO WINTER INTERNSHIP 문제 타일링 문제는 항상 피보나치와 비슷하게 풀었던 경험이 있었다. 이번에도 몇 가지 테스트케이스를 만들어 수들의 연관성을 찾을 수 있었다. [0] = 3 [1] = 4 [0, 0] = 8 [0, 1] = 11 [1, 1] = 15 [0, 0, 0] = 21 도출한 테스트케이스만으로는 유추하기 힘들어 규칙성도 파악하기로 했다. 해당 사진을 예시..
프로그래머스 - n + 1 카드게임
https://school.programmers.co.kr/learn/courses/30/lessons/258707 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2024 KAKAO WINTER INTERNSHIP 문제 1. 나의 덱에 있는 요소들로 라운드 진출 가능한 경우 2. 나의 덱 하나와 coin 하나 써서 라운드 진출 가능한 경우 3. coin 두 개 써서 라운드 진출 가능한 경우 4. 모두 통과 못하면 최대 라운드이다. 라운드마다 두장의 카드는 바로 temp_card에 넣어두고 필요할 때 coin을 쓰고 temp_card에서 빼가기로 했다. s..
프로그래머스 - 주사위 고르기
https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2024 KAKAO WINTER INTERNSHIP 문제 처음 풀 때 각 원소들을 반복문으로 돌려 다른 원소를 이길 수 있는지 판단하여 count 개수를 세고 주사위별로 count를 합쳐 비교하려 했으나 테스트케이스 7개를 통과하지 못했다. 그래서 product를 이용하여 여러 리스트의 조합을 구하고 이진트리로 이길 수 있는 원소들의 개수에 대해 파악했다. [[1, 2, 3, 4, 5, 6], ..
프로그래머스 - 도넛과 막대 그래프
https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2024 KAKAO WINTER INTERNSHIP 카카오 문제 새로 올라와서 풀어보았다. 정점의 번호를 찾는 방법과 그래프들의 규칙을 찾는 게 중요하다고 생각했다. 정점의 번호(4)를 보면 간선이 나가는거 밖에 없다. 나가는 간선이 제일 많은 노드가 정점의 번호이다. 4번 노드 보면 나가는 간선이 제일 많다. 얘가 정점 노드이다. 그리고 4번 노드에 연결된 노드 [8,2,11]이 어떤 그래프들..
백준 - ACM Craft (1005)
위상 정렬로 풀 수 있다. 여기에 dp까지 추가했다. indegree가 2개 이상인 노드를 생각해 보면 이미 값이 들어가 있는 경우 다시 한번 비교해 주어야 한다. dp[k] = max(dp[k], dp[pop_data] + cost[k]) 시작점에서 cost를 더한 것과 원래 목적지의 dp 값을 비교해서 높은 것으로 최신화 import heapq def main(): n = int(input()) for _ in range(n): v ,e = map(int, input().split()) cost = [0]+list(map(int, input().split())) graph = {i : [] for i in range(1,v+1)} indegree = [0]*(v+1) for _ in range(e):..