분류 전체보기 89

[TIL][Krafton Jungle] 4주차 - (4) : 스터디 리뷰 & 세그멘트 폴트 문제 해결

오늘은 코알라(코딩 알고리즘 라이브) 스터디를 처음 시작한 날이다. 스터디에서 푼 문제에 대한 리뷰와 세그멘테이션 폴트를 해결한 내용을 작성하겠다. 코알라 스터디 코딩 알고리즘 공부를 계속하고 싶어서 정글 교육생들과 함께 스터디를 만들었다. 매주 일요일에 3문제씩 실제 코테처럼 응시한 뒤, 각자 본인이 문제에 대한 접근법을 설명하는 방법이다. 알고리즘 문제 푸는 능력을 빠르게 키우는 건, 잘 하는 사람들의 문제 접근 방법을 들여다 보는 것이라 생각한다. 그래서 알고리즘에 익숙한 사람들과 같이 어떻게 접근했는지 방법을 들어보면서, 내 실력도 빠르게 키울 수 있었으면 좋겠다. 그리고 또 알고리즘 실력이 부족하다고 생각되서 참여하기가 꺼려지는 분들은 점수 매기는 거 아니니까 많이 들어와서 같이 실력 키워봅시다..

Jungle 2023.11.05

[TIL][Krafton Jungle] 4주차 - (3) : RB Tree 공부 및 실제 구현

오늘은 RB 트리의 삭제 연산과 구현을 실제로 진행해보겠다. 그전에 make 파일에서 발생한 오류부터 해결해 보자. Segmentation fault 세그멘테이션 폴트(Segmentation fault)는 프로그램이 잘못된 메모리 주소에 접근하려고 할 때 발생하는 오류이다. 이는 일반적으로 배열의 범위를 초과하거나 널 포인터를 참조하는 등의 상황에서 발생할 수 있다. 현재 RB 트리의 선언, 단일 노드의 삽입과 탐색, 삭제까지 구현을 마치고 올바르게 작동 된다는 것을 확인했다. 근데 test_find_erase() 함수에서 for문으로 arr[i]의 값들을 각각 insert하는 상황에서 Segmentation fault가 발생한 상황이다. 문제는 이 함수를 진입하지도 못하고 있는 상황이라는 것이다. 아마..

Jungle 2023.11.04

[TIL][Krafton Jungle] 4주차 - (2) : 포인터와 디버깅

C컴파일/디버깅/make 사용법 학습 make 사용법을 학습하라는데, make가 뭔지 모른다.. 그래서 찾아봤다. make는 C언어 프로젝트를 빌드하고 컴파일하는 빌드 자동화 도구이다. 여러 파일간의 종속성을 관리하면서, 특정 소스 코드만 변경될 경우 필요한 파일만 다시 컴파일하면서 빠르게 재빌드 할 수 있게 해준다. 다음은 간단한 C 프로젝트를 위한 Makefile의 예시이다. CC = gcc CFLAGS = -Wall -O2 TARGET = myprogram SOURCES = main.c helper.c OBJECTS = $(SOURCES:.c=.o) $(TARGET): $(OBJECTS) $(CC) $(CFLAGS) -o $(TARGET) $(OBJECTS) %.o: %.c $(CC) $(CFLAG..

Jungle 2023.11.04

[TIL][Krafton Jungle] 4주차 - (1) : RB Tree 구현 시작

금일은 새로운 발제 내용이 나오는 목요일이다. 새로운 조가 형성되고 새로운 과제가 주어지는데, 항상 설레는 날인 것 같다. 오전에 시험을 봤는데 어제 공부한 알고리즘과 비슷한 문제가 나와서 시간이 부족해 다 풀진 못했지만, 나름 목표 만큼은 맞춰서 뿌듯했다. 아무튼 이번주는 C언어로 돌입한다. 이번주 과제는 알고리즘 문제 풀이가 아닌, Python에서 쉽게 가져다 쓴 자료구조를 직접 C 코드로 구현하는 것이다. 구현 자료구조는 블랙레드 트리 (BR tree). 먼저 이 자료구조가 어떻게 생겨먹은 놈인지 뜯어보고, 어떻게 구현할지를 생각해봐야 하기 때문에 코어타임 때 이론 내용 공부를 통해 부족한 부분을 채워나가기로 했다. 그리고 환경 설치를 위해서 터미널을 다뤘는데, 터미널 관련 명령어들에 대한 자료가 ..

Jungle 2023.11.02

[TIL][Krafton Jungle] 3주차 - (7) : DP + 그리디 문제풀이 마무리

3주차 마지막 날이 다가왔다. 남은 문제를 오늘 전부 풀겠다. (도전빼고.) BaekJun - #11053 : 가장 긴 증가하는 부분 수열 (DP) 출처 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제를 처음 접했을 때, DP적 접근이 아니라 문제를 해결하는 방식을 생각하다가 뒤에서부터 result에 append하고 만약에 다음에 append할 수의 값이..

Jungle 2023.11.01

[TIL][Krafton Jungle] 3주차 - (6) : DP : 행렬 체인 / 프로시저 CS

오늘은 컴퓨터 시스템과 관련된 CS 정리를 퀴즈 문제와 같이 정리하겠다. 그전에 DP의 행렬 체인 알고리즘을 공부하고 해당 문제를 푸는 과정을 정리하겠다. DP : 행렬 체인 알고리즘 행렬 체인의 연산은 몇번째의 행렬을 먼저 계산하는가에 따라 연산의 횟수가 달라진다. 따라서 주어진 행렬의 체인을 최소로 연산하는 횟수를 구하는 알고리즘을 공부해보자. `Introduction to Algorithm` 책에 해당 로직에 대한 설명이 나와있다. 매우 이해하기 힘들지만, 간단히 정리해 보겠다. 행렬을 쭉 나열하고 그 행렬의 열이 체인형태로 (NxM , MxP) 나열되어 있어서 곱을 순서대로 할 수 있다. Ai = pi-1 x pi 의 차원을 가진다. (이부분이 어려울 수 있는데, A의 i번째가 3x6 매트릭스라면..

Jungle 2023.11.01

[TIL][Krafton Jungle] 3주차 - (5) : 신입사원 문제 + 플로이드 워셜 + LCS

BaekJun - #1946 : 신입사원 (그리디 탐색법) 출처 : https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 오늘은 신입 사원을 풀었다. 문제 이해가 조금 어려운데 풀어서 얘기해보면 실기, 필기 두개의 시험을 등수로 매기는데, 특정 A 라는 사람이 어느 누군가보다 실기도, 필기도 등수가 낮다면 그사람은 탈락된다. 문제를 이해하는데 시간이 좀 걸리긴 하지만, 문제가 이해됬다고 하면 이제 어떻게 풀어야할지 고민을 해보자..

Jungle 2023.10.30

[TIL][Krafton Jungle] 3주차 - (4) : DP 알고리즘 적용의 연습

현재 컴퓨터 시스템을 공부하고 있는 내용은 이해할 내용이기보다는 어셈블리어의 인스트럭션 기호의 정의와 해석적인 파트를 읽고 있어서, 따로 정리하지는 않겠다. 대신 DP 알고리즘을 이용한 간단(?)하지만, 코드화(규칙화)하기 힘든 문제를 통해서 DP 문제 풀이에 조금 더 익숙해져보자. BaekJun - #9084 : 동전 (DP) 동전 0 이랑 비슷해 보이지만 이문제는 DP 문제이다. 동전 단위가 주어지고 해당 값을 만들 수 있는 경우의 수를 출력하는 문제인데, 문제 아이디어를 떠올리기가 역시 아직 쉽지 않다. 처음엔 01타일 문제를 먼저 떠올렸다. 가장 최근에 푼 01타일 문제를 겪은 후에 '베이스케이스를 찾아서, 그 케이스를 통한 확장에 대한 문제가 DP구나.' 라고 생각했었는데, 이 문제를 통해서 ..

Jungle 2023.10.29

[TIL][Krafton Jungle] 3주차 - (3) : 그리디 + DP / 컴퓨터 시스템

오늘은 어제 하던 Greedy를 문제에 적용하면서 경험한 서사와 컴퓨터 시스템 약간을 추가해서 작성해 보겠다. BaekJun - # 11047 : 동전 0 (그리디 탐색법) 출처 : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전 0의 문제를 처음 풀려고 생각했을 때는, 굉장히 쉽다고 생각했다. 거스름돈을 계산할 줄 아는 사람이라면 코드를 짜는 건 어렵지 않다. 하지만 문제는..

Jungle 2023.10.29

[TIL][Krafton Jungle] 3주차 - (2) : Knapsack Problem / 컴퓨터 시스템 약간

오늘의 내용은 어제의 동적 프로그래밍 공부의 연장선인 Knapsack Problem에 대해 알아보고, 컴퓨터 시스템 정리를 간단히만 다뤄보겠다. Knapsack Problem 배낭 문제라고도 하는 kapsack 문제는 정해진 무게 한도가 있는 배낭에다 물건을 담는데, 가치가 가장 높게 담는 경우를 찾는 문제이다. 이는 모든 경우를 다 셀 경우 특정 물건을 담는다 vs 안담는다로 하여 2의 n(물건의 수)승의 탐색이 걸린다. 따라서 이는 효율적인 탐색법이 필요한데 접근법은 다음과 같다. 1. 만약 물건의 무게가 배낭의 한도보다 크다면 continue, 2. 한도보다 작다면 2중 배열(dp)에 세로줄은 담은 물건의 수(i), 가로줄은 배낭의 한도무게(w)로 설정하여 선언한 뒤 그 배열안에 최대의 가치를 저장..

Jungle 2023.10.27