본문 바로가기

전체 글131

[백준] 11047번 동전 0 (Python) https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 구상하고 코드 짜는 데 크게 난이도가 있는 문제는 아니었지만, 반복문의 조건을 잘못 입력해서 조금 헤맸다. [문제] 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시.. 2023. 1. 4.
알고리즘을 배우는 이유 및 커리큘럼 알고리즘을 배우는 이유라고 썼지만 사실 알고리즘을 "다시" 배우는 이유이다. 사실 2022년 여름방학 두 달 동안 친구들과 스터디를 만들어 스터디 장으로서 활동하였고, 그 스터디를 하면서 알고리즘을 공부한 적이 있다. 그 때 하루에 2~8시간정도씩 꾸준히 알고리즘 공부를 했었던 걸로 기억한다. 그 정도로 알고리즘을 열심히 하였다. 그래서 재귀는 기본이고 다이나믹 프로그래밍, 그래프도 충분히 익혔다. 그리고 학기가 시작하면서 42서울한다고 바빴고, 학교 공부 따라간다고 바빠서 알고리즘에는 아예 손을 놨었다. 그리고 이번에 UOSPC라는 교내 알고리즘 대회에 출전하였고, 1, 2학년 40여명 중 6등을 하게 되었다. 상금도 받고 기분은 좋았지만 조금 아쉬운 성적이었다. 그렇지만 근래에 알고리즘을 전혀 공부하.. 2023. 1. 3.
구현 - 게임 개발 난이도 : 하 [문제] 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다.. 2023. 1. 3.
구현 - 왕실의 나이트 난이도 : 하 [문제] 행복 왕국의 왕실 정원은 체스판과 같은 8 × 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 이처럼 8 × 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하라. 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 .. 2023. 1. 3.
구현 이론 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 어떤 문제든 소스코드로 바꿔야 하므로 구현 문제라고 할 수 있다. 하지만 구현 문제라고 하면, 일반적으로 소스코드로 바꾸는 과정이 어렵거나 구현에 초점이 맞춰져있는 문제를 말한다. 흔히 알고리즘 대회에서 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 말한다. 알고리즘은 간단한데 코드가 지나치게 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정 기준에 따라 끊어서 처리해야 하는 문제 적절한 라이브러리를 찾아 사용해야 하는 문제 미리 알고 있는 함수들이 많다면 쉽게 문제를 풀 수 있을 것이다. 시뮬레이션 유형, 구현 유형, 완전탐색 유형은 서로 유사한 점이 많다. 문제 예시로는.. 2023. 1. 3.
재귀함수 이론 재귀함수도 cs 전공 수업 및 개인 알고리즘 공부할 때 이미 많이 배웠던 내용이니 간단하게 작성하겠다. 재귀함수 : 자기 자신을 다시 호출하는 함수. 일종의 스택 자료구조 안에 함수에 대한 정보가 차례로 담긴다. -> 컴퓨터 메모리는 한정적이기 때문에 무한이 함수를 호출하게 되면 문제가 발생할 수 있다.(스택오버플로우가 일어나는 예시 중 하나이다.) 의도적으로 무한히 호출하는 것이 아니라면 재귀함수의 종료 조건을 반드시 명시해야 한다. 코드가 훨씬 간결해질 수 있다. 모든 재귀함수는 반복문으로 동일한 기능을 구현할 수 있고, 반대로 모든 반복문은 재귀함수로 구현할 수 있다. 가장 흔한 예시인 팩토리얼의 코드를 구현해보겠다. def factorial(n): # 재귀함수의 종료 조건이다. 이를 설정해주지 않.. 2023. 1. 3.
스택과 큐 자료구조 이론 스택과 큐 자료구조는 cs 전공 수업 및 알고리즘 개인 공부 하면서 배운 적이 있어 이미 알고 있는 내용이었다. 고로 여기에는 간단히 작성하겠다. 스택 : 선입후출 (Last In First Out - LIFO) 삽입과 삭제가 있다. 삽입 하면 자료구조의 맨 뒤에 삽입, 삭제하면 자료구조의 맨 뒤의 것을 삭제한다. 파이썬에서는 기본적으로 제공되는 list가 스택이다. 큐 : 선입선출 (First In First Out - FIFO) 입구와 출구가 모두 뚫려있는 터널과 같은 형태이다. 삽입과 삭제가 있다. 삽입하면 가장 왼쪽으로 들어오고, 삭제하면 가장 오른쪽 것을 삭제한다. 파이썬에서는 deque 라이브러리를 사용하여 큐를 사용할 수 있다. 2023. 1. 3.
그리디 알고리즘 - 1이 될 때까지 난이도 : 하 [문제] 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번 과정을 수행해야 하는 최소 횟수를 구하는 프로그램 작성하시오. [입력 조건] 첫째 줄에 N(2 2023. 1. 3.
그리디 알고리즘 - 숫자 카드 게임 난이도 : 하 [문제] 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 카드들이 N X M 형태로 놓여 있을 때, 게임의.. 2023. 1. 3.
그리디 알고리즘 - 큰 수의 법칙 난이도 : 하 [문제] 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 방법이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고 K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 .. 2023. 1. 1.
그리디 알고리즘 이론 그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것을 고르는 방법이다. (탐욕법이라고도 한다.) 합이 21인 5 - 7 - 9 루트가 아닌, 합이 19인 5 - 10 - 4 루트를 선택하게 된다. 즉, 최적의 해를 보장할 수 없는 경우도 있다. 하지만 코딩테스트에서 그리디 문제가 출제가 된다면, 그리디로 얻은 결과가 최적의 해인 경우가 많다. 따라서, 그리디로 풀면 최적의 해가 나오는지 판단하는 능력이 필요하다. 만약 화폐단위가 500, 400, 100이라면 그리디 알고리즘은 적용될 수 없다. 예를 들어, 800원은 그리디 알고리즘에 의해 500+100+100+100로 구성되지만, 실제 해는 400+400이다. 2023. 1. 1.

티스토리툴바