전체 글
-
파일처리 기본파일처리 2020. 4. 17. 17:20
기본적으로 파일을 처리하는데는 여러가지 기법이 있지만 오늘은 용어정리만 하려고 해요 파일의 종류 Physical Files 물리적 파일로 실제 디스크에 저장되며 os 가 관리하는 물리적인 파일 Logical Files 논리적 파일로 프로그램 상에서 접근하는 파일이 논리적 파일이며, file open 시 os 가 Physical file과 맵핑된 Logical file 을 넘겨주어, 이 파일을 읽거나 쓰게됨 파일처리 기법 Sequential : 테이프처럼 맨 처음부터 순차적으로 읽는 방식 Simple index : 하드디스크의 등장으로부터 가능한 방식으로, 데이터의 인덱스를 지정하여 특정 인덱스를 바로 접근할 수 있게하는 방식 Binary tree : 데이터를 바이너리 트리로 관리. 선형으로 이루어질수도 ..
-
사과와 바나나 (boj 3114)알고리즘 2020. 4. 17. 15:08오늘은 사과와 바나나 문제를 풀어봤어요 R * C 크기의 땅에 두 국가 A, B가 있어요. A나라는 Apple(사과)를 좋아하고, B 나라는 Banana(바나나)를 좋아해요. 각 땅은 1 * 1 격자로 쪼개어져 있고, 격자 한 칸에는 사과나무 혹은 바나나 나무가 심어져 있고, 각 생산량은 입력으로 주어져요. A 국가와 B국가는 불도저로 땅을 밀어버려서 국경선을 그으려고 해요. 국경선의 아래쪽은 A 국가, 윗 쪽은 B 국가의 땅이고, 불도저가 지나간 자리는 나무가 모두 사라져요. 불도저는 맨 왼쪽 위에서 출발하여 맨 오른쪽 아래에 도착할 때까지 이동하며, 한 번 이동할 때 한 칸 아래, 한 칸 오른쪽, 한 칸 오른쪽 아래 대각선으로 이동할 수 있어요. 이때 어떻게 하면 A 국가의 사과 생산량과 B국가의 바..
-
구간합 구하기알고리즘 2020. 4. 17. 14:21구간합을 O(n) 만에 구하는 알고리즘에 대해서 알아볼게요 위와 같은 수열이 있다고 하고 이들의 구간합을 구해볼게요 구간합을 구한다는 말은 랜덤으로 어떤 구간을 정하면 그 구간의 합을 딱딱 구하는걸 말해요 [0 - 3], [2 - 4] 를 예시로 구간합을 구해봤어요. 어떤 구간이 주어질때마다 수열을 loop 돌며 구하는 방법이에요. 이 방법으로 모든 구간의 구간합을 구하기 위해서는 O(n^2)이라는 시간이 필요해요 하지만 오늘 알아볼 방법은 O(n)의 방법이에요 하늘색 수열이 보이시나요? 이건 0번째 원소부터 자기 자신까지의 누적합을 구해둔 배열이에요 0번째 누적합은 2, 1번째 누적합은 2 + 5 = 7 2번째 누적합은 2 + 5 + 8 = 15 이렇게 누적합을 구해두면 특정구간의 합을 O(1)만에 구..
-
DFS 메모이제이션알고리즘 2020. 4. 15. 19:54오늘은 DFS 메모이제이션 기법에 대해 알아볼거에요 이 기법은 DFS 문제를 조금 더 최적화 시킨 기법으로, 개념 자체는 매우 간단해요 "한 번 갔던 곳의 DFS 결과 값을 저장해두고 나중에 이 곳에 다시 방문하면 또 탐색하지 말고 이 값을 재사용하자!" 라는 생각인거죠 메모이제이션 기법은 N이 커질수록 그 빛을 발하니 꼭 익혀두는게 좋아요 N * N 짜리 2차원 배열이 있다고 하고, 우리는 값이 점점 커지는 최대 경로를 구하는 문제가 있다고 합시다. 아래와 같은 배열의 경우에는 1 2 3 5 6 4 7 6 5 1 2 3 5 6 4 7 6 5 분홍색으로 칠해진 부분이 정답이 될거에요 일반적인 DFS로도 충분히 구할 수 있지만 그렇게 되면 계산의 중복이 심해져서 매우 느린 알고리즘이 될 수 있어요 여기서 ..
-
C언어의 문법프로그래밍언어 2020. 4. 13. 08:57규동 언어를 CFG로 표현하는 법을 해보았으니 이번에는 C언어를 표현해보죠 CFG 나 BNF 에 대해 잘 기억이 안나 시는 분들은 위 링크에 잠깐! 다녀오세요 ㅎㅎ 10분이면 충분합니다~ C언어의 if 문은 어떻게 생겼니? 라고 묻는다면 아마 대부분은 "음~ if, 괄호, 조건문, 괄호 닫고, 중괄호 열고, 코드들이 쭉 와"라고 말할 테지만 반은 맞고 반은 틀린 표현이에요. 기술 면접에서도 물어볼 수 있는 이 질문에 대해 정확히 답하려면 오늘 배울 내용이 반드시 필요할거에요. C언어의 BNF(CFG) 표현법 프로그램 => => | => | 프로그램은 어떻게 생겼니? 프로그램은 translation_unit으로 만들어졌어~ translation_unit이 뭔데? translation_unit은 extern..
-
CFG (Context Free Grammar)프로그래밍언어 2020. 4. 13. 06:00
프로그래밍 언어는 CFG (Context Free Grammar) 로 나타낼 수 있어요 오늘은 C언어의 문법을 BNF 로 나타내볼거에요. BNF 는 CFG의 한 갈래로 일단 여기서는 이 둘은 같다라고 생각해도 될거같아요. 세상에 "규동" 이라는 언어가 있어서 이 언어는 "규"와 "동" 이 두 글자만 사용할 수 있는 언어에요. 규칙은 모든 "규"는 "동" 보다 앞에 있어야 한다. 즉 모든 "규"가 "동" 보다 앞에있는 세상 모든 문자열은 "규동" 언어로 표현됐다. 라고 말할 수 있어요 예를 들면 "규동", "규규동", "규동동동", "규", "동" 이 이런 경우에요. 그럼 "규동" 언어가 아닌건 뭐가 있을까요? "규동규", "동규", "규규규규규규동규" 이런 경우겠죠 이렇게 어떤 언어를 말로 표현하는것도 ..
-
편집거리(boj 7620)알고리즘 2020. 4. 11. 02:45
최근 며칠동안 편집거리 문제 푸느라 엄청 고생했었어요 사실 쉽게 푸는 방법이 있었는데 편집거리(Hard) 로 풀어보고 싶어서 고집 피우다가 결국 실패했네요.. ㅠㅠ 학교 과제로 나온거라 기한이 있어서, 나중에 시간나면 하드로 다시 풀어보려구요 간단히 요약하자면 최대 17000 글자인 두 문자열 A, B 를 입력받게되면 문자열 A를 B로 만드는데 필요한 비용을 편집거리라고 해요 우리는 이 편집거리를 최소한으로 하는 방법을 찾으면 됩니다. 연산과 그 비용의 정의는 다음과 같아요 a 'n' : add 출력 문자열에 'n' 을 출력 ( 비용 : 1 ) d 'n' : delete 입력 문자열의 'n'을 삭제 ( 비용 : 1 ) m 'n' : modify 입력 문자를 'n'으로 수정 ( 비용 : 1 ) c 'n' ..
-
string.h 함수 모음C,C++ & Linux 2020. 4. 6. 23:23
void* memchr(const void* str, int c, size_t n); str 에서부터 n바이트 내에 있는 최초의 문자 c를 찾아주는 함수 리턴 값 : 최초의 문자 c가 존재한다면 c가 최초로 등장하는 곳, 없다면 NULL int memcmp(const void* str1, const void* str2, size_t n); str1, str2 의 n바이트가 일치하는지 비교해주는 함수 리턴값 0 이면 str2가 str1 보다 작음 리턴값 == 0 이면 str1과 str2 가 같음 void* memcpy(void* dest, const void* src, size_t n); src의 데이터 n바이트를 dest로 복사해주는 함수 리턴 값 :..