전체 글 (21) 썸네일형 리스트형 (7/28) 3일차 - 자료구조(1) 이론 흔히 알고리즘하면 배우게 되는 기초적인 자료구조들을 배웠습니다. 연결리스트(Linked List) 자기 참조 구조체 : 자신과 같은 구조체를 참조하는 포인터가 삽입되어 있음 노드의 초기화 : typedef struct node { int data; struct node *next; } Node; Node *front; front = (Node *)malloc(sizeof(Node)); front->data = 1; front->next = NULL; 연결리스트의 경우 임의의 위치에서 삽입&삭제가 효율적이며 동적할당을 통해 메모리를 낭비하지 않는다는 장점이 있음 front와 rear를 이어주는 형태의 원형 연결 리스트(Circular Linked List)도 존재함 next값만 가지고 있다면 연결리스트, .. (7/27) 2일차 - 정렬과 탐색 문제 어제와 같이 문제를 풀었습니다. 총 8문제였습니다. https://bas.ioikorea.cc/problems/list 2022 여름학교 처음반 로그인이 안 되는 경우 브라우저를 구글 크롬으로 바꿔주세요. 불편을 드려 죄송합니다. 문제가 발생할 시 [email protected]로 연락해 주세요. bas.ioikorea.cc 1. 정렬하기 O std::sort를 사용하지 않고 직접 정렬을 구현하라는 문제입니다. 머지소트를 구현하여 해결하였습니다. 2. 나무자르기 O 백준에도 있는 문제입니다. 적어도 M미터의 나무를 얻기 위한 절단기 설정 높이를 구해야 합니다. 최소와 최대를 양쪽 끝으로 하는 이분탐색을 하여 빠르게 찾아줄 수 있습니다. 3. 교차하는 선분 △ i보다 오른쪽에 존재하는 i보다 작은 원소의 .. (7/27) 2일차 - 정렬과 탐색 이론 오늘은 어제보다 개념자체는 쉬웠습니다. 이곳저곳에서 접해본 개념, AP Computer Science A 하면서 했던 정렬 등이 있어 이해하는 것은 수월했고 힙 정렬은 개념을 다시 정립할 수 있었습니다. 2.1 순차 탐색(Sequential Search) 말그대로 앞에서부터 원하는 것을 찾습니다. \(O(n)\)의 시간복잡도를 가지고 있으며 찾았을 때 break 해주면 조금이나마 시간이 줄어듭니다. 2.2 최댓값 및 최솟값 찾기 a[0]을 초기의 최댓값 (또는 최솟값)으로 두고 순차탐색하면서 업데이트하면 n-1번의 비교를 통해 찾을 수 있습니다. n개의 원소를 [n/2]개의 쌍으로 나누고 작은 숫자들 중에서 최솟값 & 큰 숫자들 중에서 최댓값을 찾으면 쌍으로 나누는 데에 [n/2], 작은/큰 숫자들에서 .. (7/26) 1일차 - 이산수학 문제 오후부터 저녁까지는 예제 문제들을 풀었습니다. 총 10문제였으며 5문제 해결하였습니다(추후 업데이트 예정) https://bas.ioikorea.cc/problems/list 2022 여름학교 처음반 로그인이 안 되는 경우 브라우저를 구글 크롬으로 바꿔주세요. 불편을 드려 죄송합니다. 문제가 발생할 시 [email protected]로 연락해 주세요. bas.ioikorea.cc 1. 순열 O 사전순으로 순열이 몇번째인지 찾고, 다음 순열을 구하는 문제입니다. 사전순을 구하는 과정은 순열을 앞에서부터 순차탐색 하면서 \(i\)번째에 \(1 (7/26) 1일차 - 이산수학 이론 여름학교에 한번 떨어지고 어렵게 면접으로 붙은만큼 소중한 기회에 열심히 해보고자 배운내용 기록을 조금 하려고합니다. 문제가 외부에 공개되면 안될? 가능성이 있어 나만 보이기로 비공개로 하겠지만 추후에 공개할 수도 있습니다. 9:00 ~ 12:00 : 이론 학습 첫날은 이산수학으로 시작했습니다. 세종대학교 컴퓨터공학과 나중채 교수님께서 동영상 강의를 준비해주셨습니다. 정보과학회 측에서 받은 자료와 동일한 소주제 순서로 정리하려고 합니다. 1.1 논리(Logic) 명제 : 진리값이 참(T) 또는 거짓(F) 중 하나인, 선언적 문장 함축 또는 조건문 : p --> q 라고 쓰고 p가 참 & q가 거짓인 경우만 거짓 상호 조건문 : p q 라고 쓰고 서로 같을 때 참 항진명제 : 명제의 진리값이 항상 참일때 논.. Problem Solving Review #2 [06.04~06.06] 기회가 생겨 3일동안 많은 문제를 풀게 되었습니다. 문제가 많았고 다른 대회들이나 기말고사와 겹치다 보니 많이 늦어졌지만 좋은 문제들이 많았기에 정리해서 올리게 되었습니다. BOJ 20960. Po 아이디어는 간단하지만 이를 파악하기가 어려웠습니다. 결론적으로는 스택을 이용하여 간단하게 해결할 수 있습니다. 입력받은 배열 \(a\)를 순차탐색하면서 스택에서 \(a[i]\)보다 큰 원소들을 제거하고 알맞은 위치에 삽입해주면 됩니다. 다만, 스택에 이미 \(a[i]\)와 같은 값을 가진 원소가 존재한다면 \(a[i]\)값을 만들기 위해 추가적인 increasing의 작업을 거칠 필요가 없기 때문에 스택에 \(a[i]\)를 추가해주지 않아도 됩니다. 결과적으로 스택에 \(a[i]\)를 삽입한 횟수를 세어 출력.. USACO 2022 March Silver 후기 및 풀이 https://www.acmicpc.net/category/655 USACO 2022 US Open Contest www.acmicpc.net 2021-2022 USACO 대회가 이번 US Open 을 끝으로 종료되었습니다. 목표했던 만큼은 아니지만 그래도 만점을 받고 Gold Division에 갔다는 사실에 만족하고 있습니다. 이번 문제들은 상대적으로 조금 쉬웠던 것 같습니다. 0:00 ~ 0:30 간단하게 3문제를 읽고 입력만 구현해놓았습니다. 1번은 대충 그래프일 것 같았고, 2 3번은 문자열좀 끄적이다 보면 풀이가 나올 것 같았습니다. 0:30 ~ 0:55 : COW Operations 3번 문제의 예제를 접근하다보니 규칙만 찾으면 풀릴 것 같아 3번부터 풀었습니다. 먼저 문자가 1개, 2개, 3.. Problem Solving Review #1[2022.3월 1주 - 3월 3주] 3월의 시작부터 3주차까지 풀었던 문제들과 개념들을 정리해보고자 합니다. 앞으로 문제를 풀어나가는데 있어서도 정리해둔 것이 도움이 될 것 같고, 알고리즘을 자꾸 까먹는 저에게 가장 필요한 습관이 아닐까 생각이 들어 지속적으로 작성하려고 합니다. BOJ 2631. 줄세우기 KOI 2001 > 중등부 2번 간단한 관찰을 통해 한 가지 사실을 발견한다면 해결할 수 있지만, 처음 볼 때는 의외로 관찰이 떠오르지 않았습니다. LIS(Longest Increasing Sequence) 에 포함되는 아이들을 고정해놓고 나머지 아이들을 움직여야지만 최소의 아이들을 옮길 수 있기 때문에 간단히 DP로 LIS를 구현하여 해결할 수 있습니다. #include using namespace std; int n, a[202], .. 이전 1 2 3 다음