본문 바로가기

전체 글137

[백준] 17298번 오큰수 (Python) https://www.acmicpc.net/problem/17298 쉽다고 생각하였으나 생각보다 어려웠던 문제. 스택 문제라고 생각하고 풀어서 그나마 구상을 조금 할 수 있었지만, 스택문제임을 몰랐다면 더더욱 어려웠을 것 같다. [문제] 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1).. 2023. 1. 6.
[백준] 9935번 문자열 폭발 (Python) https://www.acmicpc.net/problem/9935 조금 난이도 있는 스택 문제였다. pop과 append를 필요할 때에 맞춰 사용하는 능력을 필요로한다. [문제] 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가.. 2023. 1. 6.
[백준] 13305번 주유소 (Python) https://www.acmicpc.net/problem/13305 이전에 풀었던 회의실 배정 문제와 조금 비슷해서 금방 풀었다. [문제] 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의.. 2023. 1. 5.
[백준] 1541번 잃어버린 괄호 (Python) https://www.acmicpc.net/problem/1541 어렵지 않은 전형적인 그리디 알고리즘 문제였다. [문제] 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. [입력] 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나.. 2023. 1. 5.
[백준] 11399번 ATM (Python) https://www.acmicpc.net/problem/11399 조금만 생각하면 되는 그리디 알고리즘 문제였다. [문제] 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1= 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = .. 2023. 1. 4.
[백준] 1931번 회의실 배정 (Python) https://www.acmicpc.net/problem/1931 이번 문제는 그리디로 구상하는 것을 실패해서 재귀함수로 완전탐색을 하려했으나 시간 초과가 나서 실패하였다. 반나절 정도 고민 후 포기하고 그리디로 푼 다른 분의 코드를 보고 참고하였다. 알고보니 구상이 어렵지 구현은 매우 쉬운 코드였다. [문제] 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 .. 2023. 1. 4.
[백준] 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.

티스토리툴바