programmer life guidance 101

https://www.acmicpc.net/problem/1174 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 1366 515 432 41.659% 문제 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 숫자라고 한다. 예를 들어, 321와 950은 줄어드는 숫자이고, 322와 958은 아니다. N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. (가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.) 입력 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 N번째 작은 줄어드는 수를 출력한다. 예제 입력 1 1예제 출력 1 0코드 비트마스킹..

https://www.acmicpc.net/problem/1168 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) 출력 예제와 같이 요세푸스 순열을 출력..

https://www.acmicpc.net/problem/1167 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 16697 6017 4382 35.067% 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다. 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째..

https://www.acmicpc.net/problem/1158 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 42044 20375 14627 48.405% 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K..

https://www.acmicpc.net/problem/1107 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 43887 10219 6970 22.347% 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램..

https://www.acmicpc.net/problem/1076 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 16623 6600 5656 40.034% 문제 전자 제품에는 저항이 들어간다. 저항은 색 3개를 이용해서 그 저항이 몇 옴인지 나타낸다. 처음 색 2개는 저항의 값이고, 마지막 색은 곱해야 하는 값이다. 저항의 값은 다음 표를 이용해서 구한다. 색 값 곱 black 0 1 brown 1 10 red 2 100 orange 3 1000 yellow 4 10000 green 5 100000 blue 6 1000000 violet 7 10000000 grey 8 100000000 white 9 1000000000 예를 들어, 저항에 색이 yellow, violet, r..

https://www.acmicpc.net/problem/1062 문제 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다. 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N과 K가 주어진다..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 MN 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 88 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다..

> 비트마스킹 bitmask : 정수의 이진수 표현을 자료구조로 쓰는 기법 데이터들은 0과 1의 집합이라고 합니다. 비트는 네트워크 외에도 운영체제 등에서도 자주 접할 수 있는데요 때문에 최적의 성능을 위해 여러 곳에서 쓰이고 있습니다. 이진 숫자로 0, 1 값을 가질 수 있고 이에 따라 true/false, on/off 와 같은 상태를 나타내는 것이 가능합니다. 비트마스크 장점 먼저 비트마스킹의 장점을 알아 보겠습니다. 빠른 수행시간 시간복잡도 O(1)에 구현되는 것이 많습니다. 비트마스크를 사용할 수 있다는 말은 원소의 수가 많지 않다는 뜻이기 때문에, 큰 속도 향상을 기대할 수는 없지만 여러번 수행해야 하는 경우에는 작은 최적화도 큰 속도 향상을 가져올 수 있습니다. 간결한 코드 양한 집합 연사자들..

콜드부팅, 웜부팅 부팅 이란 컴퓨터를 처음 켰을 때, 사용자가 작업을 할 수 있는 상태로 만드는 것입니다. 부팅종류에 따라서 BIOS에서 POST(Post On Self Test) 자기진단시험 검사단계를 거친 후, BIO는 MBR(Master Boot Record)를 읽어서 메모리에 상주시킨 뒤 MBR 코드를 수행시킵니다. 이후, MBR에 포함된 부트로더에서 부팅이 가능한 파티션을 찾은 후 OS를 수행시키는 것입니다. 그럼 이제 콜드 부팅(Cold Boot) 과 웜 부팅(Warm Boot)을 알아보겠습니다. 콜드 부팅 주요 부분에 전기가 통하지 않고, 전원이 모두 꺼져 있던 상태에서 전원 스위치를 눌러 컴퓨터를 다시 키는 것 POST 검사 단계를 거친다. 컴퓨터에 무리를 줄 수 있으므로 가급적이면 피하는..

> Prefix Sum 누적 합, 구간 합 누적합 또는 구간 합을 빠르게 구하는 알고리즘입니다. 여기서 주의해야할 것은 부분 합 은 0 ~ k까지의 합을 의미하는 것이고 구간 합은 a ~ b까지의 합을 의미 합니다. 이러한 알고리즘은 어디에 쓰일까요? 아래와 같은 문제를 예시로 봅시다. int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 배열이 존재한다. 이 때 a에서 b의 구간 합을 요구하는 쿼리 "2천만개"가 들어온다. 이러한 문제에 대해 어떻게 해결 할 것인가? 가장 쉬운 방식은 브루트 포스를 이용해 일일이 더하는 것입니다.하지만 쿼리 2천만개를 1초만에 해결해달라고 요구 했을 때, 이 코드의 시간복잡도를 보면 쿼리 2천만개 * (a에서 b의 합 구하는 for 문의 최악..

RTOS 환경에서 워치독 사용하기 현업 골칫거리 중 하나인 WDT에 대해서 알아보려고 합니다. 먼저 그 중요성에 대해서 알아보겠습니다. 우주 환경에 장기간 노출 된 상태에서 센서와 우주선 구성 요소를 테스트하는 NASA 위성 인 Clementine 은 1994 년 1 월 25 일에 발사되었습니다. 몇 줄의 감시 코드가 부족하여 1994 년 5 월 7 일에 임무를 잃었습니다. 클레멘 타인은 달 궤도를 떠나 그녀의 다음 목표 인 지구 근처의 소행성 Geographos로 향했을 때 약 2 개월 연속 달지도를 수행했습니다. 그러나 곧 Clementine의 온보드 컴퓨터 중 하나에서 오작동이 발생하여 NASA가 우주선 작동을 효과적으로 차단하고 추진기 중 하나가 제어되지 않은 상태로 발사되도록했습니다. NASA는..

Memory Block Pools Allocating memory in a fast and deterministic manner is always a challenge in real-time applications. With this in mind, ThreadX provides the ability to create and manage multiple pools of fixed-size memory blocks. Since memory block pools consist of fixed-size blocks, there are never any fragmentation problems. Of course, fragmentation causes behavior that is inherently un-de..

Event Flags Event flags provide a powerful tool for thread synchronization. Each event flag is represented by a single bit. Event flags are arranged in groups of 32. Threads can operate on all 32 event flags in a group at the same time. Events are set by tx_event_flags_set and are retrieved by tx_event_flags_get. Setting event flags is done with a logical AND/OR operation between the current eve..

Mutexes In addition to semaphores, ThreadX also provides a mutex object. A mutex is basically a binary semaphore, which means that only one thread can own a mutex at a time. In addition, the same thread may perform a successful mutex get operation on an owned mutex multiple times, 4,294,967,295 to be exact. There are two operations on the mutex object, namely tx_mutex_get and tx_mutex_put. The g..