♟️ 알고리즘/알고리즘_백준 75

[Java][백준] 백준 환경 파일 입력 꿀팁(tip)

항상 알고리즘 문제는 파이썬으로 풀어왔는데,최근에 Java와 Java 프레임워크를 배우고 있다.익숙해지기위해 가끔 Java로 쉬운 알고리즘 쉬운 문제를 풀어보려고한다.   새로운 언어의 코테 문제를 풀려고 할때 (특히 백준) ,내가 먼저 하는 것은 텍스트 파일을 통해 입력을 자동으로 받는 것이다. 이거를 사용하고 안하고의 코드 노가다의 퀄리티가 확 달라진다 !   🤖 텍스트 파일을 통해 입력 자동화백준 문제를 풀다 보면, 해당 예제를 복사해서 붙여 넣는 경우가 많다. 근데 이게 생각보다 진짜 진짜 귀찮다... 이런 귀찮음을 텍스트 파일로 간단하게 해결 가능 하다 !! System.setIn(new FileInputStream("input.txt"));현재 Java 파일 경로에 "input.txt" 파일..

[Python][백준] 1365. 꼬인 전깃줄 / LIS,이분탐색(G2)

목차🖇️ 링크 https://www.acmicpc.net/problem/1365🗒️ 파이썬 코드 풀이from bisect import bisect_leftN = int(input())lst = list(map(int,input().split()))lis = [0]for i in range(len(lst)): if lis[-1]  1. 문제를 보고  LIS (Longest Increasing Sequence) 문제임을 알아야한다.처음 풀면, 생각할 수 없을 것 같다... 그냥 문제를 몇번 풀고 익숙해져야 될듯 2. 문제의 조건은 전봇대의 개수 N(1 ≤ N ≤ 100,000) 이다.때문에 시간복잡도가 O(N^2) 이하여야 함이중 for 문이 안되기 떄문에, 이분탐색으로 접근3. 이제 조건에 맞게 l..

[Python][백준] 2170. 선 긋기/ 정렬,스위핑 (G5)

🔗링크 :  https://www.acmicpc.net/problem/2170🗒️파이썬 코드 풀이N = int(input())lst = []for _ in range(N): a,b = map(int,input().split()) lst.append([a,b])lst.sort()merged = []# 초기값 설정start, end = lst[0][0],lst[0][1]for i in range(1,N): a,b = lst[i][0],lst[i][1] if a   1.두 점의 위치를 lst에 전부 넣어주고 sort로 정렬 해준다.여기에서 sort를 사용해도 된다. ( 정렬 시간 복잡도는 N*LogN | 10^6 * Log10^6 = 약 10^7)2. 초기값을 정렬된 lst의 첫번째 ..

[Python][백준] 1700. 멀티탭 스케줄링 / 그리디 (G1)

🔗링크 :  https://www.acmicpc.net/problem/1700🗒️파이썬 코드 풀이N,K = map(int,input().split())lst = list(map(int,input().split()))cnt = 0multitab = set()for i in range(len(lst)): # 장치가 멀티탭에 꽂힌 경우 if lst[i] in multitab: continue # 멀티탭 자리가 남는 경우 if len(multitab)  1. 세가지의 조건으로 나눈다.device가 멀티탭에 꽂힌 경우멀티탭 자리가 남는 경우멀티탭 자리 부족으로 device 교체2.  "멀티탭 자리 부족으로 device 교체"  이 부분이 중요한데, 멀티탭의 값이 lst의 i+1 ~ N ..

[Python][백준] 2252. 줄 세우기 / 위상정렬, DAG (G3)

🔗링크 :  https://www.acmicpc.net/problem/2252✨ 위상정렬 풀이 방식위상 정렬은 DAG(Directed Acyclic Graph)의 조건을 만족하면서 모든 노드를 나열하는 정렬 방법이다. 여기에서 DAG라는 말이 좀 어렵게 느껴질 수 있지만, 쉽게 말해 비순환형 그래프로 반드시 사이클이 없어야 한다. (뭐 어렵게 생각할 필요없고, 아래 예시와 같이 비순환형 그래프를 DAG라 보면 된다.) 위상정렬 같은 경우 그래프의 구조와 노드의 연결 방식에 따라 여러개의 답이 나올 수 있다.  EX) 다음은 위상 정렬에 대한 간단한 예시이다.아래의 그래프를 위상정렬로 나열하면 되는 것이다.  풀이과정은 다음과 같다.그래프 및 진입 차수 계산진입 차수 0인 노드 큐에 추가큐에서 노드 꺼내..

[Python][백준] 1916. 최소비용 구하기/ 다익스트라, 최단 경로 (G5)

🔗링크 :  https://www.acmicpc.net/problem/1062🗒️파이썬 코드 풀이from heapq import heappop,heappushN = int(input())M = int(input())lst = [[] for _ in range(N+1)]for _ in range(M): start,end,cost = map(int,input().split()) lst[start].append((end,cost))departure, arrival = map(int,input().split())distance = [float('INF')] * (N+1)distance[departure] = 0queue = [(0,departure)]while queue : current_cost,cu..

[Python][백준] 1062. 가르침 / 브루트포스,비트마스킹,백트래킹 (G4)

🔗링크 :  https://www.acmicpc.net/problem/1062🗒️파이썬 코드 풀이from itertools import combinationsN,K = map(int,input().split())left_word = K-5 alphabet = set("antitaca")newAlphabet = set()words = []for _ in range(N): word = set(input()) words.append(word) newAlphabet.update(word-alphabet) if left_word   1. k개의 글자를 배우는데, "anta" , "tica" 의 단어까지 포함이다. 기본 "antic", 총 5글자는 알아야 함2. 기본 배워야 할 단어: alphbet , ..

[Python][백준] 13144. List of Unique Numbers / 투포인터 (G4)

🔗링크 :  https://www.acmicpc.net/problem/13144🗒️파이썬 코드 풀이import sysinput = sys.stdin.readlineN = int(input())lst = list(map(int,input().split()))number = set()rs = sp = 0 for ep in range(N): while lst[ep] in number: number.remove(lst[sp]) sp += 1 number.add(lst[ep]) rs = rs + ep - sp + 1print(rs)ex)1 2 3 1 2 1. 위와 같은 입력을 예시로 들어보자. 아마 대부분의 보통은 1 / 1,2 / 1,2,3 /  2 / 2,3 / ..