전자공학 및 알고리즘

문제 링크입니다. https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net DFS를 사용한 문제입니다! 이동시 확률 계산이 조금 까다로운 문제였습니다. 예를 들어서 2번을 이동하고, 동서남북 이동 확률이 각각 25%라고 하겠습니다. 동->서 / 서->동 / 남->북 / 북->남 의 경우를 제외하면 전부 단순한 이동입니다. 따라서 동 -> 동,남,북 으로 이동하면 되는데 동서남북의 경우가 있으니 전부 계산하면 1/4*1/4*3*4인 75%가 됩니다. ..

문제 링크입니다 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net DFS에 익숙하지는 않아 https://yabmoons.tistory.com/117 님의 접근 방식을 참고했습니다. DFS, BFS를 모두 사용한 문제입니다 1번 기능을 구현하는 함수, 3번과 4번을 구현하는 함수와 2번 기능을 구현하는 함수로 나누어서 풀었습니다. 접근방법 1. DFS를 통해 7명의 학생을 뽑습니다. (1,2,3,4,5,6,7)이나 (7,6,5,4,3,2,1)은 똑같..

문제 링크입니다 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net K의 값이 주어졌을때, B[K]의 값을 구하는 문제입니다. N의 값이 최대 10^5이라서 이분 탐색을 하지 않는다면 시간 초과가 나는 문제였습니다. 푸는 방법이 도저히 떠오르지 않아 꾸준함님의 포스팅을 참고했습니다. https://jaimemin.tistory.com/988 백준 1300번 K번째 수 문제 링크입니다: https://www.acmicp..

문제 링크입니다 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 깊이 우선 탐색(BFS) 문제였습니다. 문제 조건입니다. 한번 지나간 알파벳은 지나가지 않고 최대로 갈 수 있는 횟수를 구하는 문제입니다. 예를 들어 CAAB ADCB 의 경우에는 C -> A -> D 총 3번이 됩니다. 접근 방법 1. 26칸을 가진 배열을 선언해 이동중에 어떤 알파벳이 입력되었는지 저장한다. 2. 상, 하, 좌, 우를 확인하여 갈 수 있는 경로를 확인한다..

문제 링크입니다 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 길이 주어졌을때 다음과 같은 방식으로 경사로가 만들어집니다. 그림에서 위 경우에는 높이 차가 1이며, 경사로를 놓을 수 있는 구간 길이가 2이상이기에 경사로를 설치할 수 있습니다. 아래 경우에서는 1번 그림에서는 높이 차가 2이기 때문에 2번 그림에서는 경사로가 바닥에 닿아있지 않기 때문에 3번 그림에서는 경사로가 곂쳐서 놓였기 때문에 4번 그림에서는 기울여졌기 때문에 경사로를 놓지 못합니다. 왼쪽 그림..

문제 링크입니다 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 삼성 SW 역량테스트 문제입니다. BFS를 이용해 풀었습니다. N*N의 입력이 주어졌을 때, 위의 조건을 따라서 인구 이동이 시작합니다. 왼쪽 그림은 인구 이동 전, 오른쪽 그림은 인구 이동 후의 모습입니다. 모든 나라가 국경선을 공유하기에 전부 인구가 달라진 모습을 볼 수 있습니다. 접근 방법 1. 이중 for문을 통해서 check배열의 값이 0일때 해당 칸부터 B..

문제 링크입니다 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 삼성 SW 역량 테스트 문제입니다. BFS를 이용하여 풀었습니다. 1. 현재 택시의 좌표에서 가장 가까운 손님에게 찾아간 뒤, 목적지까지 간다. 2. 목적지에서 가장 가까운 손님을 찾아간 뒤, 손님의 목적지까지 간다. 2 - 1. 가장 가까운 손님이 많을 경우, 행이 작은순으로 행이 같은 손님이 있을 경우 열이 작은 순으로 정렬한다. 3. 1..

문제 링크입니다 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 삼성 SW 역량 테스트 문제입니다. 아기 상어는 위와 같은 규칙으로 움직입니다. 문제를 해결하기 위해서 구현해야 할 기능은 상, 하, 좌, 우로 움직이며 갈 수 있는 칸 찾기, 규칙에 따라서 갈 수 있는 칸 정렬, 아기 상어의 정보 변경하기를 구현해야 합니다. 1. 기본 설정 아기 상어가 갈 수 있는 칸 중에서 자신이 먹을 수 있는 물고기가 있을 수 있습니다. 그렇다면 그 ..

문제 링크 입니다 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS 문제입니다. 이렇게 4개의 연산을 할 수 있는 할 수 있는 계산기가 있습니다. 이 계산기에는 0 이상 10000이하의 수를 저장할 수 있다고 할 때 수 A에서 수 B로 바꿀 수 있는 최소 횟수의 연산을 구하는 문제입니다. 각각 연산을 구현한 다음에 BFS를 통해서 A에서 B까지의 연산 과정을 저장하면 됩니다. 처음에 vector를 이용해 연산 과정을 저장했지만..

문제 링크입니다 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제입니다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다. 가장 긴 증가하는 부분수열 4번과는 다르게 범위가 1,000,000입니다. 따라서 이중 for문을 사용한다면 시간초과가 ..

문제 링크입니다 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제입니다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다. 이때 가장 긴 길이인 4와 수열 10,..

문제 링크입니다 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 합니다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, ..