[백준] 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가 포함된 집합 전체를 연결시켜야하므로..
[백준] 16946 벽 부수고 이동하기 4 | BFS | Gol2 Pythonhttps://www.acmicpc.net/problem/16946 채점 되게 천천히 됨 쫄깃하네여..ㅎ골드 쯤 되니까 시간제한이 문제가 되기 시작한다 ㅎ허허 구상유형 : bfs [문제 해석]벽이 존재하는 맵이 주어짐. 각 벽마다 벽이 없어졌을 때, 해당 벽 위치에 인접한 공간 크기를 구하는 문제빈 공간은 0, 벽은 1벽 위치에 해당하는 공간 크기를 10으로 나눈 나머지를 출력시간제한 : 2초구상 1 (timeout)전체를 돈다벽(1)이 나오면 해당 벽에 인접한 공간을 bfs 돌며 공간 크기를 계산한다벽 위치에 공간 크기를 10으로 나눈 나머지를 기록한다 구상 2 (성공)전체를 돈다방문 전인 빈 공간(0)이 나오면 bfs 인접한..
[백준] 2146 다리만들기 | BFS | Gol3 Pythonhttps://www.acmicpc.net/problem/2146 pypy로만 성공한 풀이입니다.(python은 시간초과)구상유형 : bfs비슷한 문제들을 푸는 중이라 접근은 어렵지 않게 했으나조건문 하나 잘못적어서 시간 진짜 많이 썼다 도륵시간초과만 나서 시간을 줄이는 방법만 고민했는데 코드에 잘못된 부분이 있었다코드에 논리적인 오류가 있어도 오답이 아닌 시간초과만 날 수도 있다는 것을 깨달은 시간,,,pypy로만 통과했지만 핵심적인 문제는 찾았고 더 이상 시간복잡도 개선에 시간을 쓰는 건 무리라고 판단. 넘어가자! [문제 해석]땅과 땅을 연결하는 가장 짧은 다리 길이 찾기다리와 인접해있으면 연결된 것임시간제한 2초 구상전체를 2번 돌아야 ..
[백준] 13549 숨바꼭질 3 | BFS | Gol5 Pythonhttps://www.acmicpc.net/problem/13549 구상유형 : bfs직전에 푼 1697과 유사그래서 좀더 깔끔하게 풀 수 있었다! [문제 해석]1697 숨바꼭질 문제와 동일하나, 2배 이동을 하는 경우 드는 시간이 0이라는 점만 다르다.N에서 K로 가는 가장 빠른 횟수 찾기한 횟수에 할 수 있는 이동의 종류는 3가지+1-12배 0 ≤ N, K ≤ 100,000시간제한 2초메모리제한 512 MB 구상매번 세가지 경우 모두 bfs 돈다단, 아래 조건을 만족하지 않으면 큐에 넣지 않는다.이미 방문했던 숫자의 경우 이전의 해당 숫자까지 갔던 최소이동횟수보다 클 때숫자가 이동 가능 범위를 벗어날 때 (0 ≤ N ≤ 100,000)..
