발자취

https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 플로이드-와샬 알고리즘을 사용하여 풀이가 가능하다. 플로이드-와샬 임의의 양의 가중치가 있는 graph의 노드 s에서 e까지 가는 길에 m이라는 경유지가 있다고 할 때, 해당 경로의 최단거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 노드 s에서 e까지 가는 길의 최소값만 구하는 알고리즘이다. 다익스트라는 모든 경로를 하나씩 확인하면서 최소값에 대해서 계속 탐색하는 알고리즘이라면, 플로이드-와샬..

https://leetcode.com/problems/domino-and-tromino-tiling/ Domino and Tromino Tiling - LeetCode Domino and Tromino Tiling - You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes. [https://assets.leetcode.com/uploads/2021/07/15/lc-domino.jpg] Given an integer n, return the number of ways to tile an 2 x n bo leetcode.com 무슨 문제인지 보아하니, DP를 사용하는 문제 같다. 백준의 ..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제를 읽어보고 오자. 명령어에 따라서 숫자를 제거하거나 방향을 뒤집는 문제이다. 함수의 길이는 최대 10만개이므로, 실제로 위치를 바꾸게 되면은 속도가 매우 느려지게 된다. 또한, 주어진 데이터를 적절히 파싱해야 한다. 앞뒤 모두 pop 연산을 수행할 수 있는 deque 자료형을 사용하는 것이 좋다. 덱 자료형은 삽입 연산, pop 연산 등에서 준수한 속도를 보여주기 때문이다. 명령어와 조건에 맞게 현재 상태가 역방향인지 순방향인지 판별한다. 또한 파..

https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net 문제를 읽어보고 오자. 커서를 옮기면서 문자열을 삽입 혹은 제거하는 문제이다. 이 문제는 길이가 최대 100만인 만큼, 동작함에 있어서 최소한의 계산만 있어야 한다. 나의 경우에는 중간에 삽입하는 과정 때문에 list 자료형을 사용하기로 했다. 리스트 구조는 내부적으로 링크드 리스트 구조를 가지고 있어서 중간에 삽입하는 구조에 대하여 상당히 유리하다. iterator만 잘 다루면 간단히 풀..

문제를 읽어보고 오자. https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 배열에 값을 넣고, 가장 작은 값 부터 pop연산을 하면 된다. 하지만 문제 조건을 보면 최대 10만개의 값이 들어올 수 있으며, 일반적인 배열로 계산하게 되면은 시간 초과가 나게 될 확률이 높다. 여기서 사용해야 할 자료형은 힙 구조 또는 이진 트리 구조를 사용하는 자료구조를 사용하는 것이다. C++에서는 이러한 구조를 priority_queue 로 구..

문제를 읽어보고 오자. https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 이 문제는 스택으로 풀이하는 것과 양방향 링크드 리스트 기반 자료구조로 풀이할수 있다. 나는 스택으로 풀이하는 법은 잘 몰랐기에, 후자로 풀이했다. 문제 설명은 어렵지 않다. 하지만 저 위에 있는 시간 제한의 눈에 잘 보인다. 0.3초면은 비교적 촉박한 시간이다. 그리고 입력받을 명령어의 개수도 최대 50만개로, 많은 편에 속한다. 조건 생각 이러한 제한된 조건에 근거해서 링..

문제를 잘 읽어보고 오자. https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이 문제는 단순한 그래프 탐색 문제이다. 탐색 방법은 상관없으나, bfs로 풀이하면 가독성이 조금 더 좋은 코드가 되어서 bfs로 풀이했다. 문제 풀이는 탐색한 지점에 대해서는 체크 표시를 해 두고, 모든 좌표에 대해서 탐색을 시작해도 되는 점인지 판별하여 탐색하면 된다. 여기서 다른 문제와의 차이점은 여러 개의 테스트 케이스가 있다는 점과, 4개 방향이 아닌 8개..

문제를 읽어보고 오자. https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제를 읽어 보면 그래프 탐색을 사용하는 문제인 것을 알 수 있다. 하지만 약간 까다로운 점은, 특정 조건의 이동을 특정한 횟수 안에 실행한다는 점이다. 이것에 대한 모든 경우를 세야 할까? 나는 처음에 말처럼 움직인 횟수를 큐에 저장해서 확인해 보았다. 하지만 이러한 방법을 사용하니 방문한 경우에 대해서 오류가 있다는 것을 알게 되었다. 벽 부수기 문제 (..

문제 설명을 잘 읽어보자. https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 빗물이 고이는 특성은 다음과 같다. 1. 좌측 끝과 우측 끝이 벽으로 막혀 있어야 한다. 2. 빗물이 찼을 때 양쪽 끝이 같다. 3. 중간에 구멍이 생길 일은 전혀 없다. (주어진 조건이 밑에서부터 위로 몇 칸 있는지 확인하므로) 이러한 특징을 기반으로 다음과 같은 풀이 알고리즘을 생각해 보았다. 1. 수면의 높이가 1~N 일때까지 탐색한다. 2. 물이..

문제 설명을 보고 오자. https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 이 문제는 백트래킹을 이용한 탐색 문제이다. 조건을 생각하는 구성이 복잡하지만, 역할을 잘 나누면 풀이가 한결 편해질 것이다. 인접한 두 개의 부분 수열이 동일한 것이 있으면, 해당 수열은 나쁜 수열로 다음 경우의 수로 넘어가야 한다. 그렇게 하기 위해서는 한 자리에 1~3이 들어가며, 조건에 맞으면 다음 과정을 탐색할 수 있는 백트래킹 기법으로 풀이하면 될 것이다. 탐색하는 함수를 ..