이름 못 정한 블로그

2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 본격적인 학기 시작 전에 여유가 조금 있어서 정말 오랜만에 PS를 했다. 저번 방학 + 학기 초까지는 꽤 열심히 했었는데, 학기가 바빠지고 이번 방학 때는 다른 활동을 하느라 한참 방치되어 있었다. 최근에 C++도 다루지 않았다 보니 평소보다 시간이 좀 더 걸렸던 것 같다. 이 문제는 분할 정복을 이용해서 푸는 문제였다. 문제에 주어진 24를 기준으로 설명하면, 큰 그림은 작은 그림 3개로 쪼갤 수 있다. 또 작은 그림은 더 작은 그림 3개로 쪼갤 수 있는 형태를 가졌다. 그래서 더 이상 쪼갤 수 없는 그림까지 쪼..

17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 역시나 삼성 기출문제였다. 삼성 문제는 일단 문제를 꼼꼼히 읽는 게 중요한 것 같다. 문제를 완벽히 이해하고 필요한 기능을 하나하나 구현하면 풀 수 있다. 이번 문제를 풀기 위해서 가장 고민했던 부분은 게임의 진행 상태를 어떤 자료구조에 담을까였다. 제일 처음엔 링크드 리스트로 할까했는데 Singly 하게 구현해서는 안 됐고 Doubly까지 구현해야 했다. STL의 리스트가 Doubly로 구현되어 있다고 알아서 그걸 사용할까 생각했다. 그런데 최대로 필요한 경..

19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 오랜만이라 반가운 BFS 문제였다. 문제는 복잡하거나 구현할 것이 많다거나 하지는 않았다. 택시가 동시에 여러 명을 태우고 다녔으면 그건 좀 골치 아팠을 것 같다. 하지만 이 문제는 택시에 한 번에 한 명밖에 태울 수 없기 때문에 그리디하게 풀면 되는 문제였다. 택시의 운행 알고리즘은 엄청 심플하다. 1 현재 택시 위치에서 가장 가까운 승객을 찾는다. 2 그 승객을 태우고 도착점까지 최단 거리로 운행한다. 이 과정에서 연료가..

15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 삼성 SW 기출문제를 열심히 풀고 있다. 이 문제는 사실 어제 풀었는데 오늘에서야 포스팅한다. 내가 접근한 방법은 실제로 선들을 90도씩 회전시키는 방법이었다. 이 과정에서 배열을 중심점을 기준으로 90도 돌리는 게 쉽지 않았다. 내가 평소에 배열의 좌표를 잡는 방식과 다르게 되어 있어서 진짜 헷갈렸다. 문제에 주어진대로 해보려다가 결국은 체념하고 내가 원래 하던 대로 바꿨더니 그나마 이해하기 편했다. 이제 와서 보면 별거 없었는데 그 ..

19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 보통 내용도 붙여 넣는데 이 문제 같은 경우엔 문제가 너무 길어서 따로 붙이지 않았다. 문제를 풀기 위해서 두 가지 자료구조가 필요하다고 생각했다. 그래서 상어들의 현재 상태를 저장하고 있는 구조체와 냄새의 현재 상태를 저장하는 구조체를 만들었다. 첫 번째 구조체는 다른 알고리즘 문제들과 비슷하게 현재 상어의 좌표와 방향, 생존 여부가 들어있다. 이 문제가 특이한 점은 각 상어마다 이동 방향의 우선순위가 다르다는 것이었..

15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 문제 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접..

Longest Substring Without Repeating Characters - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Given a string s, find the length of the longest substring without repeating characters. Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of ..

Add Two Numbers - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a li..

17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 문제 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구..

14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을..