본문 바로가기

분류 전체보기282

2116. 주사위 쌓기 (Python, Swift) 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 풀이 주사위를 접어보면 (A-F), (B-D), (C-E)와 같이 짝을 이루어 위와 아래가 된다. 즉, 입력으로 주어진 배열에서 인덱스로 봤을때 (0번-5번), (1번-3번), (2번-4번)과 같이 되는 것을 알 수 있다. 1번 주사위에서 임의의 아랫면의 숫자를 정한다. 그렇게 되면 윗면의 숫자 역시 알 수 있다. 윗면과 아랫면의 숫자를 제외한 나머지 4개의 면 중에서 가장 큰 숫자를 찾아서 더해준다. 1번의 위와 아래를 임시로 정하고 나면 나머지 주사위의 윗면과 아.. 2022. 4. 21.
[자료구조] Swift로 구현하는 Linked List (연결 리스트) Linked List (연결 리스트)란? 링크드 리스트는 위의 그림과 같이 데이터를 순차적으로 저장하지 않고 각각 떨어진 공간에 존재하는 데이터를 연결해 놓은 자료구조를 말한다. 위의 그림의 사각형을 노드(Node)라고 하는데 노드는 자신의 데이터와 다음 노드를 연결하는 포인터로 구성되어 있다. Array와 Linked List 배열과 링크드 리스트는 서로 장단점이 명확하다. 먼저 배열을 살펴보자. 배열은 index를 사용하여 한 메모리 공간 안에 데이터를 순차적으로 저장한다. 사용자는 인덱스를 이용해서 원하는 위치에 있는 데이터를 바로 접근할 수 있다. 하지만 배열의 중간에 데이터를 삽입하거나 삭제할 경우 기존의 데이터를 이동시키는 작업이 필요하다. 그렇기 때문에 삽입과 삭제에 있어서 오버헤드가 발생할.. 2022. 4. 20.
5014. 스타트링크 (Python, Swift) 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 현재 위치에서 bfs를 통해서 목표 층인 G층에 최소 몇 번의 버튼 동작으로 이동할 수 있는지를 구할 수 있다. bfs를 수행할 때 방문 체크가 필요한데 이 문제에서는 건물의 전체 층에 대하여 현재 위치인 n층에 도착하기 위해 총 버튼을 몇 번 눌렀는지를 기록해둔다. 예를 들어, 현재 n층에 5번 버튼을 눌러 도착했는데 이전에 n층에 4번 버튼을 눌러서 도착했던 경우가 있다면 현재 이동 기록은 큐에 넣지 않는다. 하지만 현재 n층에 3번 버튼을 눌러 도착했다면 더 적은.. 2022. 4. 20.
1016. 제곱 ㄴㄴ 수 (Python) 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 풀이 에라토스테네스의 체를 활용하여 문제를 해결할 수 있다. 일단 입력으로 주어진 두 수 사이에 있는 수의 개수만큼 크기를 가진 배열을 만든다. 예를 들어 51과 100이 입력으로 주어졌다면 총 50개의 숫자가 있기 때문에 50의 크기를 가지는 배열을 만들어준다. 이때 51 ~ 100에 해당하는 임의의 숫자 n은 해당 배열의 n - 51번째 인덱스에 해당한다. 즉, 임의의 숫자 n에서 입력으로 주어진 min값을 빼주면 해당 배열에 접근할 수 있다.. 2022. 4. 19.
1826. 연료 채우기 (Python) 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 풀이 현재 연료의 양으로 갈 수 있는 거리를 간 후 방문할 수 있었던 주유소 중 가장 연료를 많이 채울 수 있는 주유소에 들렀다고 가정하고 해당 연료를 트럭에 추가해준다. 추가해준 연료의 양만큼 이동하고 방문할 수 있게 된 주유소를 추가로 탐색한다. 그 후 가장 연료를 많이 채울 수 있는 주유소에 들렀다고 가정하고 해당 연료를 트럭에 추가하는 과정을 반복하면 된다. 문제에 나와있는 예제는 다음과 같다. 처음 트럭이 갖고 있는.. 2022. 4. 18.
[자료구조] Swift로 구현하는 Stack Stack이란? 스택은 리스트의 끝(즉, 스택의 맨 위)에서 자료의 삽입과 삭제가 이루어지는 자료구조이다. 가장 최근에 들어온 자료가 가장 먼저 나가게 되는 LIFO(Last In First Out) 형태를 띄고있다. 스택의 입출력은 맨 위(top)에서만 일어나기 때문에 스택의 중간에 데이터를 삽입하거나 삭제하는 것은 불가능하며 top을 중심으로 연산이 이루어진다. 스택에서 사용되는 연산은 다음과 같다. count : 스택에 들어있는 요소들의 개수 isEmpty : 스택이 비어있는 지를 체크 push : 스택에 새로운 요소를 삽입 pop : 스택의 top에 있는 요소를 삭제 top : 스택의 top에 있는 요소 조회 Stack의 기본 구조 struct Stack { // 스택의 요소들을 담아두는 배열 v.. 2022. 4. 17.

티스토리툴바