킹의 개발일지

https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 언제나 문제를 풀면서 느끼지만 스토리가 참 재밌는 경우가 많다. 비밀번호를 소수로 정하는 친구가 있다는게... 여하튼, 이 문제는 시작 소수와 도착 소수가 쌍으로 주어진다. 시작 소수에서 한 자리씩 바꿔가며 도착 소수로 변경하고자 할 때, 걸리는 최소 과정을 출력하는 문제이다. 예를 들어 1033에서 8179로 가기 위해서는 1033 1733 3733 3739 3779 8779 8179 처럼 총 6번의 과..

에라토스테네스의 체 라고 불리는 알고리즘은 소수(Prime number)를 구하는 알고리즘이다. 여기서 소수란 '양의 약수를 두 개를 가지는 자연수' 를 의미하고 2, 3, 5, 7 ... 을 예로 들 수 있다. 문제를 풀다보면 소수를 대량으로 빠르게 찾아야하는 상황이 생기는데, 이 때 적합한 방법이 에라토스테네세의 체이다. 일반적으로 특정 숫자가 소수임을 판별하는 방법으로, 2부터 특정 숫자까지 순회하면서 특정 숫자가 나눠보고 나눠진다면 소수가 아님을 통해서 소수를 판별했다. def is_prime(x): for i in range(2, x): if x % i == 0: return False return True 위 같이 알고리즘을 작성하는 경우, 모든 경우의 수를 다 돌면서 약수 여부를 확인하기 때..

https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그래프를 탐색해서 1번 노드와 가장 먼 거리에 있는 노드들의 갯수를 세는 문제다. 기본적으로 문제에서 주어진 edge들로 인접 리스트를 만들어서 dfs나 bfs같은 탐색알고리즘을 적용하며 되는 비교적 간단한 문제이다. 이 문제에는 bfs를 적용해서 풀어보았다. 1 번 노드와 거리를 저장하기 위해 dist라는 리스트를 만들었고 거리를 측정하기 위해 인접 노드로 이동할 때마다 1씩 증가시켜주면 된다...

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 이 문제는 크루스칼 알고리즘을 사용해서 행성들간에 터널을 연결 했을 때 드는 최소 비용을 구하면된다. 크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 연결해야 할 때 사용할 수 있다. 기본 접근 방법은 모든 행성간의 터널 비용을 구하고 가장 비용이 적은 순으로 연결해나가면서 그 터널에 순환이 있는지 없는지 체크하면 된다. import sys n =..

앞 포스트에 이어서 설명하도록 하겠다. 이전까지 할당기가 어떻게 사용가능한 공간을 찾아주는지 알아봤다. 이번에는 할당기가 할당된 공간을 해제(free) 했을 때 생겨나는 빈 공간을 어떻게 처리 할 지에 대해서 알아보자. 사용 가능한 공간 연결 위 그림에서 볼 수 있듯이, 할당기가 공간을 반환할 때 헤더에 있는 allocate bit를 0으로 바꿔주기만 한다. 즉, 자동으로 인접한 빈 공간에 붙혀주는것은 아니다. 만약 자동으로 연결해주었다면 위 그림은 16/0으로 바뀔것이 아니라, 32/0이 됐을 것이다. 다시 위 예시에서, 할당기가 첫번째 그림에서 빨간색으로 표시한 부분을 해제했다고 해보자. 그렇다면 16바이트의 새로운 사용 가능한 공간이 생기는 것이고, 총 32바이트의 사용 가능한 공간이 힙에 존재하게..

malloc, free 우리는 c 프로그래밍에서 러닝타임에 동적으로 메모리를 할당하기 위해서 malloc 함수를 사용한다. malloc을 사용하면 힙 영역에 size만큼 사용할 수 있는 메모리 블럭이 생긴다. 이후 반환된 메모리 주소를 사용해서 원하는 값을 저장할 수 있다. void *malloc(size_t size); malloc을 사용해 메모리 블럭을 할당 했다면 free를 이용해서 힙 영에서 해당 블럭을 반환 해 주어야한다. free 함수 호출 없이 malloc만 한다면 언젠간 힙 영역이 가득 찰 것이고 이는 메모리 누수로 이어질 가능성이 크다. void free(void *ptr); 그래서 메모리 우리는 메모리 영역에 대한 이해를 바탕으로 malloc과 free를 적절히 사용할 필요가있다. 그래..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 이 문제는 동적 계획법을 통해서 해결할 수 있다. dp 테이블에는 x일에 얻을 수 있는 최대 수익이 들어간다. 그래서 x일이 되었을 때, 해당 상담을 진행할 지, 안 할지 선택해서 dp 테이블에 값을 넣어준다. 상담을 할지 안 할지는 두 값중 더 큰 이익으로 정한다. x번째 일을 했을 때 수익(= x일 수익 + 상담에 소요되는 시간 뒤 날짜 최대 수익) 즉 p[x] + dp[x + t[x]] , 해당 날짜에 상담을 하면 소요되는 시간 날짜부터 일 을 할 수 있기 때문 x 번째 일을 안 했을 시 수익, 일을 안 하기에 다음 날짜에서 얻..

해시 해시는 '해시함수(hash function) h를 사용해서 특정 키 k를 테이블에 넣을 때 사용할 인덱스로 변환하는것' 이라고 할 수 있다. 이를 index = h(k) 처럼 나타 낼 수 있으며, 테이블을 T라고 한다면, 키에 대응되는 값 x를 T[h(k)] = x 형식으로 저장 할 수 있다. 보통, 키 k의 갯수는 테이블의 크기 m보다 큰데, 이 때문에 키는 다르지만 해시함수에 의해서 반환되는 값이 같을 때가 생길 수 있다. 이 경우를 '충돌'이 일어났다고 한다. 백문이 불여일견이라고 간단한 해시함수를 보면서 이해해보도록 하자. 해시함수 h를 다음과 같이 정의해보자. 여기서 x는 키를 의미하고 m은 배열의 크기를 의미한다. h(x) = x%m 즉, 해시값은 키를 배열의 크기로 나눈 나머지가 된다...

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 해당 문제는 기본적인 그래프 탐색을 적용하면 풀 수 있는 문제이다. BFS 알고리즘을 사용해서 문제를 풀었는데, 일반적인 문제가 방향벡터가 동서남북 4가지만 존재하는 반면, 해당 문제는 나이트의 이동처럼 특정 좌표에서 대각선을 탐색하는 벡터가 추가적으로 필요하다. 최종적인 방향 벡터는 다음과 같다. dx = [1, 0, -1, 0, -1, -1, 1, 1] dy = [0, 1, 0, -1, ..

우리가 만든 .c 소스코드들의 변수들은 어디에 저장되는 것일까? 그리고 이런 변수들은 언제 불러와지고 언제 소멸될까? 이번에는 이런 궁금증들을 풀어보고자 c언어의 메모리 구조에 대해서 설명하려 한다. 먼저, 프로그램이 실행되기 위해서는 프로그램이 '메모리'라는 저장공간에 로드돼야한다. 이 메모리라는 공간에 우리가 선언했던 변수가 저장되고, 문자열들이 선언되는것이다. 그리고 이러한 저장공간은 운영체제가 만들어준다. 메모리 구성 프로그램 실행시 운영체제에 의해서 만들어지는 메모리의 구조는 다음과 같이 네 영역으로 구분할 수 있다. 이렇게 나눠진 영역별로 저장되는 데이터 유형들이 다 다른데, 한번 살펴보자. 코드 영역 코드영역은 실행할 프로그램의 코드가 저장되는 메모리 공간이다. 따라서 CPU는 코드영역에 저..