재원블로그 재원블로그

이 문제는 bfs를 이용해서 풀었다. 일단 입력 배열의 크기가 4 * 4로 작아 완전 탐색과 같은 방법으로 풀 수 있음을 예상하고 문제를 풀었다.백트래킹으로도 문제를 풀 수 있는데, 최소를 구하기 위해 모든 경우를 무조건 탐색해야 한다는 점에서 시간 초과가 날 수도 있다고 생각했고, bfs로 풀기로 결정했다. 수레가 교차해서는 안되고, 같은 곳에 두 개가 동시에 있지 않게 하기 위해서 두 수레를 따로 움직이고, 이를 한번에 큐에 푸시하는 방식으로 구현했다.여기서 주의할 점은 블루가 먼저 움직이고, 레드가 나중에 움직이는 식으로 무조건 순서를 고정해놓으면 오답이 나올 수도 있다는 점이다. 따라서 블루가 먼저 움직일 때, 레드가 먼저 움직일 때 모두 큐에 넣어주는 방식을 사용했다.또한 Node의 visite..

이 문제는 그리디 알고리즘으로 풀었다. 이 문제에서 핵심은 카드를 버리지 않는 것이다. 즉, 버리는 대신 어딘가 저장해둔 뒤에 필요할 때 코인을 주고 쓰는 것이다.이걸 인지하면 문제가 매우 쉬워지고, 단순 구현 문제로 바뀌게 된다. 그리디 알고리즘이 적용되는 부분은 N + 1을 만들 때 적용되는데, 우선순위를 다음과 같이 해서 문제를 풀었다.1. 내가 가진 카드만으로 n + 1 만들 수 있을 때2. 버린 덱에서 한 장 + 내가 가진 카드 한 장으로 만들 수 있을 때3. 버린 덱에서 두 장 모두 가져와야 할 때 매 라운드마다 카드를 두 장 뽑을 수 있는데, 바로 discard set에 넣어서 구현을 단순화했다. 주의할 점은 루프가 다 돌아서 끝나는 경우에는 answer + 1을 해줘야 한다는 점이다.#in..

이 문제는 BFS를 이용해서 풀었다. 이 문제에서 관건은 한 번만 꺾이는 경로를 찾는 것, 모두 없앨 수 있을 때 알파벳 순으로 빠른 순으로 출력하는 것이다. 한 번만 꺾이는 경로에 대해서는 Node 구조체를 만들어 y, x 좌표와 함께 방향, 꺾인 카운트를 추가하여 BFS로 구현할 수 있었다. 알파벳 순으로 빠른 순으로 출력하는 부분에 있어서는 약간의 생각이 필요했다.그러나 만약 A와 C가 동시에 경로가 존재하고, 이를 순서를 바꾼다고해서 뒤의 결과에 영향을 주지 않는다는 것을 알게 되었다.어떤 알파벳이 사라짐으로써 경로가 생길 수도 있지만, 이는 순서와 상관없이 그 알파벳이 없어지기만 한다면 경로가 생기기 때문이다.따라서 알파벳 순서로 루프를 돌면서 가장 먼저 제거할 수 있는 부분이 생기면 즉시 제거..

ffmpeg을 사용해서 동영상의 상단에 제목을 붙이기 위해 drawtext를 사용하는 중에, 한글인 경우에 제대로 렌더링이 되지 않았다. 아예 깨지면 인코딩 문제라고 생각하겠는데, "안녕하세요" 라고 치면 안녕XX 이런식으로 나오는 문제가 있었다.linuxserver/ffmpeg:latest 이미지의 경우 ubuntu 기반으로 동작하는 것을 보고, 혹시 로케일 설정이 아닌가 생각해서 로케일을 ko_KR로 전부 바꾸고 빌드했지만 전혀 먹히지 않았다. 그러다가 utf-8에 대해서 보게 되었는데, utf-8에서 한글의 경우 한 글자 당 1바이트가 넘게 설정된다는 걸 보게 되었다. 여기서 힌트를 얻어 한글 한 글자당 2개의 공백을 주면 어떨까라는 생각이 들어 실행했고, 제대로 동작했다. 또한 공백을 주는 위치를..

이 문제는 맵과 다이나믹 프로그래밍을 이용해서 풀었다. 이 문제를 처음에 그리디로 접근하려다가 다이나믹 프로그래밍 문제임을 알게 되었다.왼손과 오른손 모두 똑같은 가중치로 특정 숫자에 갈 때가 문제였는데, 이 때 임의의 손을 선택하게 된다면 다음 숫자들에 대해 결과가 달라지기 때문에 그리디로는 풀 수 없다. 따라서 완전 탐색을 사용해야하는데, 왼손이 위치하는 숫자, 오른손이 위치하는 숫자, 현재 숫자(눌러야하는 숫자) 총 세 개의 파라미터를 통해 하나의 독립적인 상태를 만들 수 있었다. 따라서 다이나믹 프로그래밍으로 속도를 빠르게 만들 수 있어 문제를 해결할 수 있었다. 이 문제에서 가장 까다로웠던 것은 키패드의 위치와 숫자를 매칭하고, 최단 거리를 찾는 로직 두 개였다. 키패드의 위치와 숫자를 매칭하는..

ffmpeg을 이용한 영상 처리 서버를 만들고 프리 티어 EC2에 올려 테스트하는데, OutOfMemoryError가 발생했다.영상을 처리하려면 결국 원본 영상이 있어야하므로 당연히 메모리가 초과될 수 있을 것이라고 생각했다. https://repost.aws/knowledge-center/ec2-memory-swap-file그래서 위 포스트에서 나온 방법인 swapfile을 만들어 디스크를 메모리로 이용하여 성능과 용량을 트레이드 오프하는 방식으로 가용 메모리를 추가할 수 있었다. 기대를 품고 다시 컨테이너를 실행하는데, 또 OutOfMemoryError가 발생했다. 그러다 오류 메시지를 자세히 봤는데, java.lang.OutOfMemoryError: java heap space 라는 내용이 있었다...

이전 Dockerfile FROM openjdk:17-jdk-alpine as builderCOPY gradlew .COPY gradle gradleCOPY build.gradle .COPY settings.gradle .COPY src srcRUN chmod +x ./gradlewRUN ./gradlew bootJarFROM builder as ffmpegRUN apk updateRUN apk add --no-cache ffmpegFROM ffmpeg as executeCOPY build/libs/*.jar app.jarEXPOSE 8080ENTRYPOINT ["java", "-jar", "/app.jar"] 여기서 문제점은 COPY build/libs/*.jar app.jar 였다.as 문법을 통해서..

이 문제는 bfs와 유니온 파인드를 이용해서 풀었다. 이 문제를 요구사항 그대로 각 벽마다 bfs를 각각 수행하면 시간 초과가 나게 된다.따라서 반대로 빈칸을 bfs를 통해 덩어리의 개수를 미리 계산하고, 다음 루프에서 벽을 만나면 상하좌우로 더해주는 방식으로 사용했다. 여기서 문제는 같은 덩어리를 상하좌우 탐색에서 중복 계산할 수 있다는 점이다. 이를 없애기 위해 유니온 파인드로 한 덩어리를 그룹화하였고, 상하좌우를 탐색할 때 이미 탐색한 그룹이면 카운트하지 않게 구현했다.#include #include #include #include #include using namespace std;#define MAX 1000int N, M;int dy[] = { -1, 0, 1, 0 };int dx[] = { ..