2JINISHAPPY 2JINISHAPPY

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 카카오 기출에 슬라이딩 윈도우를 이용한 문제가 종종 등장하길래 풀어본 투포인터 기초 문제 left, right 두 개의 포인터를 배열의 양 끝에 위치하도록 한 뒤 (left 포인터를 한 칸 이동한 것 vs right 포인터를 한 칸 이동한 것) 중 절댓값이 더 작은 쪽으로 이동하게끔 구현했다 n=int(input()) w=sorted(map(int,input().split())..

2jinishappy.tistory.com/124 Array의 k번째 작은 element 찾기 - QuickSelect 알고리즘 Size가 n인 int형 Array에서 k번째로 작은 element를 찾는 방법은 여러 가지가 있다. 가장 formal하게, 배열을 sort한 뒤 인덱스가 k인 element를 반환하면 간단하게 구할 수 있다. 우리가 알고있는 Sort 알고 2jinishappy.tistory.com 이전 포스팅에서 배열에서 k번째로 작은 element를 찾아내는 Quick Select 알고리즘을 알아봤다. Quick Select를 진행하면서 선정한 pivot이 너무 작거나 크다면, partitioning이 제대로 이루어지지 않아 Worst-Case에 O(n²)이 소모됨을 확인했다 그렇기 때문에..

MST는 그리디 알고리즘을 이용해서 구할 수 있는 트리의 한 형태이다. 연결 그래프(하나의 Connected Component로 이루어진 그래프)에서 생성할 수 있는 부분 그래프이기도 하다. 그래프의 형태를 한 네트워크 회선이 존재할 때, 네트워크 구축 비용을 최소로 하는 경우의 수를 찾고 싶을 때 쓰이기도 한다. 그래프 G=(V,E)와 같고, 각 edge에 weight가 주어져 있을 때, 아래의 두 조건을 만족하는 G'( V(G), T )가 MST이다. 1️⃣ G'은 Connected하다. 2️⃣ G'은 포함할 수 있는 edge들의 cost 총 합을 최소로 한다. 해당 그래프에서는 연두색으로 칠해진 edge들을 선택했을 때 모든 vertex를 포함할 수 있으면서, cost의 합을 최소로 할 수 있기 때..

Quick Sort란, Divide And Conquer 방식을 사용하는 정렬 알고리즘이다 Merge Sort와 함께 많이 쓰이면서, 시간 복잡도가 O(nlog n)으로 실용적이고 빠르다 🤗 1️⃣ Array의 Size가 1이면 해당 Array를 return 2️⃣ Size가 2 이상이면 pivot element를 하나 정한다 3️⃣ A1을 Array에서 pivot보다 작은 element, A2를 Array에서 pivot과 크기가 같은 element, A3를 A에서 pivot보다 큰 element를 담은 Array로 Divide한다 4️⃣ A1, A2, A3를 Quick Sort한 다음 return된 A1, A2, A3 순서대로 이어 붙인다(Conquer and Merge) 위와 같이 Divide 해준 ..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 할만한가?싶다가도 ㅇㅏ닌 악마같은 문제.... 😠 어찌보면 삼성 역량테스트의 표준같은 문제였당 나는 두 가지 방법으로 문제를 풀었다 ① 일단 역테 기출중에서 많이 쓰는, 모든 경우 완전탐색을 위해 DFS로 방향 경우의 수를 구한 뒤 방향 순서에 따라 5번 이동을 해주고 배열 최댓..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 엄청나게.... 빡취는 문제 구슬이 들어있는 판을 이리저리 굴려서(이동이 멈출때까지 방향 전환X) 10회 안에 구멍에 빨간 구슬..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net ^- 문제링크 인구 이동 문제는 맞닿아있는 국가와의 인구 수 차이가 L이상 R 이하일 경우 국경을 열어 열린 국가들끼리 인구 수를 평..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net ^- 문제링크 테트리스 블록을 회전/대칭했을 때의 모양을 고려하여 배열에 덮었을 때 덮은 숫자의 최댓값!을 찾는 문제이다 ㅇㅖ를 들..