🔅코딩테스트 공부🔅213 [프로그래머스] Level2 예상 대진표(python) https://school.programmers.co.kr/learn/courses/30/lessons/12985 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 해결 방법 1. 오답이 난 풀이 두 수의 차가 1인 경우 cnt를 return 해주는 방식으로 문제를 풀었는데 많은 문제에서 실패가 떠서 고민을 해봤다. A => 2번 / B => 3번일 경우 두 수의 차는 1이지만 round가 같지 않아 발생하는 경우의 반례가 생긴다는 것을 깨닫고, abs(A-B) ==1 or A//2 != B//2 => 두 수의 차는 1이고, 두 수를 2로 나눈 몫.. 2023. 3. 5. [백준] 1005번 ACM Craft(python) https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 1. 난이도 골드 3 2. 문제 해결 방법 건물을 짓는 순서가 정해져 있으며, 가장 빨리 지을 때까지의 최소시간을 알아내야한다. 따라서 순서가 정해져 있는 작업을 차례대로 수행할 때 사용되는 알고리즘인 위상정렬을 이용해 문제를 해결했다. value라는 새로운 list를 만들고, value에는 그 건물을 짓기 위한 시간을 누적해 저장한다. value 가 0인 경우는 아직 시간 측정이 안 된 건.. 2023. 3. 4. [백준] 21921번 블로그(python) https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 1. 난이도 실버 3 2. 문제 해결 방법 넓이 구간이 고정되어 있으면 슬라이딩 윈도우를 이용하고, 유동적이면 투 포인터를 이용하면 된다. 처음에 sum 함수를 while문 속에 넣어서 문제를 풀었는데 O(N^2)가 되어 시간초과가 발생했다. (sum함수의 시간복잡도는 O(N)) 두 번째로는 투 포인터 방식을 이용했는데, 구간이 유동적이지 않아 굳이 이 방법을 사용할 필요가 없다는 걸 깨달.. 2023. 3. 3. [백준] 1940번 주몽(python) https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 1. 난이도 실버 4 2. 문제 해결 방법 투 포인터를 이용하면 된다. 데이터의 크기가 작기 때문에 sort를 이용해 정렬한 후, start + end 의 값이 m과 같을 경우 카운팅해줬다. 3. 내가 작성한 코드 n = int(input()) #재료의 개수 m = int(input()) #번호 합 material = list(map(int, input().split()).. 2023. 3. 3. [백준] 2018 수들의 합(python) https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 1. 난이도 실버5 (🥈) 2. 문제 해결 방법 투 포인터를 이용해 문제를 해결했다. 투 포인터란 list를 순차적으로 접근할 때 start 와 end라는 두 점으로 각각 기록하는 알고리즘이다. 3. 내가 작성한 코드 Version1 n = int(input()) num = [i for i in range(1,n+1)] interval_sum = 0 cnt = 0 end = .. 2023. 3. 3. [프로그래머스] Level2 귤 고르기(python) https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 해결 방법 1. Counter 를 이용해 key 와 value 값을 구한다. (=> 귤의 크기에 따른 개수가 카운팅된다.) 2. list명.values() 를 출력하면 오름차순 정렬되기 때문에 reverse = True 로 내림차순 정렬한다. 3. 각 value 값을 하나씩 뽑으며 k보다 크거나 같으면 cnt 를 return 시키고, k보다 작으면 cnt를 1 증가시킨다. 2. 내가 .. 2023. 3. 3. [백준] 14567번 선수과목(python) https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 1. 난이도 골드5 (🥇) 위상정렬을 이용해 문제를 풀었다. 위상정렬은 위 문제와 같이, 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다. 2. 내가 작성한 코드 import sys from collections import deque input = sys.stdin.readline n,m = map(int, input().rstrip().split()) #n = 과목수 m = 선수 조건수 indegree = [0] .. 2023. 3. 3. [알고리즘] 위상정렬 + 문제풀이 위상 정렬 => O(V+E) 순서가 정해져 있는 작업을 차례대로 수행할 때 사용되는 알고리즘 (방향그래프) 진입차수(indegree) : 노드로 들어오는 간선의 개수 진입차수가 0인 것을 queue에 넣고 그 노드에서 출발하는 간선 삭제 queue가 빌 때까지 반복 코드 from collections import deque v,e = map(int, input().split()) # v 노드 e 간선 indegree = [0] * (v+1) # 진입차수의 정보 graph = [[] for i in range(v+1)] for _ in range(e): a,b = map(int, input().split()) graph[a].append(b) indegree[b] += 1 def topology_sort(.. 2023. 3. 2. [백준] 1197번 최소 스패닝 트리(python) https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 1. 난이도 골드4 (🥇) import sys input = sys.stdin.readline v,e = map(int, input().rstrip().split()) #v정점 e간선 parent = [i for i in range(v+1)] edges = [] result = 0 def find(x): if parent[x] != x: parent[.. 2023. 3. 2. 이전 1 ··· 3 4 5 6 7 8 9 ··· 24 다음
