본문 바로가기

Programming15

Radix Tree user level 구현과 커널 소스코드(ver 4.18)와의 비교 - Radix Tree커널 내부 Key-Value 타입의 데이터 구조로, page caching에 이용되는 자료구조이다.리눅스 커널 4.19버전부터 xarray로 대체되고 있다.Tree라기보단 extensible array 구조라고 볼 수 있다.- Radix Tree 기본 구조 각 노드는 64개(또는 48개)의 자식을 가지며, 최상위 노드를 가리키는 Root 구조체가 있다.Internal node의 슬롯은 자식 노드에 대한 포인터, leaf node의 슬롯은 저장된 값(item)에 대한 포인터값을 가진다.각 노드는 (shift,offset)값으로 위치를 알 수 있다. shift는 노드의 높이, offset은 부모 노드의 몇번째 슬롯인지를 알려준다.- Radix Tree 함수- extend(index)처음.. 2021. 1. 12.
[BOJ 10942] 팰린드롬? > 문제 출처 https://www.acmicpc.net/problem/10942 > 문제 설명 N개(1 ≤ N ≤ 2,000)의 자연수(K ≤ 100,000)로 이루어진 수열이 주어졌을 때, M개의 구간(M≤ 1,000,000)을 입력받는다. 이 때 입력받은 각각의 구간이 팰린드롬이면 1, 팰린드롬이 아니면 0을 출력한다. > 접근 방법 질문의 개수(M)이 최대 1,000,000개이기 때문에 모든 상황에서의 dp값을 구한 후 리턴하는것이 효율적이라 생각했다. 그래서 수열의 값을 입력받으면서 모든 sub-problem을 계산했다. i번째 값을 입력받으면 dp[i-1][i], dp[i-2][i], ... dp[1][i]를 계산하는 방식으로 설계했으며, 총 시간복잡도는 O(N^2)이라고 생각된다. 점화식(a.. 2020. 9. 2.
[BOJ 1912] 연속합 > 문제 출처 https://www.acmicpc.net/problem/1912 > 문제 설명 N개(1 ≤ N ≤ 100,000)의 정수(-1000 ≤ K ≤ 1000)로 이루어진 수열이 주어졌을 때, 연속된 몇 개의 수를 선택하여 구할 수 있는 합중 가장 큰 값을 구하는 문제. > 접근 방법 전형적인 DP(Dynamic Programming)문제이다. 처음엔 나름 생각한다고 신박한 방법을 썼는데 생각해보니 수열을 입력받으면서 바로 처리가 가능한 문제였다. i번째 원소가 입력될 때, x~i까지의 최대합(sum[i-1] + input[i])과 input[i]값 중 큰 값을 sum[i]에 담는다. 이 과정에서 max_sum을 갱신해주며 리턴한다. 시간 복잡도는 O(N)으로 생각된다. > CODE /* #pr.. 2020. 8. 26.
개구리 뛰기 (Frog Leaps) > 문제 출처 https://www.codeground.org/practice/ 11 SCPC_2015_Online Frog Leaps > 문제 설명 N개( 접근 방법 K값이 좌표 이전에 주어진다면 좌표 입력수준에서 편하게 풀 수 있었는데 좌표입력 후 K값이 주어지는거라 입력 후 처리를 할 수 밖에 없었다. 일단 최근 입력된 돌의 좌표를 입력받는 pos, pos부터 새로 입력된 좌표까지의 거리를 계산한 dist벡터를 선언하였다. 또한 개구리가 끝까지 갈 수 있는지 판단하기 위해 dist값의 최대값을 구해두었다. (이웃한 돌 사이의 거리가 K보다 큰 곳이 하나라도 있다면 개구리는 끝까지 가지 못한다.) 이제 max_dist값이 K이하라면 최소 횟수를 구할 수 있다. 시작점부터 K거리 이내의 가장 먼 돌을 .. 2020. 8. 15.
방 속의 거울 (mirror in the room) > 문제 출처 https://www.codeground.org/practice/ 12 SCP_2015_Online Mirror in the Room > 문제 설명 정사각형 크기(N 접근 방법 구조체로 거울 하나에 대한 정보(거울의 모양-mode, 방문여부-isVisited)를 정하였고, 클래스 선언으로 방에 대한 정보(크기, 위치별 거울의 모양)을 확인할 수 있게 만들었다. 이제 0,0부터 지나친 거울을 컨트롤 하면 되는데, 거울의 모양만으로는 다음 좌표를 알 수가 없다. 그래서 빛의 방향을 이용하여 함께 계산을 해줘야하는데 4방향을 고려하여 if문을 넣기에는 런타임, 코드 가독성의 문제가 생긴다고 생각했다. 빛의 진행 방향을 x,y방향으로 나눈 뒤 직접 그려보며 패턴을 찾아보니 다음과 같았다. 거울이 .. 2020. 8. 12.
시험 공부 (Studying for Exams) > 문제 출처 https://www.codeground.org/practice/ 3 Practice Studying for Exams > 문제 설명 초등학생인 정우는 시험 기간을 맞아 공부를 시작해야 한다. 정우가 다니는 학교에선 총 N개의 과목에 대해 시험을 보는데, 시간이 부족한 정우는 그 중 K개의 과목만을 골라서 공부할 수 있다. 정우는 매우 특이한 학생이라서 어떤 과목을 공부한다면 그 과목에 대해선 무조건 같은 점수를 받게 된다고 한다. 정우는 시험 점수 총합을 최대화하기 위해 K개의 과목을 골라야 한다. 하지만, 모든 과목을 공부할 시간이 없는 정우는, 당신에게 "최대 합계 점수"를 받을 수 있는 K개의 과목을 골라달라고 한다. K개 과목을 골랐을 때 정우가 받을 수 있는 "최대 합계 점수"를.. 2020. 8. 11.
프로그래밍 경진대회 (Programming Contest) > 문제 출처 https://www.codeground.org/practice/ 2 Practice Programming Contest > 문제 설명 삼성 프로그래밍 경진대회는 권위 있는 대회이다. 대회는 여러 라운드를 통해서 진행되며, 모든 라운드에 총 N명의 응시자가 있다. 각 라운드 별로 1등은 N점, 2등은 N−1점 순으로 순차적으로 점수를 얻게 되고 뒤에서 2등은 2점, 뒤에서 1등은 1점을 얻게 된다. 그리고 각 라운드 별로 동점자는 없으며, 각 라운드 마다 받은 점수의 합이 제일 높은 사람이 우승하게 된다. 마지막 라운드 직전까지의 점수 합이 주어졌을 때, 우승할 가능성이 있는 응시자의 수를 구하는 프로그램을 작성하시오. > 접근 방법 마지막라운드에서 점수차가 가장 많이 줄어드는 경우는 현재.. 2020. 8. 10.
숫자 골라내기 (Picking Out Numbers) > 문제 출처 https://www.codeground.org/practice/ 1 Practice Picking Out Numbers > 문제 설명 N개의 10진수를 입력받아 홀수번 나온 숫자들을 모두 XOR연산하여 결과를 리턴하는 문제. 초등학교교 학생인 정우와 석환이는 최근 학교에서 두 이진수의 XOR 연산에 대해 배웠다. 둘은 매우 영특한 학생이라 새로 배운 연산을 갖고 이리저리 장난치기 시작했다. 다만 석환이는 정우에게 일을 시키는 것을 좋아하는지라 다음과 같은 제안을 했다. “내가 N개의 10진수를 주면, 등장하는 숫자들 중 홀수번만 나타나는 숫자들을 모두 XOR한 결과를 구해줘.” 나는 XOR을 정보처리산업기사 공부하면서 처음 접했는데 이놈들은 초딩때 이런 뻘짓을 하는걸 보니 대단하다. > .. 2020. 8. 10.
조이스틱 (Joystick) > 문제 출처 https://programmers.co.kr/learn/courses/30/lessons/42860 > 문제 설명 오락실 게임을 클리어하면 마지막에 이름을 새기는 영광이 주어진다. 이름을 새기는데 필요한 최소의 방향키 이동 수를 리턴하는 함수를 완성하며 되는 문제. 최대 20글자이며, 모든 문자는 A부터 입력한다. > 접근 방법 각 자리간 이동(x방향) 과 문자 변경(y방향)은 독립적으로 계산이 가능하다는 점을 이용하여 x방향과 y방향의 최소값을 구하는 함수를 각각 만들어 더하면 될 것 같다는 생각을 했다. - y방향 : A (ASCII-65) -> N (ASCII-78)이 정방향/역방향 모두 13회로 같다. 따라서 N보다 크면 역방향, 그 반대는 정방향으로 조작 횟수를 계산한다. - x.. 2020. 8. 9.
[R #6] 데이터 조작 이번 단원에서는 수집한 데이터를 분석 목적에 맞게 가공/처리하는 변환과 조작 관련 패키지를 중심으로 구성되어있다. 배워볼 패키지 명은 plyr / dplyr / reshape / reshape2이다. 1. plyr 패키지 : 두 개 이상의 data frame을 대상으로 Key값을 이용하여 하나로 병합하거나 집단 변수를 기준으로 함수를 적용하여 요약 집계 결과를 제공하는 패키지. > join 함수 : 데이터를 병합(join 연산)하는 함수 - 형식 : join( df_x, df_y, by=, type=, match=) - df_x / df_y : join 할 데이터 프레임 - by= : 기준 열 - type : 조인 타입을 설정 (default = 'left') left - 왼쪽(x) 데이터의 기준 변수(.. 2020. 6. 11.
[R #5] 데이터 시각화 1. 시각화 도구 분류 > 변수의 연속성에 따른 분류 이산변수 연속변수 막대, 점, 원형차트 등 상자 박스, 히스토그램, 산점도 등 > 칼럼 특성에 따른 분류 칼럼 특성 도구 숫자형 범주형 1 hist, plot, barplot 1 pie, barplot 2 plot, abline, boxplot 3 scatterplot3d n n pairs 2. 이산변수 시각화 > 막대 차트 시각화(barplot) argument 내용 xlim/ylim x/y 축 값 범위 xlab/ylab x/y 축 이름 col 색상 main 차트 제목 hoirz 가로 막대형 설정(default = F) beside x축 값을 측면으로 배열(F = 누적 막대) space 막대 간격(커질수록 막대 굵기는 작아짐) cex 막대 크기 설정.. 2020. 6. 6.
[R #4] 제어문과 함수 1. 연산자 > 산술연산자 사칙연산(+,-,*,/)과 나머지연산(%%), 제곱연산(^,**)으로 구성되어있다. * 다른 프로그래밍 언어와의 차이점은 나누기(/)에서 나타났다. R에서는 integer와 double의 구분이 없어 연산을 하면 항상 몫이 아닌 실제 나눈 값이 나온다. > 관계/논리연산자 관계연산-동등/크기비교(==, !=, >, >=)와 논리연산-(&, |, !, xor())으로 구성되어있다 . 2. 조건문 > if() - 형식 : if(){statements} [else if(){statements}] [else{statements}] * 주의할 점은 else if/ else를 붙일 때 앞의 닫는 중괄호(' } ')와 같은 줄에 붙여야 한다.` > ifelse() 함수 : 3항 연산자와 유.. 2020. 6. 3.

티스토리툴바