내가 그때 이걸 알았더라면

1. 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 분석 및 아이디어 이 문제에서 까다로웠던 점은 트리에서 연결된 간선이 주어질 때 무방향으로 주어진다는 점이다. (누가 부모인지 알 수 없음) 그래서 필자는 트리를 루트부터 시작해 dfs로 탐색하면서 부모->자식 노드 연결을 끊어 주는 방식을 생각했다. 처음에는 인접 행렬 방식으로 무식하게 구현했는데, 이러면 답은 구할 수 있지..

** 주의 PS를 할 때 C++에서 list 자료형은 인덱싱을 할 수 없다는 치명적인 결함 때문에 거의 쓰이지 않습니다. 이 글에서는 list 자료형을 사용할 수 있는 방법을 소개했지만, PS를 할 때는 다른 라이브러리를 사용하는 것을 추천드립니다. 1. 개요 알고리즘을 풀 때 만약 요소를 순서대로 조회하면서 인덱싱을 하려면 std::vector 라이브러리나 std::deque, std::map (포인터로 iterator 생성가능) 등의 자료형을 사용할 것이다. 하지만 만약 시퀀스 중간에서 삽입, 삭제가 일어나야 할 경우, 위에 나온 자료형 모두 사용하기가 애매해진다. (map은 확인 필요) - 특히, std::vector는 push_back, pop_back 등의 메소드는 amortized O(1)로 ..

문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과..

참고한 블로그 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html [알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 알고리즘을 풀다 내가 삽입 정렬도 구현하지 못하는 것을 발견했고, 잊지 않고자 기록한다... 먼저 삽입 정렬이란 다음과 같다. (오름차순 정렬이라고 가정) https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC 삽입 정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 삽입 정렬(揷入整列..

> 문제 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자. > 풀이 문제 자체는 보기엔 간단해 보이지만, 1~n까지의 모든 문자열 각각에 대해 각 자리의 숫자를 카운트 해주면 시간초과가 나는 문제이다. 시간복잡도만 보자면 O(nlogn)인데 문자열 처리에 걸리는 시간에 n 0은 100~109, 200~209, .., 54200~542..

> 문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i 풀이 idea 1) m..

Node.js는 크롬의 v8엔진 기반 javascript 런타임이다. Node.js에서 제공하는 라이브러리인 express.js를 사용하면 웹 서버를 쉽게 구축할 수 있다. node.js 프레임워크를 배우며 공부한 내용을 정리하고, 관련 지식을 찾는 사람에게도 내용을 공유하기 위해 해당 주제에 대해 작성해보기로 했다. 1. 폴더 및 package.json 설정 Node.js 프로젝트를 시작하려면 먼저 폴더를 만들고, 거기에 사용할 라이브러리(모듈)을 설치해야 한다. -> BackEnd Study 폴더를 만들어 주고, 거기에 npm init 명령어를 입력해준다. npm init 명령어를 입력하면 cmd창에 이것저것 이름을 설정해주라는 항목이 뜨는데, 일단 특별한 설정을 해주지 않을 거면 전부 enter 키..

참고한 블로그 - UTF-8 인코딩 설정: https://suzxc2468.tistory.com/174 이클립스(Eclipse) 한글 깨짐 - "UTF-8" 인코딩 설정 개념 인코딩이라는 개념과 친하지 않은 뉴비들을 위한 아주 간략한 설명을 하자면... 어딘가에서 소스를 가져와서 이클립스에 갖다 붙혀봤더니, 한글이 깨져서 나와요. or HTML, JSP에서 작성 된 한 suzxc2468.tistory.com - 콘솔 출력에서 MS949 인코딩 설정 https://error-nono.tistory.com/entry/%EC%9D%B4%ED%81%B4%EB%A6%BD%EC%8A%A4-%EC%BD%98%EC%86%94-%ED%95%9C%EA%B8%80%EA%B9%A8%EC%A7%90-%ED%95%B4%EA%B2..

참고한 블로그 : https://www.delftstack.com/ko/howto/cpp/how-to-convert-int-to-string-in-cpp/ C++에서 Int를 문자열로 변환하는 방법 이 기사에서는 C++에서 정수를 문자열로 변환하는 방법을 보여줍니다. www.delftstack.com https://godog.tistory.com/entry/C-string-to-int-int-to-string-%ED%98%95%EB%B3%80%ED%99%98-%ED%95%98%EA%B8%B0 C++ string to int, int to string 형변환 하기 C++ string to int, int to string 형변환 하기 , string 문자열에서 숫자만 선택해 형변환 int stoi (con..

참고한 블로그 : https://offbyone.tistory.com/437 Microsoft Visual Studio Code에서 Java 개발 환경 설정하기 이전에 Visual Studio Code를 설치해보았습니다. Visual Studio Code를 설치만 했을때 할 수 있는 작업이 없더군요. 필요한 언어에 대한 확장팩을 설치해야 더 나아갈 수 있었습니다. 이번에는 Visual Studio Co offbyone.tistory.com 목차 jdk 설치 후 jdk 폴더 환경변수 추가 해주기 vscode에서 java extension pack 설치 해주기 개발 폴더 만들고 java 프로젝트 만들어주기