티스토리

매일을 설렘으로

검색하기

블로그 홈

매일을 설렘으로

beeehappy.tistory.com/m

하루설렘 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

[Go] leetcode 387. First Unique Character in a String Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1. Example 1: Input: s = "leetcode" Output: 0 Example 2: Input: s = "loveleetcode" Output: 2 Example 3: Input: s = "aabb" Output: -1 Constraints: 1 공감수 0 댓글수 0 2023. 2. 12.
[Go 프로그래밍] open env/dev.dev: no such file or directory open env/dev.dev: no such file or directory env로 prod, dev, test로 나누던 과정에서 godotenv.Load err가 발생했다. config.Init()으로 env file 위치를 전역 변수로 저장하고 db.Connect()를 하기 때문에 문제가 없을거라 생각했다. 하지만 error가 왜 생겼을까? 결론적으로, main함수보다 main 패키지에 있는 import 되어있는 echo_sample/domain에 있는 것을 먼저 실행하고, 그 후 main함수가 실행된다. 그래서 echo_sample/domain/dao.go가 먼저 실행되면서 에러가 발생되었다. (main함수의 config.Init()전에 실행됨) echo_sample ├── config │ └─.. 공감수 0 댓글수 0 2022. 7. 31.
[Golang] 채널(channel) 의 장점 Tuker의 Go언어 프로그래밍이라는 책을 읽으면서 배운 내용에 대해서 정리해보려고 한다. 그 중에서도 채널 관련 부분이다. 채널이라는 것은 고루틴간 메세지를 전달해주는 메세지큐이다. 고루틴은 하나의 쓰레드와 1:1 매칭되어있기때문에 쓰레드라고 생각하면 쉽다. 채널은 어떤 장점이 있을까? 채널을 통해서 뮤텍스 없이 동시성 프로그래밍이 가능하다. 어떻게 동시성 처리를 할 수 있을까? 아래와 같다. 마치 공장과도 같다. 차량 생산 공정을 예를 들어보면 세 가지 설비(고루틴)가 각 역할을 하고 있다. 바디 생산 - 타이어 연결 - 페인트 세 공정이 읽고 쓰는 메모리가 다르다는 가정 하에 서로의 공정 시간에 영향을 주지 않는다. 그렇기 때문에 Tack Time에 영향을 주지 않고 Mutex가 필요 없는 것이다... 공감수 0 댓글수 0 2022. 6. 18.
[SQL error] MySQL Handling of GROUP BY mysql sql문 오류... Error Code: 1055. Expression #2 of SELECT list is not in GROUP BY clause and contains nonaggregated column 'mydatabase.menus.price' which is not functionally dependent on columns in GROUP BY clause; this is incompatible with sql_mode=only_full_group_by 0.00035 sec 원인) GROUP BY [Column1, Column2...]의 column에 포함되어 있는 열이 아니라면 SELECT list, HAVING condition, or ORDER BY list에 비집계 열(n.. 공감수 1 댓글수 0 2022. 4. 25.
사용자 수에 따른 규모 확장성 단일 서버 모든 컴포넌트가 단 한대의 서버에서 실행되는 간단한 시스템부터 설계 해보자. 웹, 앱, 데이터베이스, 캐시 등이 전부 서버 한대에서 실행된다. 사용자의 요청이 처리되는 과정과 요청을 만드는 만드는 기기에 대해서 살펴보자 사용자는 도메인 이름을 이용하여 웹사이트에 접속한다. 이 접속을 위해서는 도메인 이름을 도메인 이름 서비스(DNS)에 질의하여 IP 주소로 변환하는 과정이 필요하다. DNS는 보통 제 3 사업자가 제공하는 유료 서비스를 이용하게 되므로 우리의 시스템 일부는 아니다. DNS 조회 결과로 IP 주소가 반환된다. (15.125.23.214) 해당 IP 주소로 HTTP 요청이 전달 된다. 요청을 받은 웹 서버는 HTML 페이지나 JSON 형태의 응답을 반환한다. 어디에서 요청이 오는가.. 공감수 0 댓글수 0 2022. 3. 31.
gdb 디버깅 https://haerinn.tistory.com/59 공감수 0 댓글수 0 2021. 12. 28.
[컴퓨터시스템] 프로세스 생성 (Process creation) 2021.12.24 - [컴퓨터시스템] - [컴퓨터시스템] 프로세스 (반효경 수업) [컴퓨터시스템] 프로세스 (반효경 수업) Process is a program in excution 프로세스의 문맥(context)이란, 프로세스의 이력과 같은 것이다. 예를 들면, 내가 어떻게 살아왔는지에 대해서 이력을 명시해놓은 것이다. 문맥(context)가 필요한 이유는 CPU beeehappy.tistory.com 이전 수업과 이어서 진행한다. 프로세스와 관련한 시스템 콜 fork( ) : create a chile (copy) exec( ) : overlay new image wait( ) : sleep until child is done exit( ) : frees all the the resoures, no.. 공감수 0 댓글수 0 2021. 12. 24.
[컴퓨터시스템] 프로세스 (반효경 수업) Process is a program in excution 프로세스의 문맥(context)이란, 프로세스의 이력과 같은 것이다. 예를 들면, 내가 어떻게 살아왔는지에 대해서 이력을 명시해놓은 것이다. 문맥(context)가 필요한 이유는 CPU수행 상태를 나타내기 때문에 멀티프로세서로 구동하는 요즘 컴퓨터는 중요하다. 문맥은 Program counter/각종 register에 저장을 하고, 보통 프로세스의 주소 공간 code, data, stack 프로세스 관련 커널 자료구조 PCB (Process Control Block) Kernel stack 프로세스의 상태 (Process state) Running : CPU를 잡고 Instruction 수행중인 상태 Ready : CPU를 기다리는 상태 (메모리.. 공감수 0 댓글수 0 2021. 12. 24.
[컴퓨터시스템] Computer structure (반효경 교수 수업) ※ CPU는 메모리랑만 일하는데, 프로그램이 실행되다가 파일을 읽거나 scanf으로 읽어와야 할 일이 있을 때 CPU는 읽어 오라고 DMA controller에게 시킨다. 주변 기기들과의 의사소통을 한다. 운영체제가 timer의 도움을 받아서 프로그램들을 처리해나간다. Time sharing. Mode bit 1 사용자 모드 2 커널 모드 mode bit이란, 제어권이 운영체제가 가지고 있는지, 사용자 프로그램이 가지고 있는지에 대한 표시. mode bit이 0 경우, 운영체제가 CPU를 들고있는 것이고 모든 명령을 할 수 있는 상태 (I/O 접근까지도) 운영체제가 사용자프로그램에 넘겨줄 때, mode bit을 1로 변경해주고 넘겨준다. mode bit이 1 경우, 사용자 프로그램이 제어권을 가지고 있어.. 공감수 0 댓글수 0 2021. 12. 24.
[컴퓨터시스템] OS란 (반효경 수업) 운영 체제는 컴퓨터 하드웨어 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층 커널은 운영체제의 핵심 부분으로 메모리에 상주하는 부분 운영 체제의 목적은 본인 프로그램만 컴퓨터를 독차지하는 것처럼 알게 하는 것이다. 운영체제의 분류 다중작업 현재는 다중 작업이 가능하다. 이는 한 명령의 수행이 끝나기 전에 다른 명령이나 프로그램을 수행할 수 있음 사용자 수 처리방식 일괄 처리 (batch processing) : 작업 요청을 일정량 모아서 한꺼번에 처리/ (단점) 완료할 때까지 기다려야함 시분할 (time sharing) : 여러 작업이 수행할 때, 운영체제가 일정한 시간 단위로 분할하여 사용 실시간 운영체제 (Realtime OS) : Deadline이 있어 정해진 시.. 공감수 0 댓글수 0 2021. 12. 24.
[컴퓨터시스템] 10장 I/O 입출력 I/O Overview Linux환경에서 모든 device들은 file로 취급한다. (우리가 열고 닫고, 읽고, 쓰는 file) /dev/sda2 (/usr disk partition) /dev/tty2 (terminal) 심지어 커널 (kernel) 조차 파일로서 취급 /boot/vmlinuz-3.13.0-55-generic (kernel image) /proc (kernel data structures) ※ simple interface - open() and close() - read() and write() - lseek() : indicates next offset into file to read or write File Types Regular files : (text files/Binary .. 공감수 0 댓글수 0 2021. 12. 22.
[C언어] strcpy/strcat 함수 익히기 strcpy/strcat 함수 strcpy(char* dest, const char* src) : dest에 src를 한자한자 덮어쓰기한다. strcat(char* dest, const char* src) : dest 뒤에 src를 붙인다. 코드 확인 #include #include int main(void) { char arr1[100]; char arr2[100]; char arr3[100]; // arr1 선언 strcpy(arr1, "hello, i am array"); printf("%s\n", arr1); // arr2 선언 strcpy(arr2, "This is following text"); printf("%s\n", arr2); // arr1 = arr1 + arr2 strcat(arr1.. 공감수 1 댓글수 0 2021. 12. 20.
[Week 07] web-proxy lab Week 07 주제 : web-proxy lab ▶ 클라이언트의 request를 받고, reponse를 내어주는 웹서버를 만들어보고 웹서버 기능들을 알아보자 ▶ tiny 웹서버를 완성하기 (컴퓨터시스템 교재 기반) ▶ 숙제 문제 풀기 (11.6c, 7, 9, 10, 11) ▶ 프록시 과제 도전 (proxy.c 완성) 키워드 BSD소켓 TCP/UDP IP HTTP file descriptor DNS 11. 1 클라이언트-서버 프로그래밍 모델 - 서버: 서비스를 제공하는 프로그램 - 클라이언트: 서비스를 요청하는 프로그램 - 서버가 제공하는 서비스 : 웹 서버, FTP 서버, 이메일 서버 - 클라이언트/서버와 호스트와의 관계: 클라이언트와 서버는 종종 별도의 호스트에서 돌아가며, 통신한다. 호스트에겐 단지 .. 공감수 1 댓글수 0 2021. 12. 16.
[컴퓨터시스템] 가상메모리 (Virtual Memory) 목차 가상메모리란 무엇이고, 왜 필요한가 가상메모리 주소 공간 (Virtual Address Space, VAS) Stack Heap Data Code, Text 가상 메모리 (Virtual Memory) 실제 메모리 크기와 상관없이 메모리를 이용할 수 있도록 가상의 메모리 주소를 사용하는 방법이다. 예를 들어, 100MB 메모리 크기에서 200MB 크기의 프로세스를 수행할 수 있도록 하는 것이다. 왜 가상 메모리 필요한가? 한 마디로, 물리적 공간의 제한을 극복하기 위해 만들어진 기술이다. 프로그램을 동작하기 위해서는 실제 프로그램 파일에 메모리에 할당되어 프로세스가 처리된다. 하지만 실제 메모리의 용량은 비싸고 제한적이다. 그래서 보조 기억장치 (HDD, SSD 등)로 메모리 확장을 하여 사용하게 된.. 공감수 2 댓글수 0 2021. 12. 15.
[Week 06] Malloc Lab Week 06 주제 : Malloc 함수 만들기 ▶ 동적 메모리 할당 방법 직접 개발을 하며, 메모리, 포인터 개념 알기 > malloc, realloc, free 함수를 구현하자 ▶ implicit 방법으로 구현하기 (explicit, seglist, buddy system 방법도 여유되면 하기) 키워드 시스템 콜 (system call) 더보기 System call이란, 응용프로그램이 운영체제의 커널이 제공하는 서비스를 사용할 수 있게하는 방법이다. 예를 들어, 응용프로그램이 파일 시스템을 직접적으로 접근하는게 불가능하다. 그래서 응용프로그램은 커널에 접근하여 파일 시스템을 호출하는 방법을 사용한다. (sbrk/mmap 등) 데이터 세그먼트 (data segment) 더보기 메모리 단편화 (Memor.. 공감수 1 댓글수 0 2021. 12. 9.
[C언어] Red-Black Tree Red-Black Tree 개요 Self-balancing binary search tree ( tree의 height를 h = log2(N)으로 유지) 이 외에도 AVL Tree, B-tree 등이 있다. BST (Binary Search Tree)와 동일한 원리 (key 대소 관계로 구성) Red-Black tree의 경우, Node color / BH (black height)로 균형 유지 시간복잡도상 항상 O(logN)을 유지한다. (탐색/삽입/삭제) Tree의 특징 아래의 특징은 그냥 균형을 맞추기 위해 필요한 조건이라고 보면 좋을 듯 하다. (그냥 받아들이면 된다.) Red/Black Property: Every node is colored, either red or black. Root Pr.. 공감수 2 댓글수 0 2021. 12. 9.
[C언어] typedef/enum typedef 함수 (형 재정의) 특정 element에 대해 미리 type (int, long, double, pointer 등) 지정해서 사용하는 함수이다. 문법은 다음과 같다. typedef type element 장점 : 이식성과 수정 효율성이 좋다. 예를 들어, 프로그래밍 컨셉이 바껴 특정 element의 type을 int형 -> double형으로 변경할때 // typedef 사용 예시 typedef int key_t; // 포인터형도 typedef를 사용해서 *없이 선언할 수 있다. typedef int* intPtr; intPtr p, q; 열거형(enum) 변수가 갖는 값에 의미를 부여해 프로그램 가독성을 높임 컴파일러는 열거형 멤버들을 정수형 상수로 인식 (문자도 indexing으로 사용 .. 공감수 1 댓글수 0 2021. 12. 8.
[21.12.08] 공부할 거리 C언어 공부 Linux/gcc 사용법 익히기 RB tree 이론 malloc/free 사용법 파악 RB tree 구현 linked list를 이용한 list, queue, tree 구현 등 몇 가지 예제를 풀어가며 숙달하기를 추천합니다. 공감수 1 댓글수 0 2021. 12. 8.
[C언어] stack 자료 구조 구현 C를 활용한 stack 자료 구조 구현 전체 구조 #include #include #define SIZE 100 // stack struct 구성 typedef struct stack { // arr[SIZE], top int arr[SIZE]; int top; } stack; // init 함수 void init(stack *s) { s -> top = -1; // stack에 초기상태 -1, Push해서 data 들어오면 0부터 index시작 } // is_empty 함수 구성 int is_empty(stack *s) { if (s->top == -1) return 1; return 0; } // is_full 함수 구성 int is_full(stack *s){ if (s->top == SIZE - .. 공감수 1 댓글수 0 2021. 12. 4.
[Algorithm] 비트 마스킹 이란? 비트 마스크 (BitMask)라는건 알고리즘이라기보다 하나의 테크닉이다. 보통 DFS, BFS 알고리즘을 사용할 때, visit 방문 처리하는 이력을 남겨 거슬러 올라가는 행위를 하지 않게 한다. 이를 하나의 정수로 가능하게 한다. 보통 문제를 풀 때 DP에 남길 때 방문 이력까지 한 번에 넘겨야 할 때, 좋은 방식인 것 같다. 관련 예제로, 백준 2098 외판원 순회가 있다. visit | (1 공감수 1 댓글수 2 2021. 11. 29.
[Python] 백준 14501번 퇴사 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일TiPi 3 5 1 1 2 4 2 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다. 상담을 .. 공감수 0 댓글수 0 2021. 11. 27.
[Python] 백준 1149번 RGB거리 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 .. 공감수 0 댓글수 0 2021. 11. 26.
[자료구조] 이진 트리 및 이진 검색 트리 이진 트리 (Bianary Tree) 배열, 링크드리스트, 스택, 큐와 같이 일직선 개념의 자료구조가 아니라 비선형 자료구조인 부모-자식 개념을 가지는 자료구조이다. 데이터를 트리 구조로 배열 할 때 트리 맨 위에있는 노드를 루트 노드라고합니다. 전체 트리에 대해 하나의 루트 만있을 수 있습니다. 루트 노드를 제외한 모든 노드에는 노드 위쪽에 하나의 가장자리가 있습니다. 이를 부모 노드라고합니다. 부모 코드 아래의 노드를 자식 노드라고합니다. 각 상위 노드에는 최대 2 개의 하위 노드가있을 수 있습니다. 왼쪽 자식 노드와 오른쪽 자식 노드라고합니다. 자식 노드가없는 노드를 리프 노드. 이진 검색 트리 (binary search tree)란, 이진 탐색 트리는 기본적인 특징은 이진 트리와 같지만 하나 다른.. 공감수 0 댓글수 0 2021. 11. 25.
[Algorithm] 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) + 예제 그래프로 탐색하는 방법에는 두 가지가 있다. DFS, BFS. 1) 깊이 우선 탐색 (DFS) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. - 구현 : 스택 또는 재귀함수로 구현 -> 둘 중에 어떤 구조로 짜는지에 대한 장단점은 무엇일까? 2) 너비 우선 탐색 (BFS) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. - 구현 : 큐를 이용해서 구현 3) 활용 문제 유형 및 응용 - 그래프의 모든 정점을 방문하는 것이 중요한 문제 => DFS, BFS 둘 다 동일 (∵모든.. 공감수 0 댓글수 0 2021. 11. 23.
[Python] 백준 21606번 아침 산책 문제 아침 산책을 즐기는 서현이는 서울과학고에 입학해서도 아침 산책을 즐기려고 합니다. 서현이는 산책을 위해 서울과학고의 지리를 분석했고, 그 결과 서울과학고를 N$N$개의 장소를 N−1$N-1$개의 길이 잇는 트리 형태로 단순화시킬 수 있었습니다. 트리 구조이므로, 모든 장소를 몇 개의 길을 통해 오고갈 수 있습니다. 아침 산책은 시작점과 도착점을 정하고, 시작점에서 도착점까지 트리 위의 단순 경로(같은 점을 여러 번 지나지 않는 경로)를 따라 걷게 됩니다. 트리 위의 두 점 사이의 경로는 유일하므로 시작점과 도착점이 정해지면 경로는 유일하게 결정됩니다. N$N$개 장소 중에 일부 장소는 실내이며, 나머지 장소는 실외입니다. 서현이는 산책을 시작하기 전부터 운동을 하는 것을 원치 않기 때문에, 산책의 .. 공감수 0 댓글수 0 2021. 11. 21.
[Python] 백준 2573번 빙산 문제 지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다. 2 4 5 3 3 2 5 2 7 6 2 4 그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에.. 공감수 0 댓글수 0 2021. 11. 21.
[Algorithm] 다익스트라 알고리즘 다익스트라 알고리즘이란 매 상황마다 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하는 것으로 그리디 알고리즘으로 분류된다. 단계를 거치며 한 번 처리된 노드의 최단거리는 고정되어 더 이상 바뀌지 않는다. 그래서 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다. 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장됩니다. 완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야합니다. 구현 import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().spli.. 공감수 0 댓글수 0 2021. 11. 21.
[Python] 백준 14888번 연산자 끼워넣기 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 식의 계산은 연산자 우선.. 공감수 0 댓글수 0 2021. 11. 20.
[Python] 백준 1717번 집합의 표현 문제 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와.. 공감수 0 댓글수 0 2021. 11. 20.
[Python] 백준 11725 트리의 부모찾기 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 나의 풀이 (시간 초과) 왜 시간 초과가 났을까? While문 안에 Not in 이라는 연산자 역시 O(n)의 시간 복잡도를 가지고 있으니, O(n2)가 된다. i.. 공감수 0 댓글수 0 2021. 11. 19.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.