주제무 다시 봐도 핵심만 보이게끔!

무방향 그래프와 서로소 집합 서로소 집합의 필요성을 이해하기 위해서 아래 문제를 읽어보자. https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제를 읽어보면 진실을 알고 있는 사람이 포함된 파티와 포함되지 않은 파티로 나누고 싶을 것이다. 바이러스가 전염되는 것처럼 진실을 알고 있는 사람이 포함된 파티(그래프)는 모두 진실을 알게 된다. 하지만 단절된 그래프는 전염되지 않기도 하다. 위와 같은 상황에서 서로소 집합의 개념을 적용할 수 있다. 서로 다른 파티..

코테 연습 기타 첫 번째 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net import sys input = lambda: sys.stdin.readline().rstrip() def multiply(b): if b == 1: return A sub_result = multiply(b//2) % C result = sub_result ** 2 return result*A if b % 2 == 1 else result A, B, C = map(int, input().split()) print(multiply(B)..

코테 연습 BFS/DFS 첫 번째 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net import sys input = lambda: sys.stdin.readline().rstrip() sys.setrecursionlimit(2001) N, M = map(int, input().split()) relation = [[] for _ in range(N)] for _ in range(M): p_1, p_2 = map(int, input().split()) relation[p_1].append(p_2) relation[p_2].append(p_1) def ..

코테 연습 다이나믹 프로그래밍 첫 번째 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net import sys input = lambda: sys.stdin.readline().rstrip() N, K = map(int, input().split()) items = sorted([list(map(int, input().split())) for _ in range(N)], revers..

코테 연습 다이나믹 프로그래밍 첫 번째 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net import sys input = lambda: sys.stdin.readline().rstrip() N = int(input()) schedule = [[0]] + [list(map(int, input().split())) for _ in range(N)] dp = [0] * (N+1) max_value = 0 for idx ..

코테 연습 다이나믹 프로그래밍 첫 번째 https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 왼쪽부터 차례대로 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 www.acmicpc.net import sys input = lambda: sys.stdin.readline().rstrip() N, K = map(int, input().split()) A = list(map(int, input().split())) dp = [False] * N dp[0] = True for idx in ra..

다이나믹 프로그래밍 문제풀이 첫 문제 https://velog.io/@0_hun/프로그래머스-코딩-테스트-공부-2022-KAKAO-TECH-INTERNSHIP-Level-3-Python 프로그래머스 - 코딩 테스트 공부 (2022 KAKAO TECH INTERNSHIP) / Level 3 / Python 코딩테스트 연습 - 코딩 테스트 공부쉽지 않은 문제였다. 풀이에 실패하여 카카오 해설을 보고 다시 문제를 풀어보았다.BFS로 풀어도 정확도 테스트는 통과 할 수 있으나 효율성 테스트를 통과하 velog.io https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개..

https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/ 2022 테크 여름인턴십 코딩테스트 해설 2022년 카카오 여름 인턴십 코딩 테스트가 지난 5월 7일에 5시간에 걸쳐 진행되었습니다. 시간이 부족하여 문제를 풀지 못하는 아쉬움이 없도록 1시간을 늘려 테스트를 진행한 것이 작년과 조금 tech.kakao.com https://school.programmers.co.kr/learn/challenges?order=recent&page=1&partIds=31236 코딩테스트 연습 | 프로그래머스 스쿨 개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력..

알고리즘 문제풀이 다이나믹 프로그래밍 스티커 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net import sys input = lambda: sys.stdin.readline().rstrip() T = int(input()) arr = [] for _ in range(T): n = int(input()) dp = [list(map(int, input().split())) for _ in range(2)] if n = N: result.extend(B[b_idx:]) break if b_idx >= ..

오늘의 알고리즘 연습 회의실 예약 문제 문제에 대한 설명 https://softeer.ai/practice/6266 Softeer - 현대자동차그룹 SW인재확보플랫폼 회사에는 N개의 회의실이 있다. 수많은 팀이 모여 토론하고 업무를 처리하기 위해서는 회의실이 필수적이다. 내부망에 아주 간단한 회의실 예약 시스템이 있지만 편의성이 매우 떨어진다. 단순 softeer.ai 풀이 N, M = map(int, input().split()) rooms = [input().rstrip() for _ in range(N)] roomToCheckAvailable = {} times = [] for start in range(9, 18+1): for end in range(18, start, -1): times.appe..