Do you believe in you?

[문제] 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net [풀이] N이 1일 때, N이 2일 때, N이 3일 때를 손으로 그려보며 규칙을 찾았다. 아래 그림 참조. 즉, N이 1일 때는 가장 큰 값을 제외하고 5개를 더해주면 되고, N이 1보다 클 때는 다음과 같은 공식이 있었다. - 면이 3개 보이는 주사위 개수: 4 - 면이 2개 보이는 주사위 개수: (N-1)*4 + (N-2)*4 - 면이 1개 보이는 주사위 개수: (N-2)*(N-2) + (N-2)*(N-1)*4 공식을 구해서 ..

[문제] 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 55-50+40 같은 식이 주어졌을 때, 괄호를 알맞게 쳐서 최소 합을 구하는 문제 예시 답은 55-(50+40) = -35 이다. [문제풀이] 경우의 수를 여러개 만들어서 계산해보며 규칙을 찾아야 한다. -가 없을 때, -가 가온데 껴있을 때, -가 계속 있을 때, - + 가 반복 될 때 등등... 10+11-5+4 = 10+11-(5+4) = 12 1+10-15-10+20-1 = 1+10-(15+10)+20-(1) = 5 위 두가지 경우를 살펴..

[문제] 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net [문제설명] 스도쿠 게임의 답을 찾는 문제 ~! 스도쿠 게임 조건은 아래 2가지다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. [문제 풀이] 첨엔 예시만 보고 가로, 세로, 3x3을 탐색해서 한칸만 비어서 바로 풀수 있는 칸을 풀고 다음 칸을 푸는 방식으로 구현했다. 결과는 대망... 아래 반례처럼 빈칸이 많을 때도 포함..

[문제] 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net [문제설명] 사회망 서비스(SNS)에 속한 사람들은 얼리 아답터이거나 얼리 아답터가 아니다. 얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다. 어떤 아이디어를 사회망 서비스(SNS)에서 퍼뜨리고자 할 때, 가능한 한 최소의 수의 얼리 아답터를 확보하여 모든 사람이 이 아이디어를 받아들이게 하자. 얼리어답터의 조건은 다음과 같다. - 얼리 어답터가 아니면, 모든 친구들이 얼리 어답터야 한다. - 얼리 어..

문제 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 이 문제를 풀 때 중요한 점은, 물고기를 한마리 먹을 때 마다 그리고 물고기 크기가 늘었을 때 마다 먹을 수 있는 물고기를 재탐색해야 한다는 것이다. 물고기를 한 마리 먹었으면, 그자리로 이동해서 다시 가장 가까운 && 가장 위에 있는 && 가장 안쪽에 있는 물고기를 다시 찾아야하기 때문이다. 그리고 물고기 크기가 늘었다면, 먹을 수 있는 물고기가 늘어날 것이기 때문이다. 물고기를 탐색하는 부분은, 가장 가까운 물고기가 최우선이므로 최단거리 찾기..

[문제] 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 스코빌 지수가 가장 낮은 두가지 음식을 섞어서 모든 음식이 K이상의 스코빌 지수를 가지게 하려 할 때 필요한 최소 연산 횟수를 구하는 것. [풀이] 처음엔 걍 STL algorithm의 sort() 함수로 scoville 벡터를 내림차순 정렬하고 scoville 벡터의 가장 작은 값과 두번째로 작은 값을 K보다 커질 때까지 연산하는 과정을 반복했다. 결과는 효율성 테스트 0점. #include #include using namespace s..

* Heap(힙) : 최대값/최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 형태의 자료구조 (완전 이진 트리: 마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있고, 마지막 레벨의 node들은 가능한 한 왼쪽부터 채워져 있는 구조) : 삽입/삭제/최대값 찾기/최소값 찾기에 걸리는 시간복잡도 O(logN) : root가 최대 값을 갖는 최대 힙(Max Heap)과 root가 최소 값을 갖는 최소 힙(Min Heap)이 있음 : 값이 '왼쪽 자식 < 부모 < 오른쪽 자식' 순으로 크기가 큰 이진 탐색 트리(Binary Search Tree)와 달리 '자식 < 부모' 형태의 값 크기만 유지됨. : Heap 자료구조를 응용한 대표적인 예) Priority q..

[문제] 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net [문제설명] 인접한 두 칸을 골라서 사탕을 교환한 후, 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 찾는 문제이다. [문제풀이] 이 문제의 함정은 서로 다른 색깔의 인접한 두 칸이 아닌 걍 인접한 두 칸이라는 점인 것 같다. PPPP 처럼 교환하지 않을 때 가장 긴 연속 부분을 가질 수도 있기 때문이다. 나는 인접한 두 칸을 선택하기 위해 int dir[2][2] = { {0,1},{1,0} } 오른쪽과 아래에 해당하는 방향키 배열을 만들었다. 그리고 2중 for문을 사용해서 모든 좌표를 탐색해줬다.(brute force) for (int i = 0; ..

프로그램 구현 전에 시간복잡도를 미리 계산해봐야한다. 문제에서 주어지는 시간/메모리 제한을 벗어나는 지를 확인해봐야하기 때문이다. * 탐색 횟수당 걸리는 시간 1억 (100,000,000 = 10^8 ) → 1초 10억 = 1,000,000,000 = 10^9 → 10초 예를 들어 int는 4byte로 -2,147,483,648~ 2,147,483,647 범위이기 때문에 크기로 보면 "21억"이며 for문으로 탐색한다면 21초가 소요된다. * 시간 복잡도 Big-O(빅오) 크기 비교 O(1) < O(log n) < O(n) < O(n log n) < O(N^2) < O(2^n) < O(n!) < O(n^n) * N=1억 이라고 했을 때, 빅오표기법에 따른 실행시간 즉, 실행시간이 1초로 제한되어 있다면 ..

[문제] 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net [문제설명] n가지의 동전이 있을 때, 이 동전들을 적당히 합쳐서 k원이 되게 하는 경우의 수를 찾는 것. [풀이] Bottom-up 방식으로 1을 만드는 방법, 2를 만드는 방법, 3을 만드는 방법, ... 10을 만드는 방법까지 구할 것이다. 이 때, 2,3,...을 만드는 방법을 이전에 구한 값을 이용할 것이다. 문제에서 주어진 1,2,5 동전으로 생각해보면, 1,2,5로 1을 만드는 경우의 수는 1 한가지이다. 1,2,5로 2를 만드는 경우의 수는..