L.O.K

문제) 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 알고리즘) [알고리즘] 힙 정렬 ( Heap Sort ) 힙 정렬( Heap Sort )은 성능 좋은 정렬 알고리즘이지만 원리를 이해하기 쉽지 않다. 그 이유는 완전 이진 트리를 이용하기 때문이다. [자료구조] 완전이진트리 배열에 저장하기 완전 이진 트리를 lordofkangs.tistory.com 힙정렬은 힙트리를 이용한 정렬이다. 힙트리는 두 가지 조건이 충족되어야 한다. 1) 완전이진트리여야 한다. 2) 부모는 반드시 자식보다 커야 한다. ( 부모는 반드시..

문제 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 알고리즘 [JAVA] 백준 2751번 수 정렬하기2 : 병합 정렬( Merger Sort ) 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. lordofkangs.tistory.com 위 알고리즘을 사용하여 풀었으나, 파이썬의 장점을 살리지 못한 풀이가 되었다. 파이썬은 리스트를 생성하..

문제) 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 알고리즘) [알고리즘] 퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort)은 이름 그대로 정렬을 빠르게 하는 알고리즘이다. 그러나 버블정렬에 비해 빠를 뿐, 이름만큼 가장 빠른 정렬 알고리즘은 아니다. 퀵 정렬(Quick Sort) 알고리즘이란? 정렬 알고리 lordofkangs.tistory.com 위 개념은 JAVA언어로 구현되어 있는데 파이썬 언어로 바꾸어 실행한 결과, 메모리초과가 발생했다. 원인은 파악하는 중이다. 그래서 원리는 같지만 조금 ..

문제 ) 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 알고리즘) [알고리즘] 버블정렬 향상 시키기 버블정렬은 가장 쉽고 이해하기 쉬운 정렬이다. 그러나 시간복잡도가 O(n2)이어서 효율이 좋지 않다. 7개의 수를 일차원 배열에 저장하였다. 이제 버블정렬을 사용하여 오름차순으로 바꾸어 보자 lordofkangs.tistory.com 코드) 1) 교환횟수 카운트하여 버블정렬 향상시키기 N = int(input()) sortArr = [] for i in range(N) : sortArr.append(int(input..

음료수 얼려 먹기 문제 N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다 입력 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 = maxY : return False else : return True # DFS 알고리즘 구현 함수 def dfs(x, y) : visited[x][y] = True # 방문처리 if not validateIndex(x,y) : r..

완전 탐색에는 두 가지 방법이 있다. 1. 반복문 2. 재귀 호출 반복문은 모든 데이터에 접근할 때 사용되고 재귀호출은 모든 데이터 '조합'에 접근할 때 사용한다. 보글 게임 ( Boggle Game ) 5x5 알파벳 보드판에 상하좌우 및 대각선으로 인접한 칸들을 이동하면서 찾고자 하는 '단어'를 찾는 게임이다. 단어 'PRETTY'를 찾는다고 가정하자. 'PRETTY'는 하나의 알파벳이 아닌 알파벳의 '조합'이다. 단순히 알파벳 P를 찾는 문제이면 이중 for문(반복문)을 이용하여 완전탐색하면 된다. 하지만 BOGGLE 게임은 알파벳 '조합'을 찾는 문제이다. 1. 데이터 - 상하좌우/대각선 이동 데이터 ( 자료구조 : 배열 ) - 보글게임 보드판 ( 자료구조 : 배열 ) dx = [-1,-1,-1,1..

1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1. 문제 추상화 1부터 n까지 수로 이루어진 수열 A가 주어진다. 오름차순으로 스택에 push하여 수열A를 구현할 수 있는지 판별하시오. 구현이 불가능하면 NO를 출력하고 구현이 가능하면 어떤 과정을 통해 구현되는지 출력하시오. (push : '+' 출력, pop '-'출력' ) 2. 알고리즘 조건은 두 가지이다. 1. 스택을 사용하라. 2. 오름차순으로 push해라. 스택은 L..

9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 1. 문제 추상화 '(' 와 ')' 만으로 이루어진 문자열을 PS라 부른다. 그리고 괄호가 열리고 온전히 닫히는 PS를 VPS라 부른다. 주어진 PS 중 VPS를 구분하라. 2. 알고리즘 조금 고민했다. 그리고 한 가지 개념이 스쳐지나갔다. 바로 '스택(Stack)'이다. VPS는 두 가지 특성이 있다. 1. 나중에 열린 괄호가 먼저 닫혀야 한다. 2. 모든 열린 괄호는 닫혀야 한다. 1번은 LIFO의 특징이다. 그러므로 스택과 알..

18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 1. 문제 추상화 수열이 주어졌을 때 각각의 수보다 작은 서로 다른 수의 개수를 입력받은 순서대로 출력하시오. 2. 알고리즘 1. HashMap 조금 난해한 문제였다. 입력받은 순서대로 결과를 출력해야 했기에 원본용 배열과 정렬용 배열 두 가지를 만들었다. 그렇다보니 출력과정에서 두 개의 배열을 탐색해야했고 시간복잡도는 O(n2)이 되어 시간초과가 발생했다. 그래서 인터넷에서 방법을 찾던 중 HashMap 자료구조..

1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 1. 문제 추상화 알파벳으로 이루어진 단어들을 길이가 짧은 순으로 정렬하시오. 길이가 같으면 알파벳 순으로 정렬하시오. 2. 알고리즘 1. HashSet 자료구조 예제를 보면 동일한 단어를 입력받으면 출력시, 중복을 제거해주는 것을 확인할 수 있다. 중복제거를 위해 HashSet 자료구조를 사용한다. 2. 정렬 알고리즘 Quick, Merge, Heap 정렬 알고리즘을 사용하였다. ( Bubble 정렬은 시간초과가 난다. ) [알고리즘] 퀵 정렬 (Q..