분류 전체보기

[백준-2668] 숫자고르기 - Python

문제 소개 문제 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자. 사용한 알고리즘 더보기 DFS (루트 저장) DFS 중에서 진행된 루트를 저장하는 DFS를 하면된다. 비슷한 문제로는 https://dizzy-theme.tistory.com/53가 있다. 구상 첫번째줄에서..

[백준-2573] 빙산 - Python

문제 소개 https://www.acmicpc.net/problem/2573 사용한 알고리즘 더보기 BFS 알고리즘 & 부분 업데이트 이번 문제는 시간초과와 메모리초과를 해결하는 부분이 어려웠음 일단은 풀어서 해결을 했지만 풀고나니 별개로 조금더 최적화 할 수 있는 여지가 있는것 같다 (어떤 부분일까?) 구상 물과 얼음의 위치를 저장해놓은 Arr를 업데이트 할때 원본 Arr를 복사하지 않고 빙산을 업데이트 하면 안된다. 만약에 동시에 진행이 된다면 근접해 있는 빙산에 대해서 내년에 빙산에서 물이되는 위치가 바로 물로 판정이 되고 근접해 있는 옆빙산에 영향을 주기 때문이다. 이부분을 알았다면 빙산과 물의 위치를 저장해놓은 Map을 복사해서 2개를 만들어야 한다고 생각 할 수 있다. 왜냐하면 복사본을 만들지..

비교기반 정렬의 시간복잡도 하한은 nlog(n) 이다

비교기반 정렬 비교기반 정렬이 무엇인가에 대한 설명은 --에 있다 비교기반 정렬의 시간 복잡도의 하한은 \(n log(n)\) 이라고 알려져 있다. 조금 더 정확하게 표현은 다음과 같은 구절을 보면 된다. Can we say that it is impossible to sort faster than Ω(n lg n) in the worst case? If we could, then this would be what it’s called a lower bound. 비교기반 정렬은 가장 Worst Case에 대해서도(그러니까 모든 Case의 정렬 형태에 대해) 필요한 시간 복잡도가 \(nlog(n)\) 정도라는 것으로 이보다 더 적은 방법이 없다는 것이다. 여담으로 시간 복잡도의 상한은 \(n^2\) 이다 ..

변수 표기법 - 카멜표기법/파스칼표기법

프로그래밍 상에서 변수명 명명시 표기법을 사용하면 변수명만 보고도 어느정도 변수에 대한 정보를 확인할수있다. 프로그래밍에서 변수명명법의 대표적인 2가지 표기법을 소개한다. 표기법의 종류 - 카멜 표기법 - 파스칼 표기법 2가지 표기법 모두 공통적으로 중간의 새로운 단어의 첫번째 단어를 "대문자"로 표기한다 예를 들어 numer를 add하는 기능을 타겟으로 만들고 addnumber 라고 표현하고 싶다고 한다면 add + number 는 두 단어로 되어 있음으로 아래와 같이 써야한다 add + number => AddNumber 로 카멜과 파스칼의 차이는 첫번째 문자를 대문자로 쓰냐 안쓰냐의 차이로 아래와 같이 구분된다 카멜 표기법 : addNumber 파스칼 표기법 : AddNumber 다음은 두 표기법의..

[백준-5014] 스타트링크 - Python

문제 소개 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다) 강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그..

포인터 기초

포인터를 공부하는데 어려웠던 점은 첫번째로 포인터의 개념과 두번째로 프로그램내에서 문법 사용(특히 포인터 연산자)이였다. 1. 포인터의 개념 이해 포인터의 개념은 간단하게 아래의 예시로 이해 할 수 있었다. 예시 자료형 문자 A char 숫자 119 / 3.14159 int / double 메모리의 주소 bfe30846 int* , double* , ... 간단하게 C++에서 기본적으로 제공하는 변수의 타입중에 하나로 생각 할 수 있다 문자와 숫자를 담는 메모리와 변수형이 다르듯이 메모리의 주소만들 저장하기 위한 변수형이 따로 있다 (그걸 포인터라고 한다) 2. 포인터 실사용 포인터와 관련된 연산자는 2가지로 *,& 이다 int n = 20 ; // 왼쪽 같이 선언이 되면 변수에 대해 n의 주소와 n의 ..

다익스트라 알고리즘

먼저 봐야 할 것 Graph 탐색 알고리즘 요약 그래프 탐색중에서 최단거리 탐색에 사용되는 알고리즘이며 1. 거리(시간,비용)이 양수로 주어지고 2. 알고리즘을 수행하면 어떤 1개의 node에서 갈 수 있는 모든 node에 대해 최단거리를 구할수있다. 3. Heap의 자료구조를 사용하여 구현한다. 문제 소개 Graph 탐색 사용한 알고리즘 더보기 다익스트라 알고리즘 구상 Code 소개 # Python code import heapq import collections graph = collections.defaultdict(dict) # graph 입력받기 위해 ##################################### # graph = { # 'A': {'B': 8, 'C': 1, 'D': 2}..

두 수의 합

먼저 봐야 할 것 투포인터 알고리즘 요약 문제 소개 두 수의합이 특정 타겟이 되는 인덱스를 반환하라 예를들어 [ 2 , 7 , 11 , 15 ] 인 리스트가 있다고 할 때 타겟값이 9라고 한다면 결과로 2와 7의 위치인 0과 1을 반환하면 되는 것이다 사용한 알고리즘 더보기 투포인터 구상 리스트를 정렬한뒤 투포인터 , 오른쪽과 왼쪽을 가르치는 포인터를 양쪽 맨끝으로 지정한뒤 특정 타겟 값보다 크면 제일 큰 값을 가르키는 오른쪽 포인터를 왼쪽으로 이동 특정 타겟 값보다 작으면 제일 작은 값을 가르키는 왼쪽 포인터를 오른쪽으로 이동 그런데 어떻게 이러한 탐색 방법이 항상 working하는것인가 살펴보자 정렬된 리스트 \( a_1 , a_2 , a_3 , ... , a_L \) 배열중에 정답 $S$을 가르치는..

[백준-1655] 가운데를 말해요 - Python

문제 : [백준-1655] 가운데를 말해요 (Python) 출처 : 백준 사용한 알고리즘 더보기 자료 구조 : heapq 를 이용한 탐색 Python Code import sys import heapq sys.stdin = open("input.txt", "r") N = int(input()) right_heap=[] # 최소 힙 left_heap=[] # 최대 힙 for _ in range(N): temp_input = int(input()) if len(left_heap)==len(right_heap): heapq.heappush(left_heap,(-temp_input,temp_input)) else : heapq.heappush(right_heap, (temp_input, temp_input)) ..

[백준 - 12865] 평범한 배낭 - Python

먼저 봐야 할 것 요약 문제 소개 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 사용한 알고리즘 더보기 Dynamic programming 구상 이문제는 대표적인 DP ..