분류 전체보기

[백준 17298 17299] 오큰수 , 오등큰수 C++

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 자료구조, 스택 문제 1. 문제풀이 아이디어 N이 최대 1,000,000이므로 단순히 2중 for문으로 해결하는건 시간제한에 걸리게 된다. (N이 최대 5,000 정도면 가능할듯..) (1) 오큰수 1. 스택이 비어있을때 지금 보는 배열의 원소와 원..

[백준 1644] 소수의 연속합 C++

1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 수학, 두 포인터, 정수론 1. 문제풀이 아이디어 에라토스테네스의 체를 이용해서 N까지의 소수를 배열에 순서대로 저장한다. 배열의 마지막 소수를 ed 포인터, 그 이전 소수를 st포인터로 지정 st와 ed까지의 소수의 합을 sum으로 지정 처음에 sum = Prime_list[ed] + Prime_list[st]의 값으로 하고 sum > N이면 st와 ed가 같아질 때까지 sum -= Prime_list[ed]; ed--; 를 수행한다. st와 ed가 같아지면 st--; sum -= Prime_list[st]를 수행한다. (*순서중요!!) sum == N 이면 result++; 하..

[백준 1300] K 번째 수 C++

1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 이분 탐색 1. 문제해결 아이디어 일단 n이 최대 100000 이므로 B배열을 실제로 만들어 주는건 불가능하다. i번째 행은 i의 배수의 집합임을 이용하자 N = 5, K = 17 이 주어졌을 때. 이 문제를 이분탐색으로 풀기 위해서 5x5의 절반인 12를 최초 mid로 설정하자(lo = 0, hi = 25) 12는 위 표에서 몇 번째일까? 1행은 모두 12보다 같거나 작다 -> cnt += 5 2행도 모두 12보다 같거나 작다 -..

[백준 2146] 다리만들기 C++

2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 그래프 탐색, BFS 삼성전자 A형 기출문제 1. 문제풀이 아이디어 각 섬을 BFS로 돌면서 해당 섬의 경계좌표를 찾아서 저장한다 섬 간의 거리(경계좌표간의 거리)를 모두 찾아보면서 최솟값을 구한다 2. 코드 설명 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51..

SystemSoftware - Buffer OverFlow #2

SystemSoftware - Buffer OverFlow #1 Buffer OverFlow 배열에 할당된 메모리 사이즈를 초과해서 사용하는경우 발생 보안 측면에서 가장 빈번하게 일어나는 이슈 중 하나 대표적인 상황 : input string의 길이를 체크하지 않을 때 가지고 있 hyeo-noo.tistory.com buffer overflow는 무슨 문제를 일으키는지 어셈블리어를 통해 좀 더 자세하게 알아보자 // echo 00000000004006cf : 4006cf: sub $0x18, %rsp 4006d3: mov %rsp, %rdi 4006d6: callq 400680 4006db: mov %rsp, %rdi 4006de: callq 400520 4006e3: add $0x18, %rsp 400..

SystemSoftware - Buffer OverFlow #1

Buffer OverFlow 배열에 할당된 메모리 사이즈를 초과해서 사용하는경우 발생 보안 측면에서 가장 빈번하게 일어나는 이슈 중 하나 대표적인 상황 : input string의 길이를 체크하지 않을 때 가지고 있는 buffer보다 많은 양의 string이 들어오면 buffer overflow발생 아래 코드를 통해서 buffer overflow가 발생하면 어떤일이 생기는지 알아보자 typedef struct{ int a[2]; double d; } struct_t; double fun(int i){ volatile struct_t s; s.d = 3.14; s.a[i] = 1073741824; return s.d; } void print_fun(int to){ for(int i = 0; i

[백준 2239] 스도쿠 C++

2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 백트래킹 1. 문제풀이 아이디어 브루트포스 + 백트래킹 문제이다 현재 칸이 '0' 이라면 1 ~ 9까지의 숫자를 모두 대입해 보고, 대입한 숫자가 현재 칸에 들어가도 되는지 확인한다. 현재 칸에 모든 숫자가 들어갈 수 없다면 현재 칸을 다시 0으로 만들고 이전 칸으로 돌아간다. 현재 칸이 '0'이 아니라면 다음 칸으로 넘어간다. 2. 코드 설명 ~ 숫자를 입력 받아 Map 배열에 넣는다. ~ Map 상태를 보여준다. ~ 현재 칸에 들어있는 숫자를 넣어도 룰..

[Django] 회원정보 모델 설계 UserModel design #1

Django UserModel Design #1 1. 회원정보 모델 생성 - User 모델 회원정보 모델을 사용자 임의로 구성하고 정의하기 위해서 AbstractBaseUser 클래스를 상속받아 User모델을 새롭게 구성했다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 from django.db import models from django.contrib.auth.models import AbstractBaseUser class User(AbstractBaseUser): password = models.CharField(max_length=128) username = models.CharFiel..

[백준 2449] 전구 C++

2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전 www.acmicpc.net 1. 문제풀이 아이디어 전구를 A, B 두 부분으로 나누고, A의 시작 지점의 색깔과 B의 시작 지점의 색깔을 재귀적으로 같게 한다면 A, B 모두 같은 색이 될 것이다.. - A부분의 색을 같게 하는데 필요한 작업의 수 + B부분의 색을 같게 하는데 필요한 작업의 수 + 현재 A, B의 첫 번째 전구의 색을 같게 하는데 필요한 작업의 수 2. 코드 설명 dp[st][ed] : 전구 배열에서 st부터 ed까지의 전구를 모두 같은 색으로 맞추는데 필요한 ..

[백준 1700] 멀티탭 스케줄링 C++

1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 그리디 알고리즘 OS page replacement policy 중 하나인 Optimal replacement policy 를 적용하는 문제이다. 미래에 어떤 작업을 할 지 다 알고있는 경우이므로 적용이 가능하다 -> 가장 나중에 사용될 작업을 현재 멀티탭에서 뽑는다 (2021/05/16 update) 이 문제에서도 특정 조건이 부합하는지만 알면 언제나 최적의 해를 구할 수 있다 특정 조건을 찾는게 많이 어려웠음.. 특정 조건 : ex) 3구짜리 멀티탭이 있고 ..