맞았습니다!!

해시 함수(Hash function)

2023.11.15·

PS/Algorithm

해시 함수는 말 그대로 입력을 변환하는 함수다. 목적은 임의의 데이터를 정해진 크기의 데이터로 바꾸는 것이다. 어떤 크기의 값을 넣어도 정해진 크기로 바뀌니 데이터 관리에 유리한 면이 있다. 하지만 정보의 크기를 한정하는 함수이기 때문에 정보 손실은 불가피하고 이것 때문에 이 함수는 단방향 함수다. 해시 함수인 결과(해시 값)만을 가지고 원래 값이 무엇이었는지는 확실히 알 수 없다. 본문에서는 자료구조로서의 해시 함수를 다룬다. 1. 키(Key)와 해시(Hash) 키는 해시 함수에 입력되는 기존 값을, 해시는 그 결과 값을 말한다. 이름(3글자)을 키로 받아 각 글자의 획수로 바꿔보자. 이 방법으로 이름이 거의 대부분 3자리의 숫자로 반환된다. 이 과정에서 이름은 키, 반환된 3자리 숫자는 해시이다. 수..

15683: 감시

2023.11.12·

PS/BOJ

시간 제한 메모리 제한 1초 512MB 문제 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. (중략) 사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. CCTV의 최대 개수는 8개를 넘지 않는다. 출력 첫째 줄에 사각 지..

9084: 동전

2023.11.11·

PS/BOJ

시간 제한 메모리 제한 1초 128MB 문제 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. 입력 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까..

배낭 문제(knapsack problem)

2023.11.08·

PS/Algorithm

배낭 문제는 정해진 비용 내에서 최적의 가치를 갖는 해를 찾는 문제다. 처음 이 문제를 접하는 사람들 대부분이 그리디로 접근하지만 그리디 알고리즘만으로는 해결할 수 없는 배낭 문제도 있다. 배낭 문제는 크게 두 유형으로 분류되는데 먼저 그리디 알고리즘을 적용할 수 있는 분할 가능한 배낭 문제와 그리디 알고리즘으로는 해결하기 어려운 0-1 배낭 문제가 있다. 1. 분할 가능한 배낭 문제 분할 가능한 배낭 문제는 말 그대로 가치와 비용을 분할해 가져올 수 있다. 예를 들어 10kg의 제한을 두고 배낭을 싸는데 5kg에 75의 가치를 가진 A와 4kg에 120의 가치를 가진 B, 7kg에 140의 가치를 가진 C가 있다고 해보자. 여기서 A, B, C 모두 원하는 만큼 쪼개서 가져갈 수 있는 물건이라고 가정하..

3190: 뱀

2023.11.06·

PS/BOJ

시간 제한 메모리 제한 1초 128MB 문제 'Dummy'라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 N×N 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할 때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸..

이진 탐색(이분 탐색, Binary Search)

2023.11.06·

PS/Algorithm

이진 탐색은 배열 속에 내가 원하는 자료가 있는지 찾는 방법이다. 탐색 구간을 둘로 나누어 실행하며 이를 반복해나가기 때문에 이진 탐색이라고 부른다. 책을 펼쳐서 내가 원하는 페이지를 찾는 과정과 아주 비슷하다. 우선 길이가 10인 arr이라는 배열이 아래와 같이 있다고 해보자. 배열이 정렬되어있지 않기 때문에 내가 원하는 값이 어디에 어떤 규칙으로 있는지 알 수 없다. 이 배열에서 자료를 찾으려면 앞에서부터 순차적으로 찾아야 한다. 이걸 선형 탐색(Linear Search)라고 한다. 8을 찾는다면 적당히 5번의 비교로 끝나겠지만 5를 찾는 경우 최악의 상황으로 배열 내 모든 데이터를 확인해야 한다. 따라서 이 방법은 시간 복잡도가 O(n)이다. 사실 이 정도의 시간복잡도가 그리 나쁘지는 않지만 배열의..

2565: 전깃줄

2023.11.05·

PS/BOJ

시간 제한 메모리 제한 1초 128MB 문제 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, (생략)과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해..

17070: 파이프 옮기기 1

2023.11.05·

PS/BOJ

시간 제한 메모리 제한 1초 (추가 시간 없음) 512MB 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태(생략)이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래(생략)와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, ..

1520: 내리막 길

2023.11.04·

PS/BOJ

시간 제한 메모리 제한 2초 128MB 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림(생략)과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로(생략)가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는..

함수 내부에서 외부 변수에 접근하는 방법

2023.11.04·

python

기본적으로 함수는 완전히 독립되어야 다루기 편리하다. 함수가 외부 변수에 종속되어버리면 함수를 고칠 때 외부 변수도 함께 고려해야 하고 그렇게 되면 하나의 함수를 수정하는 것이 코드 전체를 아우르는 작업이 될 수 있다. 가독성이 매우 떨어지며 디버깅에도 굉장한 혼란이 올 수 있다. 하지만 파이썬을 처음 다뤄보는 사람으로써, 아직 프로그래밍 언어에 대해 충분히 익숙해지지 않아 함수의 독립성을 완전히 이룰 수 없는 나로써는 함수가 외부의 변수에 접근할 수 있도록 해야하는 경우가 있다. 예를 들어 깊이 우선 탐색을 실행하는 아래 코드#1520: 내리막길 M, N = map(int, input().split()) board = [] check = [[False for j in range(N)] for i in ..

11054: 가장 긴 바이토닉 부분 수열

2023.11.04·

PS/BOJ

시간 제한 메모리 제한 1초 256MB 문제 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10}은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30}은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ ..

1644: 소수의 연속합

2023.11.04·

PS/BOJ

시간 제한 메모리 제한 2초 128MB 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어보면 다음과 같다. 3 : 3(한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다. 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오. 입..

티스토리툴바