분류 전체보기20 [Journal] 점근표기법과 시간복잡도 big O notation과 little o notation에 대해 찾아보던 중, 우리가 정보과학 분야에서 자주 사용하는 시간 복잡도 개념이 이것을 응용했다는 것을 알 수 있었다. 이에 대해 자세히 조사 해 보았다. 이론적 배경 (1) 점근표기법 점근표기법이란 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 방법이다. 알고리즘의 시간 복잡도를 단순화 할 때나 무한급수의 뒷부분을 단순화 할 때 사용한다. 대표적으로 아래 다섯가지 표기법이 있으며, 이 보고서에서는 Big O Notation과 Little o Notation을 다룬다. 간단한 다항식을 예로 들어보자. (2) 시간 복잡도 시간 복잡도란 함수로서 작동하는 알고리즘을 취해 시간을 정량화 하는 것이다. 대부분의 경우 Big O Notation.. 2023. 9. 10. [DREAMHACK] darimchal_001 https://dreamhack.io/wargame/challenges/609 darimchal_001 이야기 드림이는 평화로운 오후, 드림핵으로 해킹공부를 하고 있었습니다. 그런데 갑자기! [ 드림이의 | 컴퓨터가 | 잠겨버렸습니다 ] 그렇습니다... 드림이의 친구 다리미... 결국 늘 드림이에게 dreamhack.io 문제에서 주어진 것들을 살펴보자. 받은 파일의 압축을 해제하면 C언어로 구성된 코드와 리눅스 환경에서 코드를 실행할 수 있는 파일 두가지로 구성되어있다. 본문에서는 XOR연산으로 암호화 했다는 힌트를 제공했다. 원래대로면 리눅스에서 파일을 실행하여 문제를 해결해야 하는데, C코드를 분석해서 푸는 문제이기 때문에 굳이 리눅스 환경을 구현하지 않아도 된다. #include와 #define부.. 2023. 9. 9. [Journal] 단백질 구조 예측 알고리즘 AlphaFold2 - 소개와 원리 단백질은 20가지의 아미노산으로 이뤄진 선형 사슬 수십~수천개가 복잡한 3차원 모양으로 접혀 있어(a나선, b병풍) 구조를 파악하기 어려우며 3D모델링으로 표현하는 데에도 한계가 있다. 현대 생명과학에서는 단백질의 구조를 어떻게 파악하고 있을지 알아보자. 국제 과학 학술지 ‘사이언스’는 단백질 접힘 구조를 예측하는 인공지능 알파폴드2의 개발을 21년도 최고의 과학 성과로 선정했다. 구글 딥마인드사는 단백질 구조 예측 인공지능 알파폴드2로 36만5000개 이상의 단백질 3차원 구조를 정확히 예측했다. 알파폴드2는 단백질 구조 예측 대회(CASP)에서 90%가 넘는 정확도를 기록했다. 2018년도의 최고기록이 70%대인것과 비교하면 놀라운 발전이다. ‘사이언스는 연구의 다음 단계로 단백질들의 상호작용 예측을.. 2023. 8. 30. [DREAMHACK] SingleByteXor https://dreamhack.io/wargame/challenges/559 SingleByteXor 어느날, 살인사건이 일어났다. 살인 사건의 유일한 증거물은 쓰여있는 쪽지에는, 다음과 같이 적혀있었다. 54586b6458754f7b215c7c75424f21634f744275517d6d 크립이에게 주어진 단서는, 쪽지의 내용과 이것이 dreamhack.io 주어진대로 구현하면 되는 간단한 문제이다. cyberchef 등 외부 사이트를 이용해도 쉽게 해결된다. 주어진 배열은 16진수임을 쉽게 알 수 있다. 16진수 숫자 2개가 하나의 아스키코드를 이룬다고 생각하고, 2글자씩 묶어 PW배열에 저장한다. 이것으로 flag는 23글자임을 알 수 있다. PW = [0x54, 0x58, 0x6b, 0x64, 0.. 2023. 8. 28. [BOJ] [C++] 3197 백조의 호수 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net BFS문제인데, '두 백조가 만날 때 까지 반복한다'는 조건이 달렸다. 배열의 크기가 1500*1500으로 크기 때문에, 효율적인 코드 작성이 필요하다. 다음과 같은 기본 구조를 가지고 문제를 해결한다. 기본 구조 입력을 받고, 물 공간과 백조 위치를 Queue에 넣는다 >>> BFS 1회 실행 >>> 백조가 만나는지 확인 >>> 만났다면 break, 만나지 않았다면 .. 2023. 8. 28. [BOJ] [C++] 22940 선형 연립 방정식 보호되어 있는 글 입니다. 2023. 8. 27. 이전 1 2 3 4 다음