조용하지않는개발Blog

https://www.acmicpc.net/problem/1263 1263번: 시간 관리 진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다. 진영 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제를 보면 알 수 있는 부분으로 모든 일을 처리해야며 최대한 늦게 일을 시작하게 만들면 되는 문제이다. 최소 쪽을 정렬하던 최대쪽을 정렬하면 될것같은 문제인데 나는 S를 최대로 하여 정렬하였다. S의 시안에는 일을 처리해야하기 때문에 이것을 기준으로 잡았다. S의 시에서 T시간을 뺀 값(result)을 다음에 할일을 할 수 있는 시간이 되는 것이다. 다음으..

https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 보았을때 알수있는 힌트 k개수 만큼 뺐을때 가장 큰수를 만드는 문제이다. 순조부를 이용하여 모든 경우의 수를 이용할수도 있겠지만 제한 조건에 1000000자리 수가 있다고하니.. 순열, 조합을 이용하면 시간 초과가 날것이다. 그렇기에 다른 방식으로 문제를 풀어야한다. 간단하게 스택 구간을 만들고 그 안에 큰 값을 계속 담게 하고 그보다 큰 값이 나오면 변경해주는 식으로 문제를 풀어주면..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제를 보고 조합 형식으로 풀어야하나 했지만 큰값만 잘 찾아놓으면 풀수 있는 그리디 문제였다. 자리수가 큰를 찾아서 리스트로 정리해놓는다. 예를 들어 GCF + ACDEB 라고 하면 ACDEB GCF 여기서 두 값을 더하려 위치에 맞게 값을 넣으면 A = 10000 C = 01010 D = 00100 G = 00100 E = 00010 B = 0000..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제에서 이야기하는 조건과 bfs만 알고 있으면 풀 수 있는 문제이다. 다만 시간을 줄이기 위해서는 여러가지 공부가 필요할듯하다. 문제 내용을 잘 보면 옆의 나라의 인구 차이가 L과 R 사이에 있다면 같이 공유한다고 한다. 이를 생각하여 연결된 모든 국경 인원을 저장하고 나라 수 만큼의 평균을 만들고 기존의 그래프에 저장 시키면 된다. 이를 ..

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제 자체는 어렵지 않은 문제였다. 하지만 어떻게 풀면 시간초과도 날수있으니 조금 생각하며 풀어봐야하는 문제였다. 먼저 왼쪽끝에서 오른쪽 끝으로 움직이면서 큰 값만을 이동 시키면 되는 문제이다. 이를 담을 DP를 만들어 주면 된다. 나는 이를 추가한다는 느낌이 들어 stack이라고 정의하고 넣으면서 진행했다. 결과적으로 오른쪽 아래에 도착하게..

일주일이나 늦어버린 회고록을 쓰게 되었습니다. 매달 최소 3~4번의 시험이 존재하다보니 여러가지로 바쁘게 지내고있다. # 삼성 교육 거의 한달동안 알고리즘 수업을 듣게 되었다. 아는 내용도 많이 있었지만 머리속을 정리한다는 느낌으로 다시 공부하니 많이 도움이 되었다. 강의 시간 이외에도 풀어야하는 문제를 계속 주니 거의 하루에 3~4문제씩 풀게 되었다. 중간에 코로나에 걸렸는데도 일주일을 제외하고 3주 정도 기간동안 50문제는 푼 것 같다... 8월 말에 모의 삼성 역량 테스트를 보기에 열심히 준비했다. # 모의 삼성 역량 테스트 A형 싸피에서 모의 삼성 역량 테스트를 월말 평가로 보게 하였다. 이것을 위해 알고리즘을 준비했다고 생각해도 좋을것같다. 문제는 구현 위주로 되어있다고 판단하고 백준에서 삼성 ..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 총 4가지를 생각하여 구현하면 조금이나마 쉽게 풀리는 문제 1. 궁수가 총 3명이기에 조합을 통해 3명의 자리를 만들어 준다. 2. 적들은 한턴에 한칸씩 내려온다. 3. 적을 공격할때 왼쪽이 먼저 공격하게 만든다. 4. 이를 모두 수행하고 끝나면 적을 제거한 최대 수를 나오게 구현한다. import java.io.BufferedReader; import java.io..

https://www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 이전에 풀었단 2048(Easy) 문제에 5개의 경우를 10번 이동 했을때로 좀 더 반복하는 수가 늘어난 문제이다. 당연히 그대로 푼다면 간단하게 구현하였기에 시간초과가 날 것이다. 잘 짰다면 이부분도 잘 통과했겠지만 ㅠㅠ 그래서 시간을 줄이기위해 깊은 복사하는 부분을 최대한 줄였다. 이전에는 왼쪽, 오른쪽, 위, 아래 방향을 ..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 2048을 구현하는 문제로 왼쪽, 오른쪽, 아래, 위로 움직이는 함수를 우선 만들었다. 그리고 그래프의 결과가 얕은 복사여서 다른 방향으로 움직일때 문제가 생길 수 있어서 깊은 복사 하는 메서드를 만들었다. 이렇게 구현한 방향을 총 5번 반복할수있는 dfs를 만들면 끝이나는 문제였다. 여기서 방향에 맞춰 움직이는 것이 어려웠지 ..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 왼쪽에서 오른쪽으로 가는 선을 겹치지 않고 오른쪽 방향으로 위, 가운데 아래로 움직이며 끝까지 가게 하였을때 최대로 갈수있는 개수를 찾는 문제이다. 처음 봤을때 dfs로 풀면 되겠다. 끝까지 가는 것을 확인하고 백트래킹을 하면 되겠다 생각을 했다. 하지만 그렇게 구현을 하면 너무 많은 반복을 하게 된다. R이 10000이고 C는 500이나 되기에 무조건 시간 초과가 난다...