본문 바로가기

ALGORITHM_PRACTICE

 (44)
백준 10164번: 격자상의 경로 백준 10164번: 격자상의 경로 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다. www.acmicpc.net 가장 좌측 상단에서 가장 우측 하단으로 내려올 때 O를 거쳐온 곳의 경로의 수를 구하는 문제이다. 문제를 하나 이해를 제대로 하지 않아 틀렸던 문제이다. 나는 O가 없는 경우에는 가는 방법이 없다고 착각을 했었다. O가 없는 경우에는 모든 경로의 수가 정답이다. 나는 보자..
백준 2631번: 줄세우기 백준 2631번: 줄세우기 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 www.acmicpc.net 문제를 풀다보면 풀지못하는 문제도 있는 법인데 나중에 확인해보니 초등부, 중등부 문제인 것을 알았을 때, 나는 얼마나 걸음마 단계인지 실감하게된다. 이 문제도 풀지못하고 답을 봤..
백준 15664번: N과 M (10) 백준 15664번: N과 M (10) 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net N과 M (9)를 풀었다면 10은 금방 풀 수 있다고 하는데 나는 (9)를 푼지 2달이 넘어서 기억이 잘 나지 않았다. 아무튼 기억을 되살려보고자 이것저것 하다가 9보다 더 간단하게 풀게되었다. 코드도 기존 N과 M시리즈에서 몇줄 추가되지 않았다. 이전에 삽입했던 값을 기억하는 prev 변수를 만들었고, 만일 다음에 들어가야하는 수가 prev값과 같다면 그 수는 생략. 비내림차순으로 정렬된 상태로 답을 출력하기 때..
백준 11559번: Puyo Puyo 백준 11559번: Puyo Puyo 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 뿌요뿌요를 어렸을 때 했던 기억은 있지만 그 때는 재밌는 게임인줄 몰랐다. 고등학생때였나? 뿌요뿌요랑 조금은 다르지만 비슷한 게임인 애니팡을 즐겨했던 것 같다. 그것도 한달도 안하고 접긴했지만 문제에 대한 이해는 뿌요뿌요 게임을 원래 알고있어서 블록이 터지고 움직이는 과정이 어떤지는 이해가 되었다. 여기서 구하는 것이 어떤 것인지만 확인하고 시뮬레이션 코드를 작성하면 된다. 시뮬레이션 코드에 딱히 정답은 없고 남이 작성한 시뮬레이션 코드를 보기란 쉬운것이 아닌 것 같다. 시뮬레이션은 그냥 작동 순서를 이해하고 직..
백준 2011번: 암호코드 백준 2011번: 암호코드 2011번: 암호코드 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어. 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", " www.acmicpc.net DP 문제는 언제풀어도 어려운 것 같다. DP는 풀이방법을 종이에다 손으로 직접 써봐야 알 수 있는 것 같다. 암호코드 문제는 생각해내는 것은 어렵지않은줄 알았는데 다른 사람들..
백준 1193번: 분수찾기 백준 1193번: 분수찾기 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 2차원 배열인데 시간 제한이 0.5초이네? 이것을 보자마자 간단한 규칙으로 풀 수 있을 것 같은 생각이들어서 규칙을 먼저 찾기 시작했다. 난 규칙을 찾는 기준을 1번째 3번째 6번째 10번째 15번째 위치에있는 분수들로 잡았다. 저 분수들은 다 테두리에 있는 분수들이다. 이 분수들의 표를 1/1가 꼭대기인 삼각형 모양으로 만들었을 때 1/1(1번)은 1번째 2/1(3번)는 2번째 1/3(6번)은 3번째 4/1(10번)은 4번째줄에 나타나는 것을 확인했다. 이것을 보아 홀수번째 줄과 짝수번째 줄에 있을 때 내가 고른 분수들이 삼각형 기준 맨 좌측에 있냐 맨 우측에 있냐..
백준 2225번: 합분해 백준 2225번: 합분해 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP문제는 규칙을 먼저찾는게 우선이라고 생각한다. 규칙을 찾기위해서 수를 종이위에 어느정도 써본 결과 일정한 규칙이 있다는 사실을 알아냈다. dp[n][k]의 값은 dp[0][k-1] + dp[1][k-1] + ... + dp[n][k-1] 의 값을 가진다는 것을 알아내었다. 따라서 n이 0일때의 값만 1로 초기화를 해준 뒤 이후의 값들은 공식을 코드로 구현하여 해결했다. 마지막에 1,000,000,000을 나누는 것을 잊지말자 #include #define DIV 1000000000 using namespace std; long long dp[201][201];..
삼성 SW Expert Academy 1204. [S/W 문제해결 기본] 1일차 - 최빈수 구하기 삼성 SW Expert Academy 1204. [S/W 문제해결 기본] 1일차 - 최빈수 구하기 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com 최빈수 구하는 문제로 학생수가 1000명으로 고정되어 있다. 점수는 0점부터 100점까지이므로 배열은 101까지만 선언하고 학생들의 점수가 입력되면 해당 점수로 배열 인덱스에 있는 값을 하나씩 증가시킨다. 그러면 전체 성적들의 분포수를 배열에서 가지게된다. 그 다음에 최빈수를 찾아 출력하면 된다. #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int ..

티스토리툴바