붕어빵이 헤엄치는 바다

※ 개인적으로 공부하면서 끄적끄적 받아적는 거라 다소 엉망일 수 있습니다 [1일차 필기노트] 1. 수업 소개 https://opentutorials.org/course/1688/102452. 웹 어플리케이션을 만드는 순서 https://opentutorials.org/course/1688/93313. 구상 https://opentutorials.org/course/1688/93324. 기획 https://opentutorials.org/course/1688/93335. 인터넷과 웹의 역사 https://opentutorials.org/course/1688/93346. 서버와 클라이언트 https://opentutorials.org/course/1688/9408 ========================..

백준 2110번 문제. 공유기 설치 [Point] 파라메트릭 서치를 이용 (최적해 -> 이진탐색 + 결정) 공유기를 최대한 널찍널찍하게 설치할 수 있는 최대 거리를 찾는 문제다. 이진탐색의 응용 버전인 파라메트릭 서치를 이용하면 된다.간단한 개념은 이 게시글에 정리해두었으니 참조 알고리즘 자체는 어렵지 않다."음..좋아 너로 정했다!""문제 조건 만족!""헐..니가 만족된다구..? 좋아 일단 널 임시 정답으로 생각해둔 다음... 가라 다음 후보!""피카피카! 문제조건 만족!""헐 너도 만족되는구나! 가라 다음 후보!" 이렇게 이진탐색으로 범위를 좁혀가면서 최적해를 구하면 된다.(무슨 소리인지는 나만 이해할 수 있을 것 같다......) 기본 뼈대는 다음과 같다. 1. 필요한 값을 입력받고, 집의 위치를 ..

Parametric Search (파라메트릭 서치) [개요]이진탐색의 응용 버전.최소값이나 최대값 등의 최적해 문제를 구할 때 유용하게 쓸 수 있다.혹자는 이것을 최적화문제 = 이진탐색 + 결정문제 (Yes or No) 로 쪼개는 것이라고 표현하기도 한다. [기본 뼈대]1. 이진탐색을 이용해 임의의 값 계산(보통 mid값이다)2. 이 값은 문제의 조건을 만족합니까 안합니까? 3. 문제 조건을 만족할시 일단 저장해두고 범위를 좁혀가면서 최적화된 해에 도달 [전제 조건]이 서치를 적용하려면 해의 구간이 연속적이어야한다.만일 mid가 문제의 조건을 만족한다면, [Left,mid] 혹은 [mid,Right] 범위에 있는 해는 모두 문제의 조건을 만족할 만한 '가능성'을 가지고 있어야한다.당연한 얘기긴 한데, 5..

백준 2346번 문제. 풍선 터뜨리기 [Point] 원형으로 작동할 수 있게끔 하되, 는 것에 유의하여 "몇 걸음"을 움직였는지 카운팅해줄 것 처음에 이 문제를 보자마자 떠오른 생각은 환형 더블 링크드 리스트였다 (Circular Double Linked List) 터뜨린 풍선은 앞으론 고려 안한다는 점에서 원형 큐도 좀 생각하긴 했다..하지만 C언어에서 구현하려면 코드가 생각보다 길어질 것 같아서 어떻게 할까 고민하다가, 그냥 야매로 배열을 사용하기로 결정. 전체적인 알고리즘의 뼈대는 다음과 같다. Remain : 남아있는 풍선의 갯수 total : 전체 풍선의 갯수 (이 값은 변하지 않는다)dir : 방향move : 몇 걸음 이동해야 하는가 (속도 = 속력+방향인것처럼 arr[i]의 값을 몇걸음(mo..

백준 1005번 문제. ACM Craft [Point] DP와 DFS를 짬뽕시켜 풀어보자. 개인적으로 좀 고난에 빠졌던 문제.분명 알고리즘 분류에 "위상정렬"이라고 들어가있는데, 나는 위상정렬로 어떻게 풀어야할지 떠오르지 않아서 다이나믹 프로그래밍과 DFS를 짬뽕시켰다.찾아보니 이 분의 글이 "위상정렬" 관점에서 제일 설명이 잘 된 글 같다. (링크) 일단 목표건물 w부터 차례대로 역추적 DFS를 하려고 했다DP배열은 0으로 초기화되어있으니 visit 배열의 역할을 대체하여 사용하였다. 부분해의 후보들 중 가장 큰 값을 가진 후보가 부분해로 채택이 되고, 이런 부분해들이 모여 최종 해를 구할 수 있다 (건물을 시공하려면 선행건물이 전부 다 건설되어야하기때문에 가장 건설시간이 긴 선행건물을 생각해야한다) ..

백준 4963번 문제. 섬의 개수 [Point] DFS를 이용해 그래프의 연결요소(Connected Component)의 갯수를 찾아내라 그래프의 연결요소란 이동가능한 "뭉치"라고 생각하면 된다. 이 문제에서 요구하는 섬의 정의와 그 갯수는 그래프의 연결요소 개수와 일맥상통한다.우선 w=0,h=0이 들어오지 않는 이상 무한루프로 케이스를 입력받고 결과값을 출력하면 된다.매 과정이 반복될때마다 방문여부를 알려주는 visit[][]과 섬의 갯수를 알려주는 cnt 변수를 도로 초기화하는 것을 잊으면 안된다. 코드는 간단하다.방향배열 dx,dy를 이용해 탐색가능한 8개의 주변 정사각형을 검사한다.①이동가능하면서(map[][]=1) ②맵을 벗어나지 않는 유효한 범위(nx와 ny의 범위 체크), ③마지막으로 한번도..

출처 : 네이버캐스트 -> 링크 램많을수록, 빠를수록 좋은 컴퓨터의 주기억장치[RAM ]컴퓨터의 핵심 부품 중, CPU(중앙처리장치)는 연산 작업, 보조기억장치는 각종 데이터를 보관하는 작업을 수행한다. 보조기억장치로는 HDD(하드 디스크 드라이브), SSD(솔리드 스테이트 드라이브), CD, DVD, 플로피디스크 등 다양한 종류가 존재하지만 PC(Personal Computer)와 같은 일반적인 컴퓨터에서는 대개 HDD를 의미하는 경우가 많다. 따라서 컴퓨터에서 처리되는 대부분의 작업은 HDD에 있는 데이터를 토대로 CPU가 이를 연산 처리하여 출력장치(모니터 등)로 그 결과를 표시하는 방식으로 이루어진다.때문에 이론적으로는 CPU와 HDD만을 가지고도 컴퓨터는 데이터 처리를 할 수 있다(물론, 실제로..

백준 2178번 문제. 미로 탐색 [Point] BFS 알고리즘 활용, 레벨=거리 라고 생각한다 BFS 알고리즘은 시작 노드로부터 레벨 0, 1, 2, .... 순으로 순차적으로 탐색해나가는 그래프 순회 알고리즘이다.이를 이용해서, 이동가능한 주변 노드를 계속 탐색하다가 다음 탐색지에 목표 노드가 포착되면 해당 레벨에 1을 더해서(목표지점으로 한번 더 뛰어야하니까) 리턴해주면 된다.위에서 서술한 BFS 특성 때문에 맨 처음 리턴하는 레벨값이 '최소'거리일수밖에 없음.구조체를 이용, level 변수가 거리를 나타내는 변수라고 보면 된다. 처음에 헤맸던 부분은 level, 즉 거리를 어떻게 적어주냐였다. 처음엔 while문 안에 넣어서 한사이클 돌때마다 level을 늘려버리는 바람에 레벨 2에 있던 애들은 ..

소스 코드를 이쁘게 올리고 싶다면 Color Scripter 라는 아래 사이트를 이용하면 된다https://colorscripter.com/ 각자의 선호에 맞춰 코드를 각양 각색으로 꾸밀 수 있는데,내가 제일 선호하는 것은 스타일 패키지다. 1. 자신의 소스코드를 이 사이트에 복붙한 후, 2. 언어와 스타일 패키지를 지정해주고 3. 화면 좌하단의 "클립보드에 복사"를 클릭, 4. 코드를 올리고자 하는 본인의 블로그에 Ctrl+V 해주면 예쁘게 복붙이 된다.

그래프의 정점을 모두 한번씩 방문하는 알고리즘을 순회 알고리즘(Traversal Algorithm)이라고 한다.크게 두가지 종류가 있는데,하나는 깊이 우선 탐색(DFS,Depth First Algorithm)이고, 하나는 너비 우선 탐색(BFS,Breadth First Algorithm)이다. 1. 깊이 우선 탐색 (DFS) 인접한 정점이 존재한다면 계속 한 우물만 깊게 파고드는 타입. 만약 인접한 정점이 존재하지 않는 정점(이른바 막다른 길)을 발견한다면, 이 전에 있었던 정점으로 돌아가서 또 새롭게 팔 우물(..)이 있는지 살펴본다.일단 "길이 있으면 가고 본다!!" 라는 막무가내 타입이기 때문에,①인접해있고 ②한번도 방문한 적이 없다면 , 바로 해당 정점으로 탐색하러 가면 된다. 재귀 함수만 안다면..