백준
백준 4375 1(C++)
* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다 백준 4375 1 입니다 문제 풀이 이문제를 처음 봤었을때 살짝 이해가 안되었습니다 우선 n은 2 와 5 로 나누어 떨어지지 않는 정수 즉 (n % 2) && (n % 5) 라는 부분은 쉽게 이해가 되었습니다 그러나 그 다음부분인 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오 에서 이해가 잘안되었습니다 1로만 이루어진... 처음에는 소수인가?.. 라는 생각이 들었지만 풀이를 확인해보니 정말로 1 로만 이루어진 숫자였습니다.. 즉 1 - 11 - 111 - 111 ... 와 같이 모든 자리수가 1로만 이루어진 숫자입니다 이러한 숫자가 n의 배수일때 이숫자의 자리수를 출력하면 되는 문제입니다 그러면 첫번째 1로만 이루..
백준 1629 곱셈(C++)
* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다 백준 1629 곱셈입니다 문제 해석 일단 이문제 같은경우는 문제만 봤을때는 매우 쉽게 느껴질수도있습니다 예제에 나온대로 10을 11번 곱해서 나온값을 12로 나눈 나머지를 출력하라고 나와있듯이 10의11승 나누기 12를 해서 나온 나머지를 출력하면됩니다 단순히 구현을 한다면 B만큼 반복문을 돌리면서 A를 계속 곱해주고 마지막에 C로 나눈 나머지를 출력하면 되는문제입니다 하지만 이렇게 문제풀면 시간초과 도 발생을하고 오버플로우도 같이 발생합니다 우선 시간초과 같은경우는 현재 입력되는 값에 가장 최대값은 약 21억입니다 하지만 시간 제한은 0.5초 이기 때문에 21억번의 반복문은 시간초과를 발생시킵니다 이러한 문제를 해결하기위..
백준 3986 좋은단어 (C++)
* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다 백준 3986 좋은단어 입니다 문제 해석 이문제를 처음보았는데 저는 감이 정말로 안잡혔습니다 단어가 주어지면 그 단어에 단어 위로 아치형 곡선을 그어 같은 글자끼리 쌍을 지을수있다면 좋은단어 이고, 이 좋은단어의 개수를 세는 문제 인데 ABAB 와 같이 들어올때 어떻게 처리를 해야될지 감이 안잡혔습니다 우선 예제중 AABB 를 보면 AA가 붙어 있고 BB가 붙어있습니다. 그래서 A는 A끼리, B는 B끼리 쌍을 짓을수있고, 곡선을 그어도 선이 교차하지 않습니다 AABB만 보게 되면 뭔가 감이 안잡힐수도있습니다, 이럴때 큰돌님이 주어진 문자열을 뒤집어 보고(BBAA), 한개 더 붙여보고(AABBAABB), 그리고 90도로 회전..
백준 1940 주몽 (C++)
* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다 백준 1940 주몽 입니다 문제 해석 주몽 문제풀이 입니다 이 문제 같은경우는 우선 시간제한이 2초라서 조금 여유가 있습니다, 문제를 해석해보면 값옷을 만드는 재료들은 각각의 고유 번호를 가지고 있고, 두 재료의 고유 번호를 합해서 M이 되면 갑옷이 만들어 직 ㅔ됩니다 이때 N개의 재료와 M이 주어졌을때 값옷이 몇개가 만들어지는지를 구하면됩니다 예제를 보게되면 우선 재료의 개수 N은 6이 들어왔고, 갑옷을 만드는데 필요한수(고유한번호를 합친수) M은 9가 들어왔습니다 그리고 그다음줄에 N개의 재료들인 2 7 4 1 5 3 이 들어와있습니다 문제에서 두 재료의 고유번호를 합하라고 했으니 주어진 2 7 4 1 5 3 을 2개씩..
백준 1213 팰린드롬 만들기(C++)
* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다 백준 1213 팰린드롬 만들기 입니다 문제 해석 이문제 같은경우는 AABB 가 입력이 되었을때 ABBA 로 팰린드롬 문자를 만들고 만약 ABCD같이 팰린드롬이 만들어 지지 않는다면 I'm Sorry Hansoo 를 출력하면 되는 문제입니다 우선 이문제를 풀기위해서는 입력된 문자열에서 각 알파벳(A,B 등등)이 몇개가 쓰였는지 체크를 해봐야됩니다 즉 아래와 같이 카운팅 배열을 이용해야합니다 AABB -> A 2개, B 2개 그리고 핵심은 사전순으로 앞서는것부터 출력을 해야되니 알파벳 Z 부터 출력이 됩니다 그러면 AABB가 들어왔을때 A는2개이고,B도 2개이니깐 먼저 B부터 배열을 합니다 -> BB 그리고 다음 A2개가 남아..
백준 9375 패션왕 신해빈(C++)
* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다 백준 9375 패션왕 신해빈 입니다 문제 해석 패션왕 신해빈 문제해석 입니다 우선 이문제같은경우는 경우의수를 찾는 문제입니다 즉 각 의상 종류에따른 어떤 의상을 조합해서 입을수있는지에 대한 경우의수를 파악하는 문제입니다 첫번째 예제같은경우는 다음과 같이 입력이 들어와있습니다 [hat,headger],[sunglassess,eyewear],[turban,headgear] 이렇게 입력이 들어와있을때 같은 종류의 의상은 하나만 입을수있다는 조건과, 아예 안입는 조건은 없다고 했으니 아래와 같이 5가지의 경우의 수가 만들어지게됩니다 (hat),(turban),(sunglassess),(hat,sunglasses),(turban,s..
백준 1620 나는야 포멧몬 마스터 이다솜(C++)
* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다 백준 1620 나는야 포켓몬 마스터 이다솜 입니다 문제 해석 우선 실제 문제를 보면 많이 깁니다.. 서론이 조금 길어서 문제 자체가 많이 길어지긴했는데 핵심은 마지막 오박사님의 말을 해석하면됩니다 진정한 포켓몬 마스터가 되기 위해서 도감을 완성시켜야되는데 현재 가지고있는 포켓몬 독마에서 포켓몬 이름을 보면 포켓몬 번호를, 포켓몬 번호를 보면 포켓몬 이름을 말하는 연습을 한다고 나와있습니다 즉 포켓몬이름 - 포켓몬 번호로 이루어진 자료구조와, 포켓몬 번호 - 포켓몬 이름으로 이루어져 있는 자료구조를 사용을 해야됩니다 일반적인 배열을 생각인 났다면 배열에 인덱스는 정수값밖에 입력이 되지 않아 포켓이름-포켓몬 번호로 이루어진 자..
백준 2559 수열(C++)
* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다 백준 2559 수열입니다 문제 해석 해당 문제는 문제 지문이 어렵지는 않았는데 해당 문제를 풀기 위한 개념(누적합)을 이해하는게 조금 어려웠습니다 우선 문제에서는 아래와 같이 n일 간에 온도가 주어졌을때 연속적인 k간의 온도의 합중 가장 큰값을 구하는 문제입니다 3 -2 -4 -9 0 3 7 13 8 -3 해당 문제를 풀기전에 누적합의 개념부터 알아보도록하겠습니다 누적합 부분합, 누적합이라고도 하며, 배열의 일부 구간에 대한 합을 빠르게 구할수 있는 방법입니다 예를 들어오면 [5,6,2,6,4] 와 같은 배열이 있을때 이 배열의 누적합을구하게 되면 아래와 같이 나오게 됩니다 5 11 13 19 23 즉 5 + 6한 결과에 ..
백준 1159 농구 경기(C++)
* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다 백준 1159 농구 경기 입니다 문제 해석 농구 경기 문제를 해석해보겠습니다 문제의 지문이 조금 길수도 있지만 핵심만 파악을 해보겠습니다 우선 상근이는 국가대표팀의 감독이 된 이후에 매우 게을러졌습니다, 게을려졌기때문에 선수의 이름도 모르고, 능력도 모르기때문에, 어떤 농구 선수가 선발되어있는 기억하기 쉽게 성의 첫글자가 같은 선수 5명을 선발하고, 성의 첫글자가 같은 선수가 5명보다 적다면 경기를 기권할려고 하고있습니다 입력을 보게 되면 우선 선수의 수(N)이 주어지고 다음줄부터 N만큼 선수의 성이 문자열로 주어집니다 여기서 입력된 문자열에 가장 앞글자에 있는 알파벳을 가져와서 카운팅을 하면됩니다 즉 a가 몇개, b가 몇..
백준 2309 일곱난쟁이 (C++)
* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다 백준 스페셜 저지 일곱난쟁이 풀이입니다 문제 해석 문제를 간단히 해석해보겠습니다 일과를 마치곤온 백설공주 앞에 난쟁이가 아홉명이 있었습니다, 이 아홉명의 난쟁이는 모두 자신이 일곱난쟁이라고 주장을했지만, 다행이도 백설공주는 일곱난쟁이의 키의 합이 100인것을 알고있었습니다 따라서 아홉 일곱난쟁이의 키가 주어졌을때 위에 조건에따른 일곱난쟁이를 구하는 문제입니다 여기서 중요한 부분은 아홉명의 일곤난쟁이중 7명을 뽑아 키의 합이 100인지를 확인하는것이 이문제의 핵심입니다 즉 순열 혹은 조합을 활용하여 풀수가있습니다 해당 글에서는 순열로 풀이하였습니다 문제 풀이 순서 1. 우선 9개의 정수를 배열로 입력받습니다 2. 순열로 풀것..