솧로그

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 지난 번에 푼 퇴사 문제와 동일한데 N의 범위만 커졌다. 따라서 퇴사 문제의 답을 제출하면 시간 초과가 나고, O(N)의 시간 복잡도로 해결해야 한다. 코드를 보면 금방 이해할 수 있다. 주요 포인트는 다음과 같다. max는 i 날짜까지의 최대 수입을 의미한다. i 날짜에 일을 시작하면 일이 끝난 다음날인 nextDay에 돈을 받는다고 가정한다. dp[nextDay]..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net dp 문제이고 내가 실수한 코드는 다음과 같다. for (int i = 1; i = 0; j--) { if (input[j] < input[i]) { dp[i] = dp[j] + input[i]; break; } } } 그런데 만약 input 값이 "20 60 50 70"인 ..

https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net bfs 문제로 크게 막힘없이 풀 수 있었다. 다만 주의할 점과 내가 놓친 부분은 다음과 같다. 상근이는 불이 붙으려는 칸으로 이동할 수 없다. 그리고 상근이가 있는 칸에 불이 옮겨옴과 동시에 상근이가 다른 칸으로 이동할 수 있다. 따라서 불이 먼저 이동하고, 상근이가 이동해야 한다. 불과 상근은 시간 당 한 칸씩 이동할 수 있다. 따라서 fireQue.size()만큼 각 불들이 한 칸씩 이동하도록 하고, pe..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 상하좌우로 총 5번 움직였을 때 그래프에 있는 가장 큰 수를 구하는 문제이다. 따라서 상하좌우로 5번 움직이는 조합을 찾기 위해 재귀를 사용해야 한다. 그리고 상하좌우로 움직이는 로직을 구현해야 한다. 기존 배열을 보고 새로운 배열을 만들어야 한다. 새로운 배열에 값을 채울 인덱스인 fillIdx와 기존 배열과 값을 비교할 인덱스인 checkIdx가 필요하다. 기존 배..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 일차원 그래프의 bfs 문제이다. 주의할 점은 다음과 같다. 최소 시간을 구해야 하기 때문에 dfs가 아닌 bfs로 풀어야 한다. 최소 시간을 각 그래프의 위치에 저장해준다. 한 칸 뒤로 이동, 한 칸 앞으로 이동, 두배 앞으로 이동으로 한 위치당 총 3번의 탐색을 하면 된다. 그래프를 벗어나거나 이미 방문한 위치인 경우에는 탐색하지 않는다. (최소 시간을 갱신X) 내가..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 해결법을 떠올리는 건 쉽다. 연산의 최소 값을 구해야 하므로 -가 붙는 수를 최대한 크게 만들면 된다. 예를 들어 다음과 같이 식이 있다고 가정하자. a + b - c + d + e -f 그러면 -의 값을 최대한 크게 만들기 위해 c, d, e를 한 묶음으로 묶어주면 된다. 문제는 값이 입력될 때 숫자와 연산자를 어떻게 구분하고 어떻게 저장할지 고민이었는데.. -를 기준으로 먼저 나눈 ..

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net bfs 문제인데 이 문제를 풀며 주의할 점이 몇가지 있다. 논리적으로 불과 지훈이 동시에 이동해야 한다. 따라서 코드 상으로 불과 지훈이 순차적으로 한 번씩 이동해야 하는데, 둘 중에 불을 먼저 이동시켜야 한다. 불이 먼저 이동해서 불이 번지면, 지훈이가 불이 있는 곳을 피해서 이동해야 하기 때문이다. 불을 한 번 이동시킬 때는 fireQue의 사이즈만큼 이동을 처리해주어야 한다...

스레드 프로세스는 메모리에 할당된 프로그램, 즉 실행 중인 프로그램으로 운영체제의 관리의 단위이다. 반면, 스레드는 프로세스 내부에서의 CPU 수행 단위를 의미한다. 그 전에 프로세스가 어떻게 관리되는지 정리해보자. 프로그램을 실행하게 되면 프로세스가 생성된다. 프로세스가 생성되면 각 프로세스의 주소 공간(code, data, stack)과 PCB(Process Control Block)가 생성된다. 만약 동일 프로그램을 여러 개 실행하는 경우 그만큼 프로세스가 생성된다. 즉 그만큼 메모리를 차지하고 동일 프로그램이기 때문에 각 프로세스들의 실행 코드는 같다. 따라서 굉장히 비효율적이다. 따라서 여기서 스레드가 등장한다. 동일 프로그램에 대한 프로세스가 여러 개 있을 경우 하나의 프로세스에 여러 개의 스..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net https://olsohee.tistory.com/44 이 문제와 마찬가지로 bfs로 탐색하면서 이전 값에 + 1을 해주어 토마토가 익는데 걸리는 일수를 구하면 된다. 주의할 점은 우선 처음에 그래프 값을 입력받을 때 익은 토마토의 위치를 큐에 넣어주어야 한다. 그리고 큐에서 토마토의 위치를 빼서 해당 위치의 사방면을 탐색하고, 아직 익지 않은 토마토인 경우 이전 값 + 1을 저장..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 최소 거리를 구하는 문제이기 때문에 bfs를 사용하면 된다. 관건은 이동한 칸수를 계산하는 것인데, visited 배열에 1, 2, 3, ... 과 같이 이동한 칸수를 기록해주면 된다. 즉 visited 배열의 값이 0이면 아직 방문하지 않은 위치인 것이고, 시작 위치와 같이 한 번만에 방문하면 1, 그 다음으로 방문하면 2를 기록해주면 된다. 그리고 visited 배열의 값이 0이 아닌 경우, 즉 이미 방문한 경우에는 제외하기..