조준화의 오류정정

https://www.acmicpc.net/problem/2250예제 191 2 32 4 53 6 74 8 -15 9 106 11 127 13 -18 -1 -19 14 1510 -1 -111 16 -112 -1 -113 17 -114 -1 -115 18 -116 -1 -117 -1 1918 -1 -119 -1 -1ans :3 18depth와 col을 구하면 된다. depth는 dfs와 함께 부모의 depth + 1로 구할 수 있다. col이 문제가 되는데 col을 구하는 방법은 처음에 두 가지를 떠올렸다.각 레벨의 가장 왼쪽 노드와 가장 오른쪽 노드 사이의 노드 개수 구하기 -> widthdp로 푸는데, dp [k] = k 레벨의 width로 두고 dp [k+1] = dp [k] + k 레벨의 가장 왼쪽..

https://www.acmicpc.net/problem/20955그래프를 트리로 바꾸면 된다. 이때 사용할 수 있는 특성은 트리는 n개의 노드에 대해 n-1개의 간선을 가지며 사이클이 없는 연결 그래프이다. 처음 떠올린 풀이는 우선, 연결 요소들을 파악해서 sub graph로 나누고, 그 그래프를 트리로 만든 뒤 그래프끼리 잇는 간선을 추가하는 풀이였다. 그런데 문제를 보면 N, M이 굉장히 크다. 따라서 sub graph를 트리로 만드는 과정을 시뮬레이션 방식으로는 절대 불가능하다고 판단하고 연산 횟수만 구하면 된다는 점에 집중했다. 우리는 어떤 간선을 제거할지는 생각할 필요가 없고, 적절한 간선을 선택했다고 가정하고 제거하는 횟수만 구하면 된다. 그렇다면 그 횟수는 어떻게 구할 수 있을까? 일단, ..

HTTP - StatelessHTTP는 Stateless 프로토콜이다. 연결을 유지하지 않고 요청과 응답을 주고받으면 연결을 끊고 다시 요청할 일이 생기면 연결을 새로 구축하는 특성을 가지고 있다는 뜻이다. 대부분의 웹은 HTTP, RESTful API 서버를 사용할텐데 그럼 서버가 클라이언트의 정보를 기억할 방법이 없다. 특히 한 번 로그인한 사용자는 계속 로그인이 유지되어야 하는데 서버 입장에서는 요청하는 클라이언트가 DB의 어떤 사용자인지 구분할 방법이 없다. 로그인을 하던 안 하던 해당 페이지에 접근하는 요청은 GET /url HTTP/1.1 이기 때문이다.   아래의 방식처럼 url로 로그인 정보를 넘겨줄 수도 없고 어딘가에 로그인 정보를 숨겨서 로그인을 유지할 수는 있겠지만 수많은 단점을 가지..

https://www.acmicpc.net/problem/4803 예제6 31 22 33 46 51 22 33 44 55 66 61 22 31 34 55 66 40 0---ans : Case 1: A forest of 3 trees.Case 2: There is one tree.Case 3: No trees.주어진 그래프에서 트리가 몇 개 존재하는지 판단하는 문제이다.트리의 조건은 사이클이 없는 연결 요소이고 n-1개의 간선으로 이루어져 있고 임의의 두 정점에 대해 경로가 유일하다는 것인데, 이 조건을 이용해서 찾아야 한다.처음에는 연결 요소를 찾고 사이클이 없는지 판단한 뒤 n-1개의 간선으로 이루어져 있고 모든 정점 간 경로가 유일한지 체크하려 했다. 그런데 bfs를 사용해서 연결 요소를 찾다 보니 ..

[바킹독님 블로그 정리 글입니다!] [실전 알고리즘] 0x19강 - 트리이번 시간에는 트리를 다루어봅시다. 바로 본론으로 들어가겠습니다. 특별히 트리에서의 BFS와 DFS를 또 익힐 예정입니다. 저희는 0x16강에서 이진 검색 트리를 배우며 이미 트리라는 개념을 적당blog.encrypted.gg 트리의 기본적인 특성부터 알고 가자면, 트리의 정의는 무방향이면서 사이클이 없는 연결 그래프이다. V개의 정점에 대해 V-1개의 간선을 가지는 사이클이 없는 연결 그래프라고 생각하면 된다. 트리에서의 BFS는 그래프의 BFS와는 조금 다른 의미를 가진다. 그래프의 BFS는 특정 정점에서 연결된 점을 찾는 용도로도 많이 사용되었는데, 트리는 연결 그래프이므로 방문 순서와 부모 배열, depth 배열을 채울 수 있..

https://www.acmicpc.net/problem/1707 문제를 좀 분석해 보자면 간선의 수는 200000, 정점의 수는 20000, 테스트 케이스 5개이다. 시간 복잡도는 꽤나 여유로워 보이니 문제를 분석해 보았다. 그래프를 두 집합으로 분할하되, 분할된 집합에서 인접하는 노드가 없게끔 분할하면 된다. 가장 먼저 떠오르는건 흐름은 다음과 같았다.시작점 start를 한 집합에 넣고, 인접한 점은 다른 집합에 넣는다.방문하지 않은 점 next에 대해 똑같이 1번을 수행한다.이렇게 떠올랐는데 굉장히 큰 오류들이 있었다.먼저 next는 첫 번째 단계의 start와 연관되어 있을 수 있었다. 즉, 맨 처음 시작점의 인접한 점과 그다음 방문하지 않은 점이 인접하다면? 인접하지 않다면? 모두 다른 방향으로..

오늘은 인턴에서 시킨 번역에 관해서 공부를 먼저 좀 했다. 규모도 작겠다 그냥 API로 번역하면 안 되나 싶었지만 무언가 문제가 있다고 하셔서 여러 방법을 생각해 보았다. 1. 아고다에서는 KantanAI를 사용하고 있었다. 라이브러리나 오픈소스 개념은 아닌 것 같고 AI 모델을 사용해야 하는 것 같은데 아직 AI에 관한 지식이 부족해서 비용이 얼마나 드는지, 중소기업 규모에서 사용할만한지는 판단할 수 없었다. KantanAI- The worlds most advanced machine translation enginesKantanAI is the world’s leading custom neural machine translation technology developer and creators of t..

학기 중엔 바빠서 TIL을 쓸 생각을 딱히 못했는데 방학도 했겠다 슬슬 다시 시작하려 한다. 매일매일의 목표부터 짚고 가자!1일 1문제 풀기1일 1커밋 (CS 스터디, AI 스터디 등)인턴 가기 전 운동정해진 공부 중 하나 꼭 하기 오늘은 인턴 시간에는 대표님이 시키신 아고다 등의 사이트에서 사용하는 언어 번역 방법을 조사했다. 그 과정에서 CMS라는 걸 새로 배웠는데 콘텐츠 관리 시스템이라는 웹사이트 제작 툴이었다. 그냥 쉽게 만드는 툴뿐 아니라 서버와 DB까지 제공하고 플러그인도 많이 제공한다는 것 같은데 솔직히 잘 모르겠다. 크게 쓸 일이 없을 것 같다. 그 외에도 번역 툴을 좀 공부했는데 크게 세 가지가 있다. 파파고, 구글 등 번역 API, CMS 사용, 플러그인 사용여기서 API는 지금 바로 ..

웹 소프트웨어 - 카드피디아템플릿 엔진 사용법과 프론트, 백의 기본 개념이 다져졌다. 생각하지 못한 이득이었다. 사실 뭐 사용법과 개념은 공부하면 되는 거고 진짜 느낀 점은 근거 있는 디버깅의 중요성이었다. 내가 풀스택을 도와가면서 하다보니 백에서 일어나는 오류는 로그로, 프론트에서도 로그로 해결하려 했다. 그런데 규모가 커지다 보니 로그가 어떻게 찍히는지도 모르겠고 많은 오류를 겪어서 차근차근 인터넷 도구의 네트워크 탭과 소스 탭을 확인하고, 로그를 찍어보고, 논리적으로 판단하여 이 부분은 문제가 없다. 혹은 이 부분에 무조건 문제가 있다. 이런 걸 잘 판단하는 능력이 길러졌다. 또 깃을 그나마 체계적으로 사용하면서 원격 저장소, 원본 저장소, 로컬 저장소의 개념을 좀 깨달을 수 있었다. 전문 프로젝트..

파일 시스템 개요유저 관점에서 파일 시스템은 다음과 같다.파일을 어떻게 이름 붙이지?권한은 어떻게 설정하지?디렉터리 트리어떻게 구성하지?시스템 입장에서는 다음과 같다.파일과 디렉터리를 어떻게 디스크 블락에 배치해서 저장해야 하지?디스크의 공간이 사용자 빈공간 이런 게 있을 텐데 이걸 효율적으로 안정적으로 잘 관리해야 한다.디스크에는 OS가 사용하는 첫 번째 블락이 반드시 존재해야 한다. OS가 쓰는 것이다.하나의 디스크를 파티션으로 나누어 관리할 수 있고 보통 아래와 같은 구조를 가진다.하나의 운영체제가 여러 파일 시스템과 여러 스토리지를 지원해야 하기에 하나의 통합된 VFS가 있다.성능상의 문제로 버퍼 캐시가 있고 그 밑에 디바이스 드라이버가 동작한다.메모리 안에서는 PCB를 따로 가지는 것 처럼 프로..