본문 바로가기

전체 글

 (336)
unordered_map을 이용한 노드 개수 최적화 알고리즘 문제를 풀다가 이런 문제를 발견했다. 다익스트라 문제인데 노드는 50개 뿐이지만 노드의 번호 범위가 무려 1~10억이었다. 다익스트라는 dp기반이기 때문에 dp[노드의개수]로 맞춰놓는 것이 일반적이다. 그런데 dp[10억]은 엄청난 메모리 낭비를 초래한다. 그래서 사용할 수 있는 방법이 바로 unordered_map을 이용한 노드 개수 최적화이다. unordered_map는 자동으로 키값으로 정렬하는 맵과 달리 정렬하지 않는 해싱기법이다. unordered_map nodes; int get_idx(int v) { return nodes[v]; } 먼저 맵을 선언해두고 인덱스를 겟할 수 있는 함수를 만들어준다. for (int i = 0; i < N; i++) { if (nodes.count(원래..
백준 2357 최솟값과 최댓값 (c++) https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 세그먼트 트리는 원래 O(N)이상 걸리는 작업들을 log 시간으로 해결할 수 있는 자료구조이다. 코딩테스트에 출제된다면 아마 모르면 맞아야지 문제이기 때문에 정답률이 처참할 것으로 예상된다. 하지만 세그먼트 트리를 응용까지 해서 풀어야하는 테스트는 아마도 카카오 네이버를 제외하면 거의 없을 거라 생각한다. 세그먼트 트리는 1. 세그먼트 트리 빌드 2. 업데이트..
백준 5639번 - 이진 검색 트리 (c++) https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 이진검색트리는 세가지 검색법이 있다. 1. 전위순회 - root -> left -> right 2. 중위순회 - left -> root -> right 3. 후위순회 - left -> right -> root 문제에서는 전위순회로 들어온 값들을 후위순회한 값으로 나타내라고 한다. 처음 생각은 다시 트리를 구성해서 전위순회해야하는건가 싶었는데 불가능하지는 않겠지만 비용이 많이들고 굳이 ..
소프티어 - 함께하는 효도(C++) https://softeer.ai/practice/7727 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 소프티어에서는 처음 문제를 풀어보는데 나쁘지 않은 문제인 것 같다. dfs 백트래킹 문제에 더불어 재귀적인 요소를 포함하고 있었다. 내 풀이가 정해인진 모르겠는데 일단은 맞았다. 아이디어는 이러하다. 문제를 파악했을태니 이 각 친구들은 각자 나무에서 열매를 따는데, 만약 A가 이미 땄다면 B는 거기서 열매를 딸 수 없다. 이 조건 때문에 문제가 까다로워진다. 그래서 난 visited배열을 3차원으로 설정하고, A가 열매를 다 따면 B가 열매를 따며 조절하는데 각자 방문 배열이 존재하면서 다음으로 갔을 때 다른 차원의 배열이 만약 방문표시 되어있다면 열매를 따지 않도록 조절했다...
SWEA - 영어 공부(C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXNQOb3avD0DFAXS SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 이해 자체는 어렵지 않다. 만약 답을 구할 수 있도록 러프하게 구해보면 1 3 4 5 라고 들어온다고 가정할 때 1에서 시작해서 N 모두 보기 , 2에서 시작해서 모두보기 해서 총 N * N의 시간이 걸리도록 하는 것은 쉽다. 그러나 20만 * 20만 = 4천억으로 어림도없다. 그래서 처음 생각해낸 것은 1 3 4 5에서 1에서 최고수를 구하고 3에서 최고수를 구하는 것을 이분탐색으로 찾아내는..
Docker Container - VScode 연동(컨테이너 내부 파일 VSC에서 편집) 도커 내부 파일을 작업해야할 일이 생기면 데스크탑에서 코드 편집기를 제공해주긴 하지만 아무래도 불편하다. 그래서 VSC에서 작업하는 것이 일반적이다. 먼저 Docker, Cocker 컨테이너를 사용하고 있다는 가정 하에 진행한다. 이걸 설치하면 VSC 좌측 사이드바에 이게 생길 것이다. 위 아이콘을 클릭하면 사진처럼 현재 자신의 도커에서 실행되고 있는 컨테이너들이 보일 것이다. 여기서 Attach in New Window를 클릭하면 새 창이 열리면서 vscode-server이 자동으로 설치된다. 새 창의 Remote 아이콘을 누르면 저렇게 초록색으로 컨테이너에 접속되었다는 표시가 된다. 이제 상단의 파일탐색에 원하는 경로를 집어넣으면 된다. 나는 워드 프레스를 공부중이어서 워드프레스 파일들이 있는 곳인 ..
백준 1194번 - 달이 차오른다, 가자. (C++) https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net bfs 최단거리 문제임은 자명한데, 주어진 다른 조건이 있어 쉽지 않은 문제이다. 문제를 보며 깨달아야하는 것은 들고있는 열쇠마다 타일에 접근하는 것의 의미가 다름을 깨달아야한다. 즉 2,2 가 a라고 할 때 열쇠 a,b,c를 가지고 있는 것과 열쇠 a만을 가진 것은 의미가 전혀 다르다는 의미이다. 그래서 bfs를 돌 때 각 bfs 노드들은 x,y 말고도 현재 열쇠의..
기존 MySQL을 사용하고 있을 경우 Docker Mysql 포트 충돌 컨테이너 생성 중, 3306:3306 사용했을 때 오류 내용 (HTTP code 500) server error - Ports are not available: exposing port TCP 0.0.0.0:3306 -> 0.0.0.0:0: listen tcp 0.0.0.0:3306: bind: Only one usage of each socket address (protocol/network address/port) is normally permitted. 말그대로 3306포트는 오직 하나의 소켓만이 사용할 수 있는데 이미 점유중이라는 의미이다. netstat -ano gitbash 혹은 cmd(관리자모드)에 들어가 위 명령어를 실행하면 현재 사용중인 포트 번호들을 볼 수 있다. 3306포트는 6036..

티스토리툴바