코딩일기

오랜만에 문제풀다 하나씩 오늘은 union find disjoint set 알고리즘을 공부할 차례 보스가 -1이고 보스랑 연결되어 있는 조직원 찾고, 그 조직원과 보스가 묶인 부분집합이 몇 개있는지 찾는 문제다 https://brownbears.tistory.com/460 [Python] union find (disjoint-set) 알고리즘 union find (disjoint-set) 이란? 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조입니다. 간단하게 다수의 노드들 중에 연결된 노드를 찾거나 노드들을 brownbears.tistory.com union find(disjoint-set)의 핵심은 아래 3가지. 1. 초기화 : N 개의 원소가 각각의 집합에 ..

# https://www.acmicpc.net/problem/5430 import sys from collections import deque def AC(p, lenn, arr): # RDD 4 [1,2,3,4] i = 0# p의 인덱스 r = 0# reverse의 count if (arr[0] == '' and p[0] == 'D'): # 예외처리 1 D 0 [] 일 경우 error가 나와야 한다 print("error") return while (p[i] == 'R' or p[i] == 'D'): # len(p)로 하면 오류가 난다 if (p[i] == 'R'): # 바로바로 reverse()하면 시간초과가 나므로 r로 카운트만 한다 r += 1 elif (len(arr) == 0 and p[i] ..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀..

# Programmers |DFS(완전탐색)||| |:---|:---|:---| |[타겟넘버](https://programmers.co.kr/learn/courses/30/lessons/43165#qna) |lv.2 |[풀이](https://github.com/shl13/ps_study/blob/master/selim/level2/43165dfs.py)| |[소수 찾기](https://programmers.co.kr/learn/courses/30/lessons/42839) |lv.2| [풀이](https://github.com/shl13/ps_study/blob/master/selim/level2/42839dfsprime.py)| |BFS||| |:---|:---|:---| |[게임 맵 최단거리](htt..

# https://programmers.co.kr/learn/courses/30/lessons/42839 # 완전탐색 > 소수 찾기 lv.2 answerlst = [] def is_prime(x): # 소수가 맞다면 1을 return if x

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9..

https://programmers.co.kr/learn/courses/30/lessons/42748 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로..

프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/42883# 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 백준 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net # https://programmers.co.kr/learn/courses/30/lessons/42883# # 탐욕법(Greedy) > 큰 수 만들기 from collections import deque import sys def solution(number, k): bucket = deq..

https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다. 그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 ..