[백준] 1074 Z | Gol5 | 분할정복(divide and conquer) Pythonhttps://www.acmicpc.net/problem/1074 접근사분할 하면서 좌표 위치에 따라 순서를 더해 계산해가면 될 것 같았다유형 : 분할정복[문제해석] 2^N 크기의 정사각형 배열을 Z모양으로 나눠 탐색할 때, 특정 칸을 탐색하는 순서 구하기 Z모양 탐색이란 : 2사분면 > 1사분면 > 3사분면 > 4사분면 순 [구상] 4x4. N=2 4x4/4 = 4 가 제일 큰 사각형 크기. 현재 탐색중인 면 크기 = S 이 중에 누구? r,c 값이 S / 2 보다 큰가?작은가? 그 안에서 다시 2^N/2 /2 0 1 2 3 0 | 0 1 4 5 1 | 2 3 6 7 2 | 8 9 ..
DSA/Algorithm
[백준] 5430 AC | deque, 구현 | Gol5 Pythonhttps://www.acmicpc.net/problem/5430 접근유형 : deque, 구현 [문제 해석] 주어진 문자열에 주어진 연산을 수행한 결과를 출력양쪽에서 제거가 일어나야 하므로 데크deque 사용시간제한이 넉넉하지는 않은 것 같아서뒤집기 연산 시 문자열을 실제로 뒤집지 않고 현재 앞방향을 표시해두고 그에따라 처리하는 방향으로 풀어보겠음시간 제한 : 1초 트러블 슈팅입력을 깔끔하지 않게 주는 경우를 많이 겪어보지 못해서아래 경우들 처리에 좀 시간이 걸렸다. 알아두자~앞뒤의 특정 문자 제거하고 입력받기 : string = input().strip(”\n그리고제거할문자들”)** input()은 마지막에 \n가 같이 들어오므로 s..
[백준] 2696 치즈 | BFS | Gol5 Pythonhttps://www.acmicpc.net/problem/2636 접근유형 : bfs [문제 해석] 치즈의 공기에 노출된 부분이 한시간에 한칸씩 녹을때, 마지막에 녹은 치즈 칸수와 다 녹기까지 걸린 시간은?-> BFS로 공기를 상하좌우 인접한 것만 탐색해나가면 치즈 속 구멍을 공기로 인식하지 않도록 처리가 가능해짐! 구상 1. 전체 치즈 개수 적어둠 2. BFS 돌며 공기랑 인접한(이번에 녹을) 치즈 위치 적어둠 3. 녹임. 녹은 치즈 개수를 전체 치즈 개수에서 빼서 남은 치즈 개수 계산해둠 4. 다 녹을 때까지 반복 트러블 슈팅구멍이 아닌 공기에 노출된 부분만 세는 방법을 깔끔하게 생각해내지 못했는데,확실히 공기인 부분에서 시작하는 bfs를 ..
[백준] 2869 달팽이는 올라가고싶다 | 수식 | Bro1 Pythonhttps://www.acmicpc.net/problem/2869 접근시간제한 0.25초시간제한때문에 반복문 없이 수식으로 해결해야 하는데 수식정리 머리가 안굴러가서 애먹은 문제..^.^브론즈라고 만만하게 보지 마라 하늘아래 알고리즘문제는 공평하다math.ceil() 대신 그냥 /나누기연산 후 int()함수 적용한 결과와 같은지 비교해서 소수점유무를 알아내 처리해도 올림과 같은 효과를 낼 수 있다.풀이달팽이는 무조건 낮에 도착하므로, 마지막날 갈 수 있는 거리는 밤에 미끄러지는 영향을 받지 않는다.따라서 한번의 낮 이동값을 미리 전체거리에서 빼두고, 남은 거리 이상 이동하려면 낮밤(하루)를 최소 몇번 지나야 하는지 계산하면 된다. 나..
[백준] 12904 A와 B | greedy? | Gol5 Pythonhttps://www.acmicpc.net/problem/12904 접근유형 : greedy [문제 해석] 문자열을 두 종류의 연산만으로 특정 문자열로 바꿀 수 있는지 확인하는 문제 문자열 S, T주어짐. S를 T로 바꿀 것 가능한 연산 두가지 마지막에 A추가 전체를 뒤집고 B추가 바꿀 수 있으면 1, 없으면 0 출력 구상 그냥 bfs로 연산 경우의 수 다 확인?? -> 너무 오래 걸림거꾸로 연산? -> 이게 연산 수가 적다! T -> S 뒤집는 연산 - 현재 마지막 글자에 따라 연산이 결정된다. 마지막 글자가 A이면 : 마지막에 위치한 A제거 마지막 글자가 B이면 : 마지막에 위치한 B제거 후 전체 뒤집기 트러블 슈팅x 코드im..
[백준] 2812 크게 만들기 | stack, greedy? | Gol3 Pythonhttps://www.acmicpc.net/problem/2812 접근유형 : stack, greedy?이런것도 그리디에 속하는 구나..? 흠 [문제 해석] 주어진 숫자에서 숫자 K개를 지웠을 때 얻을 수 있는 가장 큰 수 구하기고려해야할 조건 자릿수 (앞으로 갈수록 큰 숫자가 자리하도록) 그 숫자 자체 구상앞에서부터 그 다음자리가 현재자리보다 크면 현재자리 삭제 -> 아이디어는 맞음! 구현에 스택을 떠올릴 것..~ 트러블 슈팅x 코드import sysinput = sys.stdin.readlinestack = []N, K = map(int, input().split())nums = tuple(map(int, input(..
[백준] 1946 신입사원 | greedy | Sil1 Pythonhttps://www.acmicpc.net/problem/1946 접근유형 : greedy 아이디어 생각하는 거 하나 더 배웠다..~ [문제 해석]두가지 순위 중 적어도 하나는 선발인원 내 최저순위가 아닌 사람 최대인원수 구상 아 설명부터 어렵다일단 각 순위 1등을 뽑아놓고 이 1등의 다른 순위를 이기는 사람을 고름? x순위 합 작은순? x-> 첫번재 순위대로 정렬해두고 차례로 보면서 b순위 기준점을 넘는지 판단하면 된다..a는 갈수록 낮아지기만 하므로 b만 보면 되는 것..!!..! 백준 예제로 예시를 들어보면 아래처럼 된다.v는 선발한 사람, x는 선발하지 않은 사람이다.예1) 1 4 v -> min_second = 4 2 3 v -..
[백준] 1715 카드 정렬하기 | greedy, heap | Gol4 Pythonhttps://www.acmicpc.net/problem/1715 접근유형 : greedy, heap(우선순위큐)전에 풀었던 14698 슬라임문제랑 비슷해서 금방 해결~[문제 해석] 모든 카드를 합치는 비교 횟수 최솟값 정렬된 카드묶음들이 주어짐 카드 묶음은 두개씩 합칠 수 있고, 합칠때에는 두 묶음의 카드수 합만큼 비교가 필요함 구상 전에 풀었던 슬라임문제랑 비슷하네? 작은묶음부터 합치면 될 듯 새로 생긴 묶음을 포함해 다시 정렬해야 하므로 정렬 상태를 유지하면서 삽입삭제가 필요함 -> 힙(우선순위큐) 트러블 슈팅x 코드import sys, heapqinput = sys.stdin.readlineN = int(input..
[백준] 1931 회의실 배정 | greedy | Sil1 Pythonhttps://www.acmicpc.net/problem/1931 접근유형 : greedy 어떤 걸 기준으로 할 지 아이디어만 떠올리면 쉬웠던 문제. 근데 난 못 떠올려서 솔루션봤다 ㅎ.ㅎ[문제 해석] 배치 가능한 회의의 최대 수 구하기 회의 시작시간과 끝나는 시간이 주어지며, 이는 같을 수도 있음 회의가 끝나자마자 시작 가능 시간은 24시간으로 분단위 없이 주어져서 편하게 쓰면 될듯~ 구상 제일 많은 회의를 배치할 수 있는 경우는 ? 짧은 것부터? ㄴㄴ 빨리 시작? ㄴㄴ 겹치는 수 세두고 적은 거 > 짧은 거? ㄴ -> 대박 끝나는 시간이래... 맞네 트러블 슈팅아이디어 떠올리는 연습..(? 코드import sysinput = sys..
[백준] 14621 나만 안되는 연애 | MST (Kruscal) | Gol3 Pythonhttps://www.acmicpc.net/problem/14621 접근유형 : MST - kruscal [문제해석] 모든 대학교를 연결하는 최단경로 = MST 남초대학교M 와 여초대학교W 사이의 간선만 경로에 포함할 수 있음 모든 학교를 연결하는 경로가 존재하지 않을 경우 -1 출력 1 1 크루스칼~로 해보자 간선수 노드수에 비해 그렇게 많은 것같진 않고 프림보다 빠른 편이니까특이사항은 간선 선택할 때, 연결된 노드의 학교종류가 같으면 선택하지 않도록 짜면 될 듯 구상 간선 (가중치, 노드1, 노드2) 형식으로 한 리스트에 입력받음 이 때 노드1과 노드2의 학교타입이 같으면 리스트에 넣지 않음 (그래프에 사용할..
[백준] 1922 네트워크 연결 | MST (Prim, Kruscal) | Gol4 Pythonhttps://www.acmicpc.net/problem/1922 접근유형 1 : MST - prim (396ms)유형 2 : MST - kruscal (240ms)간선 수가 노드수보다 100배 많은데 prim보다 kruscal 이 더 빠르네 [문제 해석]최소의 비용으로 모든 컴퓨터를 연결하는 경로 구하기= MST 최소 스패닝 트리 구하기1 1 1 간선이 주어질 때 두 노드번호가 같을 수도 있다 MST 프림으로 풀어보자~ 노드선택 구상 - Prim간선 입력받아서 연결된 첫번째 노드별로 (가중치, 노드2) 형태로 리스트에 저장최소힙 사용(정렬유지하며 잦은 삽입 필요)현재 그래프에 포함되어있는 노드 표시하는 배열..
[백준] 1197 최소 스패닝 트리 | MST (Kruscal, Union Find) | Gol4 Pythonhttps://www.acmicpc.net/problem/1197 접근유형 : MST - 크루스칼 알고리즘크루스칼 알고리즘은 간선 추가 시마다 사이클이 생기는 지 확인하기 위해 주로 Union Find를 사용한다. 그래서 그 내용도 나옴! [문제 해석]주어진 그래프의 최소 스패닝 트리MST를 구하는 문제1 1 음수 가중치 간선 존재, 양방향가중치 절댓값 시간 제한 1초메모리 제한 128MB [개념]MST 구하는 법크루스칼 : 간선을 greedy로 선택, 사이클없이(union find)프림 : 노드를 선택. 노드 중 간선 가중치가 가장 적은 것 직전 글에 프림으로 풀어보았고, 이번에는 크루스칼로 풀..
[백준] 1197 최소 스패닝 트리 | MST(Prim) | Gol4 Pythonhttps://www.acmicpc.net/problem/1197 접근유형 : MST - 프림 알고리즘프림이 노드를 추가하는 방식이지만 결국은 간선의 가중치를 확인해야 하는데논리를 너무 노드에만 집중해서 생각했다. 생각을 열어두자~ [문제 해석]주어진 그래프의 최소 스패닝 트리MST를 구하는 문제 1 1 음수 가중치 간선 존재, 양방향 가중치 절댓값 시간 제한 1초 메모리 제한 128MB [개념]MST 구하는 법 크루스칼 : 간선을 greedy로 선택, 사이클없이(union find)프림 : 노드를 선택. 노드 중 간선 가중치가 가장 적은 것정점보다 간선 개수 범위가 더 커서 프림으로 짜보자 구상 1 간선 입력받아 리스트..
[백준] 4195 친구 네트워크 | Union Find, 경로압축 | Gol2 Pythonhttps://www.acmicpc.net/problem/4195 접근유형 : union find (합집합)union find 인데 노드 이름이 문자열인union find 짤 때 모든 연산은 루트노드 기준으로 할 것 기억하기..~! [문제 해석]sns 친구추가(합집합 연산) 시마다 그 새로운 친구 네트워크에 포함된 전체 친구 수 구하기친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말함친구 = 노드, 친구관계 = 간선시간제한 3초친구관계 수 앗.. 사이클이 생길수도 있겠네..? 같은 네트워크면 친구추가 무시해야겠다노드가 친구이름으로 주어지니까 딕셔너리를 쓰자 구상 : 노드이름 문자열에 해당하는 번호를 따로 ..
[백준] 1717 집합의 표현 | Union Find, 경로압축 | Gol5 Pythonhttps://www.acmicpc.net/problem/1717 구상유형 : union find +경로압축둘 다 새롭게 구현해본 개념이라 공부가 많이 됐다!union find만으로는 시간초과가 나서 경로압축 등 find함수를 최적화하여 해결했다.새로운 재미가 있던 문제~ [문제 해셕]0~n 각 하나씩만 원소로 갖는 집합 n+1개가 주어지고, 이들 간의 집합 연산 결과 출력하기0 a b : a와 b가 포함되어있는 집합의 합집합 연산1 a b : a와 b가 같은 집합의 원소인지 확인하는 연산a = b 일 수도 있음1 1 시간제한 : 2초 트러블 슈팅TS 1 : 합집합 연산 시 x,y가 포함된 집합 전체를 연결시켜야하므로..
