[Python] 1407번: 에디터 풀이 포스팅 썸네일 이미지

Coding_Algorithm/백준 풀이

[Python] 1407번: 에디터 풀이

백준 풀이 1407번: 에디터 풀이 문제 Link: https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제 설명 풀이 과정 제가 처음 접근했던 방식은 단순하게 string을 사용하여 관리를 하고, 별도로 index라는 변수를 사용하여 커서를 구현했었습니다. 리스트를 사용하려다가 string으로 관리하는 것이 더 빠르기 때문에 string으로 구현하였습니다. 코드는 다음과 같습니다. # github link: https://github.com/dub..

2022.05.17 게시됨

[Python] 17215번: 볼링 점수 계산 풀이 포스팅 썸네일 이미지

Coding_Algorithm/백준 풀이

[Python] 17215번: 볼링 점수 계산 풀이

백준 풀이 13783번: 합 구하기 풀이 볼링? 절 대 못 참 아 문제 Link: https://www.acmicpc.net/problem/17215 17215번: 볼링 점수 계산 첫째 줄에 각 기회마다 소현이가 쓰러뜨린 볼링핀의 개수가 공백없이 주어진다. 이때 스트라이크는 S, 스페어는 P, 핀을 하나도 못 쓰러뜨린 것은 -으로 주어진다. www.acmicpc.net 문제 설명 단순하게 볼링 점수 계산을 하는 프로그램을 만드는 것입니다. 저는 볼링을 쳐본적이 있어서 따로 점수 계산에 대한 이해가 필요 없었지만, 볼링 점수 체계에 대해서 잘 모르시는 분은 참고 부탁드립니다. 참고: https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=jabab..

2022.02.21 게시됨

[Python] 11441번: 합 구하기 풀이 포스팅 썸네일 이미지

Coding_Algorithm/백준 풀이

[Python] 11441번: 합 구하기 풀이

백준 풀이 13783번: 합 구하기 풀이 문제 Link : https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 단순한 합 구하기 문제인 것 같다. 그러나 특히 python같은 느린 언어로 정직하게 짤 경우, 시간초과가 발생하게 된다. import sys input = sys.stdin.readline N = int(input()) n_list = list(map(int, inp..

2022.01.20 게시됨

[Python] 13783번: Hashing 풀이 포스팅 썸네일 이미지

Coding_Algorithm/백준 풀이

[Python] 13783번: Hashing 풀이

백준 풀이 13783번: Hashing 풀이 문제 Link : https://www.acmicpc.net/problem/13783 13783번: Hashing For each test case, print a single integer: the number of valid strings that have the same hash as the input string (including the input string itself), modulo 1,000,000,007 (10^9 + 7). www.acmicpc.net 문제 A string hashing function is an algorithm that turns arbitrary strings into numbers. If S is a string of..

2021.12.28 게시됨

Semaphore - 코드로 이해하기 포스팅 썸네일 이미지

Coding_Algorithm/Operating System

Semaphore - 코드로 이해하기

앞선 글들에서 공유메모리를 사용하기 위한 방법을 서술하였습니다. 그러나 이런 기법을 구현할 때, synchronization관련 이슈를 해결하는 것은 필수적입니다. 이런 부분들을 고려하지 않는다면 race condition등의 이슈가 발생합니다. 1. (IPC) Semaphore? 따라서 사용하는 대표적인 수단 중 하나가 semaphore입니다. 특히 이번 글에서 다룰 것은 IPC Semaphore인데, 이는 공유하는 자료 구조에 대한 통제된 접근을 위해서 사용됩니다. 주요 특징을 정리하자면, 기본적으로 semaphore은 양의 정수값을 가집니다. 자원에 프로세스가 접근할 때 마다 semaphore값은 감소합니다. semaphore값이 0이되면 semaphore값이 다시 양수가 될 때까지 프로세스의 접근..

2021.06.02 게시됨

Shared Memory - 코드로 이해하기 포스팅 썸네일 이미지

Coding_Algorithm/Operating System

Shared Memory - 코드로 이해하기

저번 글에서는 shared memory에 대한 이론적인 부분을 보았습니다. 이번 글에서는 공유메모리에 관련한 함수들을 알아보고, 코드를 통해 직접 이해를 해보는 걸로 합시다. 1. 관련 함수 파악 우선 크게 4가지 함수가 있습니다. 하나하나 알아보도록 하겠습니다. #include #include 공유메모리 관련 1) shmget int shmget(key_t key, size_t size, int shmflg); shmget함수는 처음 공유메모리를 생성하고, shmid를 얻을 때 사용하는 함수입니다. 앞선 글에서 공유메모리는 생성만 하면 다른 과정은 할 필요가 없다고 언급했었습니다. 그 과정을 담당하는 함수입니다. 다음은 매개변수에 대한 설명입니다. key : 공유메모리를 설정할 때 사용하는 고유 key..

2021.06.01 게시됨

IPC와 Shared Memory 포스팅 썸네일 이미지

Coding_Algorithm/Operating System

IPC와 Shared Memory

1. IPC란? IPC는 Inter-Process Communication의 줄임말로, 프로세스 간에 데이터 및 정보를 주고받기 위한 메커니즘입니다. 특히나 OS는 프로그램을 실행시키면서 하나의 프로세스가 독박으로 모든 걸 해결할 수 없기 때문에, 통신을 위한 메커니즘은 필수적이죠. 따라서 이런 통신을 할 때 사용하는 것을 IPC라고 합니다. 다른 것들에 알아보기에 앞서, 이런 IPC는 어떠한 상황에서 필요할까요? 크게 4가지로 나누어 볼 수 있습니다. 정보 공유: 여러 사용자가 동일한 정보에 흥미를 가질 수 있음에 따라, 병행적으로 접근할 수 있는 환경 제공 계산 가속화: task를 sub task로 나누고, 병렬 처리를 통한 계산 가속화 모듈성: 시스템 기능을 변도의 프로세스 또는 스레드로 나누어 모..

2021.05.31 게시됨

[Python 2] input() 취약점에 대하여 포스팅 썸네일 이미지

Coding_Algorithm/Python

[Python 2] input() 취약점에 대하여

0. 조사하게 된 계기 CTF문제를 풀다가 엄청난걸 알아냈습니다 python2에 한해서 input함수는 eval(raw_input(prompt))로 실행된다는 사실이요. 일단 eval함수 자체가 보안측면에서 봤을 때는 위험한 함수죠. (명령어를 실행시킬 수 있는 함수인지라) 그래서 조금 더 찾아봤는데 생각보다 뭐가 많더라구요! 그래서 정리할 겸 찾아봤습니다. 1. input함수 자체에 대하여 일단 input함수 자체에 대해서 조금 탐구를 해봅시다. python2에서 이 함수의 가장 큰 특징은 "알아서 형변환"을 해준다는 점입니다. 직접 확인해봅시다 s1 = input("input()>> ") print(type(s1)) s2 = input("input()>> ") print(type(s2)) s3 = i..

2021.05.17 게시됨

[C] pthread_mutex 이해하기 포스팅 썸네일 이미지

Coding_Algorithm/C_C++

[C] pthread_mutex 이해하기

thread에서 가장 중요한 이슈는 race condition입니다. 동일한 메모리에 접근할 때, 그 메모리에 대해서 일관성이 유지될수 있는가?에대한 문제죠. 이런걸 해결하기 위해서 대표적으로 사용할 수 있는 함수가 pthread_mutex입니다. 오늘은 그 함수를 어떻게 사용해야하는지에 대해서 보도록 하겠습니다. 01. 문제상황 이해 우선 문제가 있는 상황을 통해서 이해를 해봅시다. 다음은 간단한 thread를 통한 코드입니다 #include #include #include int mails = 0; void* routine(){ for (int i=0;i

2021.05.07 게시됨

Thread에 대하여 - C언어 기준으로 포스팅 썸네일 이미지

Coding_Algorithm/Operating System

Thread에 대하여 - C언어 기준으로

Thread에 대하여 1. Introduction 우선 Thread를 이야기 할 때 항상 거론되는 Process에 대해서 간단히 이야기해봅시다. Process에 대해서는 앞서 글을 써놨으니 참고합시다. C언어에서 가장 대표적으로 프로세스를 생성할 때 쓰는 함수는 fork()입니다. 그러나 이 과정은 매우 비쌉니다.(자원의 측면에서) 우선 프로세스라는 것 자체가 자원을 공유하지 않고 각각의 code, data 등을 가지기 때문에 기존의 process의 것들을 다 복사를 해 주어야 합니다. 이걸 해결하기 위해 COW(Copy on Write)방법같은것도 고안되었지만, 만족스러운 수준까지 성능이 향상되지는 않았습니다. 그래봤자 page table이라던가 file descriptor table같은건 복사해주어야..

2021.05.06 게시됨

[OS] Scheduling Techniques Depending on Environment 포스팅 썸네일 이미지

Coding_Algorithm/Operating System

[OS] Scheduling Techniques Depending on Environment

Scheduling Techniques Multiple-Processor Scheduling 앞서서는 Scheduling 알고리즘 자체에 대해서 알아보았습니다. 근데 그 알고리즘들은 모두 single-processor라는 전제 하에 배웠는데, 오늘은 그 이외의 상황들에 있어서는 어떤 방식으로 스케줄링이 되어야 하는지에 대해서 알아보도록 하겠습니다. 1. Multiple-Processor Scheduling 우선 이 멀티프로세서 스케줄링의 경우에는 여러개의 비슷한(homogeneous) 프로세서들로 이루어져있습니다. 이러한 멀티프로세싱은 크게 두 가지로 나뉩니다. - Asymmetric Multiprocessing '비대칭'이라는 단어처럼 하나의 대장 프로세서가 있고, 그 친구가 스케줄링 및 자원분배를 담..

2021.04.28 게시됨

[OS] Scheduling Algorithm - 2 (RR, Priority Scheduling, Multilevel Queue) 포스팅 썸네일 이미지

Coding_Algorithm/Operating System

[OS] Scheduling Algorithm - 2 (RR, Priority Scheduling, Multilevel Queue)

Scheduling Algorithm - 2 RR, Priority Scheduling, Multilevel Queue 1편에 이어서 Scheduling Algorithm에 대해서 계속 알아봅시다. 1. RR (Round Robin) 기본적으로 FCFS(First-Come First-Served)에서 preemptive가 추가되었다고 보면 됩니다. Round Robin 알고리즘에서 가장 중요한 점은 모든 프로세스에 기본적으로 같은 시간을 준다는 것입니다. 실제로는 보통 0~100ms 정도의 시간을 준다고 하네요. 아무튼 미리 정해놓은 시간이 다 되면, CPU를 뺐기고, queue의 뒤로 가는 식으로 진행됩니다. 대신에, 이 time unit이 너무 크면 FCFS랑 같은 격이 되고, 너무 잦은 경우에는 너..

2021.04.27 게시됨