본문 바로가기

Koi7

선형 구조의 탐색 선형 구조의 탐색 이번 글은 선형 구조란 무엇이고 선형 구조 속에서 탐색하는 대표적인 방법 2가지를 설명한다. 선형 구조란? 선형 구조란 프로그래밍 언어를 배울 때 배우는 배열, 연결 리스트 같은 말 그대로 선 같이 생긴 데이터 구조를 선형 구조라고 한다. 반대로 비선형 구조는 트리, 그래프 등이 있다. [배열] - 대표적인 선형 구조 [연결 리스트] - 얘도 선형 구조다. 선형 탐색 선형 탐색에는 대표적으로 전체 탐색과 이분 탐색(이진 탐색)이 있다. 전체 탐색은 말 그대로 전체를 순환해서 어떠한 값을 찾는 것을 말하고 이분 탐색은 정렬된 선형 구조에서 부분적으로만 탐색을 해서 값을 찾는 부분 탐색을 말한다. 구체적인 예시와 설명을 보면서 설명하면 좋을 것 같다. 전체 탐색 전체 탐색은 전체를 순환하기.. 2018. 5. 5.
[BOJ] 14867번: 물통 14867번: 물통다른 친구가 우선 순위 큐를 이용해서 풀었다고 하고, 인터넷에 풀이 올리신 걸 보니 BFS or DFS로 푸시는 걸 보고 감이 안 잡혔다. ㅠㅠ아무튼 나는 1. A에서만 물통을 채워서 B에게 넘겨주는 작업, 2. B에서만 물통을 채워서 A에게 넘겨주는 작업. 이 둘 중에서 최소 작업 횟수를 출력하게 만들었다. 사실 코드가 굉장히 미개하다. 왜냐하면 중복이 너무 많기 때문이다... 코드를 짤 때 생각해야 할 점이 -1을 출력할 때인데 bucketA == a && bucketB == b일 때가 못 만들 때이다. 왜냐하면 이 때는 어짜피 bucketA, bucketB를 비워줘야 하는데 이렇게 되면 처음 시작할 때와 똑같은 상황이기 때문이다.또한 a == c && b == d일때는 2를 출력해.. 2018. 4. 9.
정올 2013년 시도예선 중고등부 문제풀이 1! + 2! + 3! + ··· + 10!의 마지막 자리의 숫자는 어떻게도 볼 수 있냐면 1!, 2!,...,10!의 마지막 자리의 숫자의 합의 마지막 자리의 숫자로도 볼 수 있다. 그래서 Dn = n!의 마지막 자리의 숫자라고 놓으면 D1 = 1, D2 = 2, D3 = 6, D4 = 4, D5 = 0, D6 = 0, ..., D10 = 0이 된다. D5부터 0이 되는 이유는 D4가 4이기 때문에 5를 곱하면 0이 되고 그 뒤로도 계속 0이 되기 때문에 쭉 0이다.따라서 1 + 2 + 6 + 4 + 0 + 0 ... = 13이고, 답은 2번(3)이다. 1~9 = 4510~19 = 10 + 45 = 5520 ~ 29 = 20 + 45 = 6530 ~ 39 = 30 + 45 = 7585(40~49), 9.. 2018. 4. 8.
정올 2012년 시도예선 중고등부 문제풀이 24 = 7원 * 2 + 5원 * 2 26 = 7원 * 3 + 5원 * 1 31 = 7원 * 3 + 5원 * 2 33 = 7원 * 4 + 5원 * 1 1번 23원이 못 만들어진다. 총 경기 수 : 4 + 3 + 2 + 1 = 10 경기 하루 가능 경기 수: 2경기 10 / 2 = 5일 각 빈칸을 a,b,c,d,e라고 설정. b = 2c라서 b와 c가 되는 경우가 (2, 1), (4, 2)인데 b=2, c=1일 경우에는 만들어지지 않는다. (4, 2)일땐 a=3, b=4, c=2, d=5, e=1로 방정식이 일치하게 된다. *참고: 균형이 맞으려면 (왼쪽 무게)*(왼쪽 거리) = (오른쪽 무게)*(오른쪽 거리)여야 한다. 방정식으로 두고 풀면 되긴 한데 방정식을 세웠다고 해서 연산을 통해 풀리는 건 아니고.. 2018. 4. 7.
정올 2011년 시도예선 중고등부 문제풀이 정올 2011년 중고등부 예선 풀이어떤 밭을 일구는데, 세 사람 A, B, C가 혼자 밭을 일구면 각각 2시간, 3시간, 6시간이 걸린다. A, B, C 세 사람이 함께 이 밭을 일구면 몇 시간이 걸리는가? [풀이]: A가 시간 당 1/2, B는 1/3, C는 1/6 만큼 일한다. 따라서 A,B,C가 동시에 일하는 건 hour(A+B+C) = 1이므로 hour = 1 아버지와 아들의 나이 합은 85이다. 과거에 아버지가 아들의 나이였을 때, 아버지의 나이는 아들의 나이의 6배이었다. 아버지와 아들의 나이 차는 얼마인가? [풀이]: a: 아버지의 나이, b: 아들의 나이. a+b=85, a-x = 6(b-x) = b를 계산하면 a=55, b=20이므로 a-b=25이여서 답은 4번(25)가 된다. (13)1.. 2018. 4. 7.
정올 2008년 시도예선 중고등부 문제풀이 2008년도 풀이 수열 1, 3, 6, 11, 19, 31, 48, ( )이면 (+2, +3, +5, +8, +12, + 17) -> 이 수열의 계차 수열 (1, 2, 3, 4, 5) 따라서 다음 수는 +6이여야 하고 17 + 6 = 23, 48 + 23 = 71. 답은 71이된다. B, A를 곱했을 때 일의 자리에 B가 나오기 위해서는 A, B 중에 하나가 1이면 편하게 구할 수 있다. A는 1이고 B는 1을 제외한 나머지 수가 될 수 있는데 4번째 줄 B C가 되려면 B*B의 값이 10을 넘으면 안된다. 따라서 B는 2 또는 3이된다. A=1,B=2일 경우 252가 나오는데 E와 B가 같은 수가 될 수 없으므로 B=2일 때는 틀렸다. 따라서 A=1, B=3이다. 이 값을 계산하면 403이 나오고 D는.. 2018. 4. 6.
정올 2007년 시도예선 중고등부 문제풀이 2007 시도예선 중고등부 문제풀이 한 변에 11그루를 세울 수 있지만 4방향에 세울 경우, 4번의 중첩이 생기므로 44 - 4 = 40이므로 답은 3번이다. A*B의 일의 자리 수가 7이므로 경우의 수를 세보면 3 x 9가 이상적이다. 또한 AB x BA 이므로 A=3, B=9여도 되고 A=9, B=3이여도 된다. 따라서 3 + 9 = 12, 답은 4번이다. 삼각형의 세 번이 가장 많이 지나가는 경우를 찾으면 된다. 답은 5번 역으로 계산하면 된다. A ◎ 4를 A'로 놓고 A' ◎ 5 = 3을 계산하면 A'가 나올 수 있는 수가 15,16,17,18,19가 나온다. A ◎ 4 = 15,16,17,18,19이니깐 4*5=20 답은 5번이다. 20 x 4 + 30 + 10π(코너); 코너 계산법(2 x .. 2018. 4. 6.

티스토리툴바