[C++] 2042 : 구간 합 구하기(세그먼트 트리 풀이)
·
Baekjoon
https://www.acmicpc.net/problem/2042세그먼트 트리라는 자료구조를 공부해야지..공부해야지 하다가 미뤄놨는데, 삼성 코딩테스트를 준비하면서 공부를 했다. 구현이 복잡해 보였지만, 결국 분할 정복 테크닉을 구간합에서 구현한 것이라는, 생각보다 쉬운 자료 구조였다. 공부할 때는 개발자 영맨님의 유튜브 영상을 참고했다. 현재 나와있는 어느 자료보다 본질적인 부분에 대해서 잘 설명하신 것 같다. 영상을 보고 이 포스트를 보면 되겠다(포스트는 대충 적어놔서 영상 안보고오면 이해가 안 될 것이다..)https://www.youtube.com/@bluedawnstar 개발자영맨(bluedawnstar) www.youtube.com 알고리즘 분류세그먼트 트리분할 정복 알고리즘문제 설명문제 접근..
[C++] 23289 : 온풍기 안녕!
·
Baekjoon
백준에서 가장 인기 있는 문제집은 삼성 SW 역량 테스트 A형 문제집이다.https://www.acmicpc.net/workbook/view/1152이 중에서 어려운 문제에 속하는 "온풍기 안녕!"을 풀어보자.알고리즘 분류너비 우선 탐색 (BFS) 문제설명https://www.acmicpc.net/problem/23289while loop을 돌며 다음 단계를 거친다.바람 나옴온도 조절가장자리 온도 1 감소초콜릿 먹기온도 검사이 각각의 부분을 함수로 구현하면 된다. 문제접근1. 바람 나오는거 구현하기바람은 세 방향으로 퍼지는데, 그림으로 표현하면 다음과 같다. 우선 동쪽으로 바람을 쏘는 온풍기를 나타내면 다음과 같다. 문제와 다르게, y를 아래방향, x를 오른쪽 방향으로수정했다.우선 (y,x)에서 오른쪽으..
[FreeRTOS] 1. FreeRTOS Task 관련 API(1)
·
FreeRTOS
https://www.freertos.org/Documentation/02-Kernel/07-Books-and-manual/01-RTOS_book FreeRTOS Documentation - FreeRTOS™ freertos.org포스트를 시작하기 전, AWS에서 제공하는 공식 튜토리얼 가이드가 있는데, Real Time OS가 뭔지? 시분할 시스템이 뭔지? 선점/비선점 스케줄링이란? ... 궁금해하는 분들에게는 좋은 자료가 될 것 같다.본격적으로 시작하면서, 새롭게 API를 이제 배워야하는데 정리하기 귀찮고, 이걸 보는 분들도 귀찮을 거라고 생각한다. 그래서, 좀 더 흥미를 높이기 위해 main.c 에서 freeRTOS를 도입했을 때 어떻게 함수가 진행되는가??? 를 중점으로 알아보자.우선 FreeRT..
[FreeRTOS] 0. STM32F411RE 환경 설정
·
FreeRTOS
FreeRTOS는 여러 모로 한물 간 OS이다. mcu의 컴퓨팅 속도가 너무나도 좋아지고, 자동차에서는 AUTOSAR OS가 표준으로 적용되어서 쓸 데가 없다. 하지만 임베디드 디바이스에서 스케줄러를 간단하게 구현할 수 있고, 무엇보다 아직 방산 산업 분야와 같이 진짜로 실시간성이 중요한 경우에는 많이 쓰이고 있다. 예를 들어 LIG넥스원의 Job Description을 보면,위와 같이 FREE RTOS 가능자를 선호하는 걸 알 수 있다. 그럼 ST사의 mcu 를 이용해서 freeRTOS를 공부해보자. FreeRTOS는 오픈소스라서 미들웨어 형태로 포팅해서 사용할 수 있다.우선 우리의 친구 STM32CUBEMX를 사용한다면 기본 peripheral 설정을 알아서 해준다.Yes 눌러 주면 다음과 같은 화면..
[삼성기출/C++] 미지의 공간 탈출
·
CodeTree
이 문제는 필자가 코딩테스트에서 틀렸던 문제이다. 다시 풀어보니, 단 한 부분...에서 잘못되었다는 점을 깨달았다알고리즘 분류너비 우선 탐색 (BFS)시뮬레이션문제 설명https://www.codetree.ai/ko/frequent-problems/problems/escape-unknown-space/description?introductionSetId=&bookmarkId= 삼성 코딩테스트 기출 문제 설명: 미지의 공간 탈출 | 코드트리삼성전자 코딩테스트 기출 문제 미지의 공간 탈출의 상세 설명입니다. 문제 요구사항을 정확히 파악하고 효율적인 알고리즘을 설계해보세요.www.codetree.ai위와 같은 3차원 공간에서, 시간 이상 현상(빨간색)이 정해진 방향에서 주어진 시간마다 하나씩 전진한다. 타임머..
[삼성기출/C++] 메두사와 전사들
·
CodeTree
삼성 공채 시즌이 다시 한 번 돌아왔습니다. 모두 화이팅입니다. 그럼 달려봐야겠죠.. 알고리즘 분류너비 우선 탐색 (BFS)깊이 우선 탐색 (DFS)기하 (Gemometry)시뮬레이션 문제 설명문제가 너무 길어서 사이트를 참고하자.https://www.codetree.ai/ko/frequent-problems/problems/medusa-and-warriors/description?introductionSetId=&bookmarkId= 삼성 코딩테스트 기출 문제 설명: 메두사와 전사들 | 코드트리삼성전자 코딩테스트 기출 문제 메두사와 전사들의 상세 설명입니다. 문제 요구사항을 정확히 파악하고 효율적인 알고리즘을 설계해보세요.www.codetree.ai 문제 접근삼성기출은, 일반적인 코딩 테스트의 "원리"..
[C++] 4991 : 로봇 청소기(외판원 순회 풀이)
·
Baekjoon
https://www.acmicpc.net/problem/4991 배열을 통해 적용할 수 있는 고급 테크닉들이 적용된 문제이다. 현대오토에버는 최근 AUTOSAR Classic 직무에 대해서 C 언어로만 응시할 수 있도록 프로그래밍 언어를 제한했는데, 이 경우 배열을 이용한 고난도 문제들이 등장한다. (priority queue는 구현하는데만 한 세월..이므로) 따라서 배열을 이용해서 문제를 풀어야 하는데, 그 중에서도 고급 테크닉인 DP와 비트마스킹 정도인데, 이것들이 짬뽕된 문제이다. 알고리즘 분류다이나믹 프로그래밍비트마스킹외판원 순회 문제(Traveling Salesperson Problem)너비 우선 탐색(BSP) 문제설명 예를 들어 이런 input이 들어오면,7 5........o...*.....
[C++] 11066 : 파일 합치기
·
Baekjoon
https://www.acmicpc.net/problem/11066 이전 포스트로 "행렬 곱셈 순서"에 대해서 두 가지 방식의 다이나믹 프로그래밍으로 문제를 풀어봤다.https://gg4ever1724.tistory.com/39 [C++] 11049: 행렬 곱셈 순서https://www.acmicpc.net/problem/11049 두 가지 방법으로 연습해보자.알고리즘 분류다이나믹 프로그래밍 문제설명 행렬은 교환법칙이 성립하지 않지만, 결합법칙은 성립한다. 그래서 예를들어, ABC의gg4ever1724.tistory.com 이 포스트처럼 이번 파일 합치기 문제도 두 방법으로 풀되, 우선적으로 상향식 방법을 연습하자. 알고리즘 분류다이나믹 프로그래밍 문제설명 문제접근 어떻게 보면 행렬 곱셈 순서보다는 덜..
[C++] 11049: 행렬 곱셈 순서
·
Baekjoon
https://www.acmicpc.net/problem/11049 두 가지 방법으로 연습해보자.알고리즘 분류다이나믹 프로그래밍 문제설명 행렬은 교환법칙이 성립하지 않지만, 결합법칙은 성립한다. 그래서 예를들어, ABC의 곱을 구할 때에는 B x A x C 이렇게 하면 안되지만,A x (B x C) 이렇게 하면 된다는 이야기다. 이 과정에서 행렬 곱을 구할 때 가장 작은 곱셈의 연산 횟수의 최솟값을 구하자는 것이다. 아이디어는 간단하고, 실제 최적화 작업에도 도움이 될 만한 로직이다. 문제접근우선 완전탐색으로 이 문제를 풀 수 있을지! 에 대해 알아보자.for loop 을 돌면서 괄호를 잡을 것이다. 우선 ABCD의 곱을 구한다고 가정하고, 현재 index = B 라고 생각하자. 그렇다면, 여기에서는..
[C++] 2749: 피보나치 수 3
·
Baekjoon
https://www.acmicpc.net/problem/2749 피보나치 수를 구하는 재미있는 방법을 알게 되어 공유한다. 알고리즘 분류분할 정복다이나믹 프로그래밍 문제설명 문제는 아주 간단하다. 다만, n이 1e18이다. 일단 n은 long long으로 받아야 한다. 그리고 MOD값은 1e6이므로, 결과값 역시 안전하게 long long으로 받아주자. 문제접근 우선 피보나치 수열의 점화식은 다음과 같다. 이 방법으로 f(n)을 구할 수 있지만, n이 1억을 넘어가기 때문에 시간 초과에 해당한다. 즉 O(logN)으로 풀어야 한다. 그러면 어떻게풀어야할까? O(logN)으로 해결할 수 있는 알고리즘은 많지 않다. 분할 정복 말고는 풀이를 찾기 어려울 것이다. 따라서 이 문제를 분할 정복으로 풀어보자...
[C++] 11401: 이항 계수 3
·
Baekjoon
https://www.acmicpc.net/problem/11401 이항 계수 3이라는 문제를 풀었는데, 여기서 사용된 수학 개념과 테크닉은 향후 유용하겠다 싶어서 정리한다. 사용되는 기법유클리드 호제법페르마의 소정리O(logN) 거듭제곱 모듈로 계산(분할 정복)다이나믹 프로그래밍 문제의 접근문제는 매우 간단하다. 이항 계수를 1e9+7로 나눈 나머지를 구하면 된다. 일반적으로 이항 계수를 구하는 방법은 다음과 같이 팩토리얼을 이용한다. 여기서 MOD 연산이추가되어야 할 것이다. 최대 400만 팩토리얼을 구해야 하기 때문에 MOD를 통해 줄여야 한다. 우선 여기까진 당연히 맞다. 그러면 계산을 다음과 같이 해야할까? 아니다. 뭔가 이상하다. modulo 연산은 다음과 같이 덧셈(=뺄셈)과 곱셈에만 적..
[부트캠프] 현대오토에버 모빌리티 SW스쿨(임베디드 4기) 합격 후기
·
취준
https://edu.rapa.or.kr/recruitment/428 RAPA DX캠퍼스 - 현대오토에버 모빌리티 SW 스쿨 2기본 과정은 고용노동부가 주최하고 디지털선도기업인 현대오토에버&현대엔지비와 전문교육기관인 한국전파진흥협회가 주관하여 공동 운영하는 K-디지털 트레이닝의 디지털선도기업아카데미edu.rapa.or.kr 25년도 상반기 취업준비 시즌이 본격적으로 시작되었습니다. 역대급 또대급 취업난이지만, 이 글을 보는 취준생 여러분들(저를 포함) 모두 좋은 결과 있기를 바랍니다. 아무래도 프로젝트 경험이 부족한 저같은 분들이 부트캠프를 지원할 거라고 생각하는데, 지금 3개월 정도 이수를 했는데 정말 만족하면서 듣고 있고, 수준 높은 강사님들, 교수님들이 강의해주십니다. 현대오토에버를 비롯한 현대차 ..
[Datasheet] 6. AVR CPU Core
·
ATmega328p Datasheet
https://ww1.microchip.com/downloads/en/DeviceDoc/Atmel-7810-Automotive-Microcontrollers-ATmega328P_Datasheet.pdf Overview Datasheet에 의하면, AVR은 Harvard Architecture를 사용한다고 한다. 일반적으로 아키텍처 시간에 배운 Von-Neumann Architecture와는 무엇이 다를까? 바로 메모리와 버스 측면에서 다르다.메모리 측면Von Neumann architecture: 프로그램 코드와 데이터를 동일한 메모리 공간에 저장 -> 설계가 단순하지만 명령어와 데이터를 동시에 접근할 수 없기 때문에 성능 저하Harvard architecture: 프로그램과 데이터를 독립된 메모리 공..
[Datasheet] 2. Overview
·
ATmega328p Datasheet
https://ww1.microchip.com/downloads/en/DeviceDoc/Atmel-7810-Automotive-Microcontrollers-ATmega328P_Datasheet.pdf 우선 ATmega328p의 Block Diagram을 보면서 전체적인 구조를 파악해보자. 여기서, AVR Core의 경우는 AVR CPU로 abstraction 되어 있다. 이 그림에서 중요한 것은 AVR의 주변기기(peripheral)이다. 아직 AVR을 처음 배우는 입장에서 뭔가 많은 peripheral이 있지만, 이럴수록 Top-Down 방식으로 차근차근 접근하는게 좋다. 우선 점선으로 표시된 부분 밖에서 오는 외부 신호에 주목해보면, 저번에 배웠던 내용을 복습할 수 있다.PD, PB, PC로 in..
[Datasheet] 1. Pin Configurations
·
ATmega328p Datasheet
1. Pin Configurations ATmega328p에서 정의하는 여러 가지 pin들에 대해 알아보자. VCC - digital supply voltageGND - groundPort B (PB7:0)bi-directional IO : 8bit 짜리 레지스터에 읽고 쓰기가 모두 가능하다는 것이다.internal pull-up : 풀업저항을 세팅해서 안정적으로 High 상태를 유지한다. internal하므로 풀업 저항을 따로 달아주지 않고 프로그래머가 풀업 저항을 activate하면 풀업 상태가 된다.symmetrical drive characteristics : 소스 전류와 싱크 전류 모두 가능하다는 말로, 즉 출력이 HIGH도 되고 LOW도 된다는 것을 의미한다.tri-stated : 리셋하면..
gg4ever1724
상단으로

티스토리툴바