본문 바로가기

알고리즘 문제풀이174

[삼성역량테스트] 17825 주사위윷놀이 풀이일시 : 2021-03-13 문제 : 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다. 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다. 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수.. 2021. 3. 14.
[개념정리] Big - O 시간복잡도 표기 알고리즘 문제를 풀면서 언젠간 한 번쯤 마주할 시간초과를 계산해내기 위한 Big-O 표기법이다. 시간복잡도란 실행시간으로 알고리즘의 효율을 측정한다. 연산 Step 의 수 ex 1부터 N 까지 더할 때 int summ(){ int result = 0; for(int i=1; i O(n^2) T(n) = n^4 + n^3 + n^2 + 1 => O(n^4) T(n) = 5n^3 + 10n^2 => O(n^3) Big-O 표기법의 종류 1 log n n n log n n^2 n^3 2^n O(1) : - 데이터의 양과 상관없이 일정한 실행시간을 가진다 - 상수그래프의 모양을 그린다. O(log n) : - 위와 같은 그래프의 모양을 보인다. - 따라서 데이터양이 많아져도 시간이 조금씩 늘어난다. - bina.. 2021. 3. 13.
[알고리즘 문제풀이] 기타 코딩테스트 1-6 문제 : 토지 개발 A씨는 가로 세로의 크기가 1로 이뤄진 작은 칸들이 가로로 N개 연결된 토지를 소유하고 있다. (단, N은 2의 지수 승으로써 2, 4, 8, 16, 32, … 이다) 토지의 각 칸에는 토지를 개발함으로써 얻을 수 있는 이익이 적혀 있으며, 토지는 아래와 같은 형태로 개발한다. 토지를 개발할 때에는 토지를 절반으로 나누어 한쪽 절반에 해당하는 부분을 모두 활용하여 개발해야 한다. 특정 부분을 모두 활용하여 개발할 때 얻을 수 있는 이익은, 해당 부분에서 개발로 얻을 수 있는 이익 중 최댓값이다. 예를 들어, 아래와 같이 토지가 주어져 있다고 하자. 1 3 10 9 6 2 3 2 그렇다면, 아래와 같이 좌/우로 나누어 개발할 수 있는 두 가지 선택지가 있다. 좌 : 1 3 10 9 6 .. 2021. 3. 13.
[알고리즘 문제풀이] 기타 코딩테스트 1-5 문제 : 두더지 게임 A씨는 두더지 게임을 좋아한다. 두더지 게임판은 가로 세로의 크기가 1로 이뤄진 작은 칸들이 모여 가로와 세로의 크기가 N인 N x N 의 크기로 이루어져있고 총 N^2마리의 두더지가 있다. 이 두더지들은 특정 시간에 올라와서 1초 동안 올라와 있는다. 이때 A씨는 1초에 1번만 두더지를 칠 수 있고 A씨가 두더지를 망치로 치게 되면 해당 두더지에 적혀있는 점수를 얻게 되며 망치로 치지 않으면 1초 후에 두더지는 다시 들어간다. 예를 들어, 판의 크기가 2 x 2이고, 아래와 같이 두더지가 올라온다고 하자. 두더지 1 : 1초, 3초, 5초 – 점수 1 두더지 2 : 2초, 4초 – 점수 2 두더지 3 : 1초, 2초 – 점수 3 두더지 4 : 3초 – 점수 4 위와 같이 두더지 1.. 2021. 3. 13.
[알고리즘 문제풀이] 기타 코딩테스트 1-4 문제 : N개의 발판이 주어지고, 각 발판에는 양의 정수 혹은 음의 정수가 적혀있다. 특정 발판을 밟을 경우, 해당 발판에 적혀있는 숫자만큼 좌로 혹은 우로 이동하게 된다. 음수가 적혀 있을 때는 왼쪽으로, 양수가 적혀 있을 때는 오른쪽으로 이동한다. A씨가 5번째 발판에 있으면 발판의 값이 4이므로 오른쪽으로 4칸 이동한다. 만약 A씨가 4번째 발판에 있으면, 발판의 값이 -2이므로 왼쪽으로 2칸 이동한다. A씨는 1번째, 2번째, 3번째 발판에서 발판을 밟기 시작할 수 있다. 그렇게 발판을 하나하나 밟아 나가다가, 이미 밟았던 발판을 다시 밟을 경우 발판 밟기를 종료한다. 예를 들어, A씨가 1번째 발판에서 발판 밟기를 시작할 경우 아래와 같이 발판을 밟아 나간다. 발판의 개수와 각각의 발판에 적혀있.. 2021. 3. 10.
[알고리즘 문제풀이] 기타 코딩테스트 1-3 문제 : 땅콩 먹기 A씨는 N 개의 땅콩을 발견했다. 땅콩은 1차원 수직선 위에 존재하고, i번째 땅콩은 원점으로부터 i 만큼 떨어져 있으며 A씨는 원점으로부터 e 만큼 떨어져 있는 곳에 있다. A씨는 땅콩을 먹는 것을 아주 좋아하지만, 모든 땅콩 중에서 M 개만을 먹을 수 있다. A씨는 기억력이 좋지 않아 지금까지 지나온 길에 빨간 선을 그리는 마법을 부려왔다. 물론 이 수직선에서도 마찬가지이다. 즉, A씨가 수직선 위의 위치 3에서 위치 5까지 움직인다면, 위치 3에서 위치 5까지 총 길이 2의 빨간 선이 그려진다. 단, 이미 빨간 선이 칠해진 곳을 다시 이동하게 될 경우, 새롭게 빨간 선이 그려지지는 않는다. A씨가 N 개의 땅콩 중 M 개의 땅콩을 먹으려 할 때, 그려지게 될 빨간 선 중 최소 길.. 2021. 3. 8.
[알고리즘 문제풀이] 기타 코딩테스트 1-2 문제 : 피시방은 시간당 1,000원으로 이용할 수 있으며 매일 h 시간 동안 p 대의 PC를 운영하고 있다. 피시방은 인기가 많아 예약제로 운영되며 미리 고객들로부터 사용을 희망하는 PC번호와 사용 희망 시간을 전달받아 운영하고있다. 예를 들어 2대의 PC를 활용하여 하루 4시간 동안 영업을 한다고 가정하고 총 7명의 손님으로부터 아래와 같은 예약을 받았을 때 1번 PC를 통해 0원, 2번 PC를 통해 4,000원의 이익을 얻을 수 있다. 예약 PC 사용 희망 시간 1번 10시간 1번 5시간 1번 7시간 2번 10시간 2번 1시간 2번 3시간 2번 7시간 피시방의 상세 조건은 아래와 같다. - 고객이 운영 시간보다 사용 희망 시간을 많이 신청한 경우 해당 고객은 받지 않는다. - 고객은 한 시간 단위로.. 2021. 3. 5.
[개념정리] getline의 사용 getline 은 주로 입력을 전체로 받을 때 사용한다. 사용 : 배열에 cin 으로 넣는 방법. #include using namespace std; int main(){ char a[100]; cin.getline(a,100); cout 2021. 3. 4.
반응형

티스토리툴바