화햇 3기 기초 교육 받으면서 apk 분석을 처음 해봤는데 재밌었다. mobilehacking.kr 이라는 사이트인데 문제 중 write up을 쓸 수 있는 문제가 하나 있습니다. ProjectApp 블루스택에 주어진 apk를 설치하고 실행해보면 이렇게 입력 할 수 있는 칸과 SERIAL CHECK 버튼이 있다. 이정도만 보고 jadx...

개강한지도 1달이 됐고, 할 것들이 자꾸 쌓여가서 정리를 좀 하려고 적는다. 시간표 <3-1> 우선 이번 학기 시간표입니다. 작년 시간표를 보면 원래도 그득그득 채우는 스타일이긴 했다. <2-2> 이번에는 일단 6전공을 듣고 있고, 화이트햇이라는 교육도 받고 있다. 사실 화햇을 일단 넣어보고, 합격해도 시간을 낼 수...

n제곱 계산 n제곱 계산 문제 이 문제에서 숫자 (3 + √5)^n 에 대한 소수점 앞에 마지막 세 자리를 찾아야합니다. 예를 들어, n = 5 일 때 (3 + √5)^5 = 3935.73982 … 이므로 답은 935입니다. n = 2 인 경우 (3 + √5)^2 = 27.4164079 … 이므로, 답은 027입니다. 입력 첫 번째 입력 줄은 ...

백준 마라톤 (코스43) (6/8) 이번 주는 시간도 별로 없었고, 도저히 못 풀겠는 문제가 2문제가 있었습니다.. 저장해놨다가 나중에 더 강해지면 도전해보자. Identifying tea (11549, B4) A번 문제 풀이 숫자 n을 입력 받은 후 a,b,c,d,e를 입력 받는다. a,b,c,d,e 중에서 n과 같은 숫자의 개수를 출력...

binary search int search(int a[], int n, int x) { int i; for(i=0; i<n; i++) if(a[i] == x) return i; return -1; } 어떤 배열에서 원하는 값을 찾는 경우를 생각해보자. 배열의 길이가 N일 경우 앞에서부터 하나씩 보면 O(...

우물 파기 우물 파기 문제 폴리매스 왕국의 사람들은 우물을 이용해 지하수를 마십니다. 지하수의 근원은 물의 돌이라고 알려져 있으나, 물의 돌의 정확한 위치를 알고 있는 사람은 아무도 없습니다. 최근 들어 인구가 늘어나자 물이 부족해졌습니다.<br. 사람들은 이를 해결하기 위해 두 개의 우물을 더 파려고 합니다. 우물을 팔 수 있는 곳은 N곳...

백준 마라톤 (코스42) (8/8) 처음 플레 문제가 나왔다. 계속 풀다보니 실력이 느는지 풀만했다. Haughty Cuisine (20336, B4) A번 문제 풀이 그냥 입력 받은 것 중 1세트를 출력하면 된다. int main() { ios_base ::sync_with_stdio(false); cin.tie(NULL...

brute force 브루트 포스. 직역 하면 무식한 힘이라는 뜻이다. 머리가 나쁘면 몸이 고생한다는 것처럼 어떤 문제에 대해 모든 경우의 수를 시도하는 방법이다. 이렇게 보면 비효율적이고 무식한 방법이라고 생각할 수 있지만 의외로 많이 쓰인다. 우선 모든 경우의 수를 해보기 때문에 시간과 자원만 된다면 성공률이 100%이다. 노가다라고도 부르고 ...

Alkon 3주차 챌린지 (6/6) 또 2등에 있다. 이번에는 D번에서 막히면서 느려져버렸다. A번 아카라카 2 (32652, B3) A번 문제 풀이 연속 부분 문자열로 AKARAKA를 n개 만드는 문제이다. AKA가 뒤에 3개 있으니 계속해서 RAKA를 붙이면 만들 수 있다. int main() { ios_base ::sync_...

백준 마라톤 (코스41) (8/8) 이번에도 다 풀 수 있었다. 이분 그래프를 알게 됐어요. 점점 알고리즘 공부에 할애할 시간이 줄어들고 있다. 다음 마라톤에는 플레 문제가 나오지 않을까 기대가 되네요. Virus (13775, B1) A번 문제 풀이 암호학 시저 암호? 같은건데 key가 1씩 증가한다. 그냥 역으로 구현하면 해독이 된다....

Alkon 2주차 챌린지 (6/6) 저번이랑 똑같은 사진 같지만 다른 주차 다른 문제이다. A번 오버플로우와 모듈러 (15818, B3) A번 문제 풀이 주어지는 숫자들을 모두 곱한 값에 모듈러 연산을 한 값을 출력하는 문제이다. 간단하게 곱하는 모든 숫자들에 모듈러 연산을 하며, 마지막 결과에도 한번 더 해주면 된다. int main(...

트리 트리 문제 그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다. 트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개,...

이분 그래프 이분 그래프 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테...

halting problem 우리 교수님이 항상 이 halting problem에 대한 이야기를 첫 수업마다 한다. 재밌는 이야기라 정리해보자. 이발사 문제 우선 이발사 문제에 대해 알아보자. 어떤 마을에는 이발사가 한 명 있는데 이 이발사는 스스로 이발하지 않는 사람 모두 이발을 해준다. 그러면 이발사의 머리는 누가 이발을 하는가? 만약 스스...

트리의 지름 트리의 지름 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000) 둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정...

최대공약수와 최소공배수 수학 관련 문제에서 가장 많이 사용하는 것은 이전 글인 소수와 최대공약수인 것 같다. 보통 최대 공약수를 구하는 문제에서는 유클리드 호제법을 이용한 알고리즘을 사용한다. 시간 복잡도는 O(lonN)이고, 이 글에서는 간단하게 증명을 해보려고 한다. 증명 A와 B라는 두 숫자의 최대 공약수 G를 구해보자. 증명할 내용은 a...

소수 판별 수학 관련된 문제를 풀다보면 어떤 숫자가 소수인지 아닌지를 판별해야 할 때가 많다. 어떻게 어떤 수가 소수인지 아닌지 알 수 있을까? 소수 우선 소수란 자기 자신과 1로만 나누어 떨어지는 수이다. 이 때 1은 제외한다. 2, 3, 5, 7... 숫자 1개가 주어졌을 때 소수인지 판별하는 방법부터 보자. 시간 복잡도 O(N) 가장 간...

특정한 최단 경로 특정한 최단 경로 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했...

거짓말 거짓말 문제 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말...

백준 마라톤 (코스40) (8/8) 39주차는 일본어 문제 + 위상 정렬 4문제라는 문제 셋을 받아서 풀 수 없었다.. 그래도 이번 주차는 수학 + 애드 훅 구성으로 나와서 쉽게 풀만했다. A번 노트북 세 대를 가지고 왔다 (33515, B5) A번 문제 풀이 숫자 2개를 입력 받고 더 작은 것을 출력하면 되는 간단한 문제이다. int ...

Alkon 1주차 챌린지 (6/6) 이번에 학교 알고리즘 동아리 들어갔는데 매주 챌린지가 있다길래 다 풀어보려고 한다. 문제 난이도는 각각 B4, B2, S4, G5, G3, P4였는데 나름 풀만한 난이도였던 것 같다. A번 심부름 가는 길 (5554, B4) A번 문제 풀이 이동하는 시간이 초 단위로 4개가 주어지고, 그걸 다 더한 다음...

GCD(n, k) = 1 GCD(n, k) = 1 문제 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 n (1 ≤ n ≤ 10^12)이 주어진다. 출력 GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다. 풀이...

제곱수 찾기 제곱수 찾기 문제 N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다. 연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수...

오아시스 재결합 오아시스 재결합 문제 오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다. 이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다. 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. 줄에 서 있는 사람의 ...

EZ-RSA-PZ 오랜만에 드림핵 문제를 붙잡고 풀어봤다. 방학 때 암호학 스터디를 하면서 계속 암호학 공부를 하다보니 문제가 풀고 싶어졌다. 딱 풀고서 블로그에 깔끔하게 정리해야지 생각을 했는데 찾아보니 dreamhack 롸업은 별로 없는 것 같다. 기본 새싹~레벨 1 정도까지는 많은데 그 이상은 없고 다 비공개 처리한 글들 밖에 없는 것 같...

백준 마라톤 (코스38) (6/8) 사용자 수준에 맞춰서 문제를 랜덤으로 골라서 내주는 solved 랜덤 마라톤이다. 어느새 하다보니 38번째 코스에 도달했고, 실버 반, 골드 반이 나온다. 다 풀 수 있었는데 실수해서 시간내에 못 푼 것이 아쉽다. D번은 기간 내에 풀었는데 왜 X처리가 된 것인지는 모르겠고.. 골랜디 느낌으로 공부하기 재밌고...

가짜 소수 가짜 소수 문제 문제에 수식이 들어있어서 사진으로 대체한다. 페르마의 소정리는 소수 p에 대해 a^(p-1) ≡ 1 (mod p)이다. 하지만 페르마의 소정리를 만족한다고 소수가 되는 것은 아니다. 지구이는 a를 2~500까지 확인해 페르마의 소정리를 만족한다면 소수라고 판별했다. 하지만 논리의 역은 참이 아니고, 반례가 있으니,...

팰린드롬? 팰린드롬? 문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 ...

수 나누기 게임 수 나누기 게임 문제 문제가 길어서 요약. 각 플레이어는 1~1000000 사이의 카드르 한 장 씩 가지고 모든 사람과 결투를 한다. 결투를 했을 때 결과는 상대 숫자를 내 숫자로 나누면 +1, 나뉘면 -1이 된다. 게임이 끝나고 모든 플레이어의 점수를 구하라. 풀이 처음엔 예전에 풀었던 누적합으로 최대 공약수 했던 문제가 생각났...

회문 회문 문제 회문 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseud...

패스 패스 문제 N명의 사람들이 원형으로 앉아있고, i번째 오른쪽 사람은 i+1번째, N번째 사람 오른쪽엔 1번째가 앉는다. 1번이 처음에 공을 가지고 있고, 둘러앉은 사람 가운데에는 1~N의 카드가 있다. 둘러앉은 사람들은 다음과 같은 게임을 N차례 진행했다. 공을 가진 사람이 나와서 카드 한 장을 뽑은 다음 자기 자리로 돌아간다. ...

직사각형 && 약 팔기 직사각형 약 팔기 문제 풀이 날먹문제집? 시리즈에 있어서 넌센스 겸으로 풀어봤다. 애드 훅이지만 다행히도 풀이가 간단하게 생각나서 쉽게 푼 것 같다. 이제 붙어 있는 값을 더해서 1~1000000 까지의 숫자를 만들 수 있으면 된다. 처음에는 2진수로 1 2 4 1 2 4 8 … 이런식으로 하면 되지 않...

빙고 빙고 문제 구데기컵에 나온 빙고를 푸는 문제이다. 풀이 재밌어 보이고 티어도 높아서 1시간 동안 열심히 풀었는데 점수를 안 준다고 한다. ㅠ 그래도 푸는 과정이 퍼즐 푸는 것 같아서 재밌었다. 우선 C3는 반드시 참이다. 색칠되지 않으면 모순이 생기기 때문이다. B1이 참이 아니라면 빙고줄의 일부지만 체크가 되면 안되므로 모순이 ...

학부 연구생 민상 새벽까지 계속 고치고 고쳐봐도 문제가 풀리지 않는다. 문제는 빡구현이라고 할 수 있는 귀찮은 dfs? 문제라고 생각했고 어쨌든 구현은 다 했다. 그런데 59%에서 시간 초과도 아니고 자꾸 메모리 초과가 발생한다. 처음에는 배열 index를 넘어간다거나 그런게 있나? 하고 찾아봤는데 아무것도 없다. 문제 제한을 봐도 메모리 ...

백준 문제를 푸는데, 분명 로직이 맞는 것 같은데 안되는 경우가 있다. int ma=-1; for(int i=1;i<=n;i++){ if(ma < graph[i].size()){ ma = graph[i].size(); save = i; } } 이런 코드...

경비병 세우기 게임 경비병 세우기 게임 문제 Yuto 와 Platina가 보초 세우기 게임이라는 새로운 게임을 해보려고 한다. 이 게임은 N × M의 가로가 긴 격자판에서 진행된다. 게임은 항상 Yuto부터 시작하며, 둘은 번갈아 가면서 자신의 턴에 원하는 빈 위치에 경비병을 세운다. 이 게임에서 ‘안전상태’라는 것은 격자판 안에 완벽히 포함되는...

최솟값 찾기 최솟값 찾기 문제 N개의 수 A1, A2, …, AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. 입력 첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000) 둘째 줄에는 N...

소트 소트 문제 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 N개의 수가 주어진다. N개의 수는 1,000보...

동전 뒤집기 동전 뒤집기 풀이 비트 마스킹 문제인데 아직 어색하다. 우선 아이디어 1. 같은 자리를 두 번 이상 뒤집는 것은 아무런 의미가 없다. 그렇기에 모든 가로에 대해 뒤집는 경우 2^20을 해보고, 세로에 대해 그리디하게 뒤집으면 된다. 그러면 시간 복잡도는 2^n * n^2이니까 충분히 해결이 가능하다. 계속 시간 초과가 나서 다...

절망적인 줄 절망적인 줄 문제 해빈시의 공원에는 화장실이 두 개가 있다. 그런데 그 중 하나가 얼마전에 고장났다. 이제 남은 건 한 개 뿐이다…. 문제는 해빈이는 당장 화장실이 가고 싶은데, 화장실 앞의 줄이 매우 길다는 것이다! 고통을 잊기 위해 해빈이는 절망적인 줄을 쳐다보며 아래와 같은 문제를 풀기 시작했다. 화장실 사용료는 50원이다....

냅색 문제 냅색 문제 문제 세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다. N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 ...

**팰린드롬 인코딩 ** 팰린드롬 인코딩 문제 준규는 심심해서 팰린드롬 인코딩이라는 새로운 인코딩 방법을 만들었다. 팰린드롬 인코딩은 0과 1로만 이루어진 자료만 인코딩 할 수 있으며, 다음과 같은 과정을 거친다. 문자열 S에서 짝수 길이인 팰린드롬 연속 부분 문자열을 찾는다. 팰린드롬은 앞에서부터 읽을 때와 뒤에서부터 읽을때가 똑같은 문자열...

보이는 산맥 보이는 산맥 문제 맑은 날 울릉도에서 태백산맥을 바라보면 수평선 위로 N개의 산봉우리가(1 ≤ N ≤ 100,000) 보인다. 다음은 N = 5인 경우의 예이다. /\ /\ / \ /\ / \/\ /\/ \/ \ / \ \ / \ / \ ---...

최대공약수 하나 빼기 최대공약수 하나 빼기 문제 정수 A가 B로 나누어 떨어지면, B는 A의 약수이고 A는 B의 배수이다. 최대공약수란 정수의 공통된 약수 중 가장 큰 수를 말한다. 예를 들어, 12와 8의 공통된 약수 1, 2, 4 중에서 가장 큰 것은 4이기 때문에 12와 8의 최대공약수는 4이다. N개의 정수 중에서 임의의 수 K를 뺐을...

별 찍기 시리즈 별 찍기 시리즈 처음 풀었던 알고리즘? 프로그램? 문제라서 그런지 왠지 정이 가는 별찍기 문제다. 이중 반복문을 이해하는데 별 찍기만한 문제도 없다고 생각이 된다. 저 문제집에서 뒷 부분은 재귀 or 귀찮은 조건문 문제긴 하지만 나름 재밌다. 학원에서 가르치면서 딱 반복문 끝내면 꼭 별찍기 1~7을 풀게 했는데 이걸 잘하면 보통 ...

차원의 나무 여행 차원의 나무 문제 정점의 개수가 N, 간선의 개수가 N-1인 트리가 주어진다. 간선으로 직접 연결되지 않은 정점으로 이동하는 것을 워프라고 한다. 각 정점을 최대 한 번만 방문할 수 있을 때, 가능한 워프의 최대 횟수를 구하여라. 시작 정점은 임의로 고를 수 있으며, 시작 정점을 고르는 것도 워프이다. 입력 첫 번째 줄에 N이 ...

Consonants (Large) Consonants (Large) 마라톤에 나와 푼 영어 문제라 눈에 안 들어온다.. 코드 잼 2013년 문젠데 이게 왜 골드 5지.. 생각하기 어려운 애드 훅 같은데 문제는 이런 입력에서 예제 입력 1 4 quartz 3 straight 3 gcj 2 tsetse 2 예제 출력 1 Case #1: 4 Ca...

풍선 풍선 문제 전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다. 풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다. 풍선은 방 A와 방 B에 보관되어 있다. 대회에 참가한 팀의 수는 총 N개이고, 앉아있는 자리는 서로 다르다. 어떤 팀은 방 A에 가깝고, 어떤 팀은 B에 더 가깝다. 각 팀에게 달아줘야 하는 풍선의 수와 방 A와 ...

호반우가 학교에 지각한 이유 2 호반우가 학교에 지각한 이유 2 문제 이세계를 모험할 때는 무기가 필요한 법이기에 호반우는 현재 신에게 받은 소수소수검의 사용법을 익히고 있다. 소수소수검을 사용하기 위해서는 검이 제시하는 두 자릿수의 소수 A,B와 양의 정수 N을 이용해 소수소수를 만들어야 한다. 소수소수란 해당 수 자체가 소수일 필요는 없지만...

곱셈 곱셈 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나...

좌표 압축 좌표 압축 문제 수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자. 입력 ...

회의실 배정 회의실 배정 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과...

평범한 배낭 평범한 배낭 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치...

시간복잡도 시간 복잡도란 특정한 크기의 입력에 대해 알고리즘의 수행 시간을 평가한다. 알고리즘 문제를 풀다보면 입력의 크기에 따라 시간을 어느정도 계산할 필요가 생긴다. 입력 데이터가 최선의 경우, 평균적인 경우, 최악의 경우에 따라 시간 복잡도를 나누게 되고 문제에서는 보통 최악의 경우로 알고리즘의 성능을 파악한다. 최선의 경우는 빅 오메가 표...

algorithm 시작 방학 목표가 백준 플레 + 코드포스 블루까지 가는 것이었는데 자꾸 안하게 된다. 코드포스는 2학기 기말 전까지 열심히 해서 민트 단 다음에 그 뒤로 안하고 있고 백준도 스트릭은 계속 잇고 있긴한데 많이 풀고 있진 않다. 티어작을 하려면 금방 올리겠지만 그것보단 다양하게 공부하고 싶다. 그래서 자료구조, 알고리즘 개...

블로그 계획 사실 C언어 정리를 1월 초~중이면 끝낼 줄 알았는데 생각보다 늦어졌다. 알고리즘도 정리해야 하고, 문제 푸는 것도 정리를 시작해야겠다. 주 공부는 보안이었으면 좋겠는데, CTF랑 개념 정리한 것도 만들어아 하고 학교 공부나 추가로 CS 공부한 것도 만들어야겠고, 언어도 시간이 되면 조금씩 해야겠다. 일단 하나씩 꾸준하게 쓰는 것을...

C언어 (26) visual studio visual studio 오류랑 편리하게 쓸 수 있는 디버깅 모드들 오류 모음 #_CRT_SECURE… visual studio만의 오류?라고 볼 수도 있는 오류이다. scanf뿐만 아니라 입출력, string 관련 함수에서도 다 이런 에러를 낸다. 실제로 이 함수들이 버퍼 오버플로우 및 기타 ...

C언어 (25) 조건부, 분할 컴파일 마지막으로 조건부, 분할 컴파일에 대한 내용이다. 이론적이라기 보다는 컴파일 방법에 대한 내용이니 간단히 적어도 될 것 같다. 조건부 컴파일 C언어는 다양한 OS에서 사용되었기에 제공하는 표준 함수나 동작이 조금씩 다를 수 있다. 같은 운영체제를 사용한다 하더라도 사용하는 컴파일러와 라이브러리가 다를 수도...

C언어 (24) 매크로와 인라인 함수 C언어 책 마지막엔 전처리기와 분할 컴파일에 대한 이야기가 있다. 사실 잘 안쓰는 잡다한 내용이라 여기까지 진도도 안나가고 안 읽어봐서 처음 보는 내용이었다. 이번에 싹 정리하는 겸 다 내용을 알아보자. 전처리기 전처리는 본격적으로 소스 파일을 컴파일 하기 전에 먼저 처리해야 하는 일이다. 코드의 가장 위...

C언어 (23) 동적 메모리 할당2 지난번에 안본 realloc과 free를 보고, 동적 메모리를 끝내자. 동적 메모리 할당 함수 함수명 설명 반환 값 malloc(size) 지정된 크기만큼 메모리를 할당하며 초기화되지 않은 메모리를 반환. ...

C언어 (22) 동적 메모리 할당 프로그램에서 사용되는 메모리는 정적 메모리와 동적 메모리가 있다. 우리가 선언하던 일반 배열들은 컴파일 할 때 메모리의 크기가 정해진다. 이런 정적 메모리는 프로그램을 실행하면서 메모리의 크기를 변경하는 것이 불가능하다. 이 문제점을 해결 하기 위해서 동적으로 메모리를 할당하고 해제하는 작업이 필요하다. 프...

C언어 (21) 파일 입출력2 stream이란 무엇인지, 파일을 어떻게 여는지 알았으니 이제 입출력 함수를 사용해본다. 표준 파일 입출력 함수 표준 파일 입출력 함수는 이렇게 입출력 스트림을 정해서 원하는 입력 방법을 선택할 수 있다. 함수들을 하나씩 사용하면서 기능을 정리해보자. 문자 단위 표준 파일 입출력 함수 fgetc(), fpu...

C언어 (20) 파일 입출력 프로그램은 파일을 통해 데이터를 받거나 쓰는 경우가 많다. 이런 동작을 C언어로 해보자. 스트림(stream) 스트림(stream)이란 데이터를 입력하고 출력하기 위한 다리 같은 역할이다. 키보드, 모니터 같은 입출력 장치들은 다양한 방식으로 데이터를 주고받는다. 이 키보드와 프로그램, 프로그래뫄 모니터를 이어 ...

C언어 (19) 문자열 이용하기 지난번에 문자열의 입출력 함수에 대해 자세히 알아봤다. 이제 문자열을 처리하는 함수와 포인터로 문자열을 사용해보자. 문자열 처리 함수 문자열을 프로그램에서 사용하다보면 문자열을 붙이거나, 길이를 구하거나, 비교하는 작업이 필요하다. 직접 함수로 작성해도 되지만 C에서는 이런 역할을 하는 여러 함수를 라이브러리로...

C언어 (18) 문자열 C언어에서의 문자열은 상당히 복잡하고 신경 쓸 것이 많다. 그래서 python을 먼저 배우고 C언어를 배울 때 제일 헷갈려하는게 이 문자열 부분인 것 같다. 또 python이나 C++ string STL을 사용하면 문자열 다루기가 굉장히 편하다. 그럼에도 C언어로 문자열을 사용해야 하는 일이 있을 수도 있고, 여러 함...

C언어 (17) 구조체와 공용체3 함수에 구조체를 이용하는 방법과 공용체, 열거형을 보자 . 구조체와 함수 구조체를 함수로 사용하는 경우는 두 가지가 있다. 구조체를 함수의 인자로 전달하기 구조체를 함수의 반환형으로 전달하기 인자로 사용할 때도 값으로 전달하는 방법과 주소로 전달하는 방법이 있다. #include <stdio...

C언어 (16) 구조체와 공용체2 구조체에서 배열과 포인터를 어떻게 쓰는지 자세히 보자. 구조체의 메모리 저장 방법 구조체가 메모리에 저장되는 방식은 그림과 같다. 각각의 멤버 변수는 시작 주소부터 연속되어 저장을 한다. 크기는 구조체의 멤버 중 가장 큰 멤버의 자료형에 영향을 받는다. 예시로 확인을 해보자. typedef s...

C언어 (15) 구조체와 공용체 새로운 자료 구조인 구조체와 공용체, 열거형까지 알아보자. 구조체 배열이 타입이 같은 데이터를 하나로 묶는다면 구조체는 타입이 다른 데이터도 묶을 수 있다. 학생의 정보를 저장한다고 할 때 이름, 나이, 점수를 하나로 묶어 저장할 수 있으면 편할 것이다. 이런 여러개의 변수를 그룹화하여 새로운 자료형으로 만...

C언어 (14-2) 함수와 포인터 ex 책에는 있는데 알면 좋고 중요한 것도 맞긴 한데 이해하기 어렵기도 하고 C언어를 배우는 과정에서 꼭 알아야하는 건 아닌 것 같아서 간단히 정리만 했다. main() 함수에 인자를 넣을 수 있다? 여태까지 본 main() 함수는 인자가 없는 main(void) 형태였다. 그런데 다른 형태의 main()함수...

함수는 어떻게 저장되는가? 함수 포인터를 알아보다 작은 궁금증이 생겨서 찾아보고 정리해봤다. 다시 생각하보니 간단한 것이었는데 알아보면서 재밌었으니까~ 함수는 어떻게 메모리에 저장되는가? 함수의 포인터는 함수의 원형과 거의 비슷하게 생겼다. int (*pointer) (int, int) 변수의 포인터는 int*, double* 등으로 참조하...

C언어 (14) 함수와 포인터 여태까지 배운 것을 합쳐서 함수에서 어떻게 포인터를 활용하는지 알아보자. call by value vs call by reference 값에 의한 호출(call by value)은 변수의 값을 복사해서 함수를 호출하는 방식이다. #include <stdio.h> int func(int n); int m...

C언어 (13) 함수2 함수의 선언 방법을 알아보았고, 어떻게 사용하는지 좀 더 알아보자. 또 변수의 선언 위치에 따른 차이점과 종류를 알아보자. 변수의 종류와 범위 변수는 선언되는 위치나 종류에 따라 메모리 상에 존재하는 기간이 다르다. 지역 변수 전역 변수 정적 변수 외부 변수 레지스터 변수 이렇게 5가지로 나눌 수...

C언어 (12) 함수 책을 보면 함수를 간단하게 소개하고, 그 다음이 배열, 포인터 순서로 하는 것이 대부분이다. 하지만 포인터, 포인터-배열 관계, 함수, 포인터-함수 관계로 잇고 싶어서 순서를 조금 꼬았다. 흐름만 이해하면 함수는 쉽게 이해하는 것 같다. 함수 수학에서 함수란 어떤 x를 넣었을 때 y라는 값을 내는 f(x)같은 것이다....

C언어 (11) 포인터와 배열2 포인터와 배열의 관계를 이어서 더 보자. 포인터 변수를 통한 1차원 배열 접근 배열의 이름은 배열의 시작 주소와 같다고 했다. 그리고 배열의 주소에 +1, +2를 하면 주소는 배열의 요소 크기만큼 증가한다. #include <stdio.h> int main() { int arr[5] = { 1...

C언어 (10) 포인터와 배열 포인터에 대해 간단히 보았는데, 활용에 대해서는 아직 잘 모르겠다. 포인터의 특성을 좀 더 보고, 배열과 연관지어 보며 어떻게 사용하는지 알아보자. 다중 포인터 int** ppnum; 이런 포인터는 존재할 수 있을까? 포인터 변수도 주소를 가지고, 8바이트 또는 4바이트의 크기를 가진 변수이다. 그렇다면 포인터...

C언어 (9) 포인터 C언어에서 가장 중요하고 이해하기 어려운 개념으로 꼽히는 것이 포인터일 것이다. 변수와 배열 이야기를 하며 계속 주소를 언급했는데, 이 주소를 어떻게 쓸 수 있는가?에 대한 이야기다. 중학생 때 처음 C언어를 학원에서 배웠었는데 포인터는 어려우니까 넘어가자~라고 말했었다. 지금 생각해보면 이해가 안되는 말인 것이 포인터...

C언어 (8) 배열 학교의 모든 학생의 성적을 변수에 저장하고 싶은데 각각 변수를 생성하면 변수의 개수가 너무 많아진다. 이 때 같은 자료형을 가진 변수를 묶어 배열이라는 자료구조로 처리할 수 있다. 배열 변수란 우리가 프로그램을 작성할 때 숫자나 문자 같은 데이터를 저장하기 위한 공간이다. 변수는 저장되는 주소가 있고, 공간이 있다. 배...

C언어 (7) 반복문 반복문이랑 동일한 문장을 여러 번 반복하는 구조이다. 동일한 작업을 계속해야 한다면 똑같은 문장을 crtl+c, crtl+v하는 것보다 반복문을 사용하는 편이 좋다. 반복문 노트북을 구매하기 위해 월급을 받아 저축하는 사람의 경우를 프로그램으로 만들어보자. 저축한 돈이 240만원 이상이 될때까지 아르바이트를 하고, 이...

C언어 (6) 조건문 프로그램은 사용자의 선택에 의해 동작해야 한다. 입력이나 신호에 따라 변화하는 프로그램을 만들기 위해 조건문을 알아야 한다. 조건문 자판기 내부의 과정을 간단하게 도식화해서 보면 이런 동작들이 있을 것이다. 이 때 마름모안에 들어있는 문장들을 조건문이라고 부르고, 문장의 참, 거짓에 따라 동작이 바뀐다. 여태까지 ma...

C언어 (5) 연산자 컴퓨터의 연산이란 사칙연산을 포함해 대입, 지수, 조건 등이 있다. 상황에 맞는 연산을 할 수 있도록 연산자를 알고 있어야한다. 분류 연산자 설명 대입 연산자 = 대입 산술 연산자 ...

C언어 (4) 자료형2 정수형 변수에 이어 실수형 변수를 알아보자. 자료형 변환에 대해서도 알아보자. 자료형 키워드 바이트 수 범위 정수형 short 2 -32,768 ~ 32,767 ...

C언어 (3) 자료형 변수를 선언할 때 어떤 자료형을 받을지 앞에 적어줘야 한다. 자료형이란 뭘까? 이 자료형에 따라 메모리에 어떻게 값이 저장되는지 자세히 알아보자. 자료형 데이터는 정수형, 실수형, 문자형과 같이 다양한 type을 가진다. 이 type이 자료형이다. 나누는 기준은 변수 앞에 붙여진 int, double 등의 키워드를 보고 ...

C언어 (2) 변수와 상수 프로그램은 사용자에게 입력을 받고 그에 따라 다른 값을 내놓는다. 상수와 값을 저장하는 공간인 변수의 차이를 알아보고 입력 함수 scanf를 써보자. 변수 변수란 우리가 프로그램을 작성할 때 숫자나 문자 같은 데이터를 저장하기 위한 공간이다. #include <stdio.h> int main() { ...

C언어 (1) 기초 사항 비주얼 스튜디오를 설치하고 이제 프로그램을 직접 만들어 본다. 문장, 주석, 함수, 출력 함수를 본다. 입출력 방법 #include<stdio.h> /*주석*/ int main(void){ printf("Hello World!"); //hello world! return 0; } 위의 코...

C언어 (0) 개요 공부한 것을 적으려고 만든 블로그인데 어떻게 시작할지 모르겠다. 일단 컴공의 시작은 C언어! 같은 느낌이니까 c언어 정리로 시작하자 코딩 학원 강사로 일한지가 24년 1월 말부터니까 거의 1년이 되어간다. 수업을 하며 이건 알았으면 좋겠다거나 많이 실수하는 것도 적어야겠다. 수업 자료처럼 쓰기 위해서.. 책은 C언어 콘서...

마크다운 문법 정리 github.io를 처음 만들고 마크다운으로 글을 쓰는 것이 처음이라 한 번 정리하고 노트처럼 쓰기 위해 작성합니다. 1. 제목 (Headers) 제목을 표시할 때는 #을 사용하고. #의 개수에 따라 제목의 레벨이 된다. # 제목 1 ## 제목 2 ### 제목 3 #### 제목 4 2. 강조 (Emphasis) 텍스트...