https://www.acmicpc.net/problem/4485 난이도 : 골드 4 알고리즘 유형 : BFS , 다익스트라 풀이 시간 : 49분 문제 풀이 목적지까지 가는 데 뺏기는 루피의 최솟값을 구하는 문제이다. 처음에는 단순히 BFS 돌리면 되겠지 ~ 하고 룰루랄라 돌렸는데 아뿔싸 ! BFS를 돌리는 도중, 방문처리를 하게 되면 다른 노드에서 온 값에 대해 처리를 하지 못해 빼앗기는 최소 루피를 구할 수 없게 된다.따라서 나는 다익스트라 알고리즘을 사용해보았다. 다익스트라 알고리즘이란 ? 최단거리를 찾기 위한 알고리즘 중 하나이며, 현재 값과 가중치를 더해 새로운 값과 비교하고, 우선순위큐를 사용하므로 최단거리를 찾을 수 있다.  그런데, 우선순위큐를 구현하고, 실행하자 바로 시간초과가 뜨는 것이..

https://www.acmicpc.net/problem/1240 난이도 : 골드 5 알고리즘 유형 : 그래프탐색, BFS, DFS 풀이 시간 : 15분 + 34분문제 풀이 정점과 정점 사이 비용이 주어진 양방향 그래프를 탐색하는 문제이다. 문제의 풀이 순서는 간단하다. 1. 양방향 그래프를 생성한다.2. `M`만큼 순회하며 정점과 정점 사이 비용을 계산하여 출력한다. 위 방법을 사용하여 정점과 정점 사이의 거리(비용)을 구할 수 있다. 하지만 이렇게 입력이 주어질 때마다 정점의 거리를 구하여 출력하게 되면, $정점의 개수 ≤ 1000$이고, $간선의 개수 ≤ 1000$이기 때문에 C++치고 꽤나 긴 시간이 걸린다. 따라서, 단순히 순회하는 방식이 아닌, LCA 알고리즘을 사용하여 풀게된다면 런타임 시간..

https://www.acmicpc.net/problem/2458 난이도 : 골드 4 알고리즘 유형 : 그래프탐색, BFS 풀이 시간 : 39분 문제 풀이 문제의 입력으로 주어지는 정보는 자신보다 키가 큰 사람의 정보이다. 또한, 이를 단방향 그래프로 연결할 수 있다. 문제에서 물어보고자 하는 것은 자신의 위치를 정확히 아는 사람의 수 이기 때문에, 한 정점에서 다음 정점의 개수와 이전 정점의 개수를 모두 알아야한다. 따라서 나는 정방향 그래프와 역방향 그래프를 생성하여, 각 정점에서 모두 BFS 탐색을 진행한 뒤, 모든 탐색이 끝나고 $현재 정점의 개수 == N - 1$인 경우의 개수를 체크하여 정답으로 출력하였다.그림으로 나타내면 다음과 같다. 코드/*두 학생의 키를 비교한 결과의 일부가 주어짐.N명..

https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : DP 풀이 시간 : 17분 문제 풀이 전형적인 2차원 DP문제라고 생각한다. 문제에서 경로는 오른쪽으로 이동, 아래로 이동 두 가지만 존재하고, (1, 1)에서 (N, M)으로 이동할 수 있는 모든 경로를 찾는 문제이다. 중간에 물웅덩이가 있는데, 이 부분으로는 이동할 수 없다. 사실 격자의 크기가 $N ≤ 100$, $M ≤ 100$으로 주어졌기 때문에 BFS로도 충분히 풀 수 있을 것 같지만, DP..

https://school.programmers.co.kr/learn/courses/30/lessons/43236# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 4 알고리즘 유형 : 이분탐색, 매개변수탐색 풀이 시간 : 51분 문제 풀이 이분탐색은 어떤 값을 조건으로 잡는지가 매우 중요하다. 문제 설명을 간단히 하자면, 징검다리 중 바위 `N`개를 제거하는 모든 경우들 중 거리의 최솟값이 가장 큰 값을 return하라이다. 한 줄로 요약하려니 이해하기 힘들지만 문제에서 설명해주는 예제를 보면 이해가 쉬울 것으로 생각된다. 우선, 변수들의 범위를 확인해보면 $distance ≤ 1..

https://www.acmicpc.net/problem/2457 난이도 : 골드 3 알고리즘 유형 : 그리디  풀이 시간 : 42분 문제 풀이 문제의 조건을 먼저 확인해보면, 1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 라고 명시되어있다. 여기서 우리가 생각해야 할 조건은 2번 조건이다. 정원에 심는 꽃들의 수를 가능한 적게 하며 공주의 요구사항을 만족해아 하기 때문에 우리는 완전탐색, 그리디와 같은 알고리즘을 생각할 수 있다.문제 조건을 확인해보면, 입력으로 주어지는 꽃이 피고 지는 날짜의 개수가 $N ≤ 100000$으로 주어져있다. 완전탐색을 사용하면 시간초과가 ..

https://www.acmicpc.net/problem/1865 난이도 : 골드 3 알고리즘 유형 : 그래프이론, 벨만-포드 풀이 시간 : 1시간 7분 문제 풀이 이 문제를 접하며 벨만포드 알고리즘을 처음 다뤄보았다. 근데 문제에 허점이 많은 것 같다 ... 결론부터 말하자면 접근은 벨만포드 알고리즘으로 하였지만, 풀이 방법은 벨만포드 알고리즘이라고 할 수 없다.그 이유를 면밀히 따져보자. 우리가 흔히 아는 다익스트라 알고리즘의 경우, 현재 정점에서 다음 정점까지 최소한의 비용을 업데이트하며 탐색을 이어나간다. 따라서 다익스트라 알고리즘은 그리디 알고리즘의 원리를 따른다. 하지만, 벨만포드 알고리즘은 모든 정점에 대해서 탐색을 진행해본다. 따라서 완전탐색에 가깝다고 생각한다. 벨만포드 알고리즘이 더 궁..

Adaptive AUTOSAR 구조 AUTOSAR Adaptive Platform은 크게 총 세 가지 기능으로 나눌 수 있다. 1. SoA (Service oriented Architecture) 네트워크를 통해 정의된 프로토콜을 이용하여 서비스를 제공, 소비하는 SW 구조 여기서 말하는 서비스란 ? 기능적인 의미를 가진 소프트웨어 단위를 나타내며, 명시적으로 정해진 인터페이스를 통해 통신한다. 추후 서비스의 종류 및 통신 방법에 대해 다시 다뤄볼 예정SoA는 신호 기반의 통신(Signal-Based Communication)이기 때문에, 보다 유연성과 확장성이 높다는 장점이 있다.SoA의 장점1. 다양한 클라이언트에게 서비스가 가능하다.플랫폼에 독립적이기 때문에, 원하는 SW와 HW의 사용이 가능시스템..

https://www.acmicpc.net/problem/2660 난이도 : 골드 5 알고리즘 유형 : 그래프탐색, BFS 풀이 시간 : 22분 문제 풀이 예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.문제 설명이 조금 헷갈리게 되어있었지만, 잘 읽어보면 궁극적으로 각 회원의 점수는 다른 회원을 만나기까지의 깊이(Depth)와 같다고 생각하면 된다.이를 그림으로 표현하면 다음과 같다.( 검정 숫자 : 정점의 번호 | 빨간 숫자 : 방문 시간 )1번 회원이 모든 회원을 만나는..

Adaptive AUTOSAR란 ??자동차 업계에는 전기차와 자율주행이라는 패러다임이 형성됨에 따라서 차량 분야와 IT의 기술융합이 활발하게 일어나고 있다. 특히 다양한 드라이버를 활용하기 위해 리눅스를 차량에 적용하는 사례가 많다. 하지만, 이전에는 리눅스 OS가 실행되는 프로세서와 차량 기능을 실행하기 위한 AOTUSAR OS가 별도로 분리되어 사용되었다. 이러한 단점을 보완하고,  미래 자동차 기능을 위해 필요한 자원 제공 및 차량 진단과 차량 통신 네트워크/보안의 요구까지 동시에 만족시키기 위한 것이 바로 AUTOSAR Adaptive Platform이다. Adaptive AUTOSAR 특징1. POSIX 기반 운영체제 선택AUTOSAR Classic Platform은 기본적으로 확장성에 따라 운..