백준72 [백준][C++] 11286번: 절대값 힙 <224> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 문제 자체는 엄청 쉽다. 그냥 Queue 2개 만들어서 각각 minus, plus 용으로 사용하면 된다. 다만 주의할점이... 아무 생각없이 그냥 queue를 사용하면서 삽질하면 안된다. 우선순위큐를 사용해서 minHeap을 만들어줘야 한다. priority_qu.. Algorithm/백준 2022. 5. 30. [백준][C++] 5430번: AC <223> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 각 케이스마다 별도로 bool값을 담아두는 isReverse 와 isError 변수를 만드는 것이 핵심이다. 1) isReverse 의 사용처 이 문제를 읽자마자 든 생각은, "이걸 직접 진짜 배열을 뒤집으면 시간안에 못풀겠는데?" 였다. 당연히 직접 뒤집을 필요도 없는 문제이다. isReverse 에 true가 담겨있으면 -> 뒤집.. Algorithm/백준 2022. 5. 26. [백준][C++] 16928번: 뱀과 사다리 게임 <222> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x HTML 삽입 미리보기할 수 없는 소스 음 일단 횟수의 최소값을 구해야 하니, BFS 방식을 가장 먼저 떠올렸다. input을 nextNumber[101]이라는 배열로 받아야 겠다 생각했다. nextNumber[31] = 42 는 31번 칸에 도착시 42번 칸으로 사다리를 타고.. Algorithm/백준 2022. 5. 23. [백준][C++] 16946번: 벽 부수고 이동하기 4 <221> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제를 1이 나올때마 전체 이동 가능한 칸을 직접 확이하면 시간안에 해결할수가 없다. 총 방문 가능한 칸이 1000*1000 칸이 있는데, 각 칸마다 확인하려면 1000*1000(모든 칸)*1000*1000(이동 가능한 최대 칸) 만큼 돌아야 한다. 시간안에.. Algorithm/백준 2022. 5. 19. [백준][C++] 15684번: 사다리 조작 <219> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 사다리 좌표계를 다음과 같이 생각하였다. ladder[i][j] == true 는 i행 j열에 가로 사다리가 배치되어있다는 의미이다. 우선 isValid라는 메서드를 다음과 같이 만들었다. bool isValid(){ for(int col = 1; col Algorithm/백준 2022. 5. 12. [백준][C++] 10026번: 적록색약 <217> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 사실 BFS를 2번 돌면되는 간단한 문제이다... 1) 일단 이반적인 BFS를 1번 돈다 2) R을 G로 변경한 후 (R과 G를 동일시 하기 위해) 3) 다시 BFS를 1번 돈다 (적녹생맥 전용) 나의 코드 " data-ke-type="html"> HTML 삽입 미리보기할 수 .. Algorithm/백준 2022. 5. 2. [백준][C++] 7579번: 앱 <216> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 유명한 KnapSack 문제이다. 해당 알고리즘에 대한 설명을 다음과 같이 정리해 두었다. HTML 삽입 미리보기할 수 없는 소스 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 터질 것" data-og-host="blo.. Algorithm/백준 2022. 4. 28. [백준][C++] 12100번: 2048 (Easy) <215> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 원래 맨 처음 생각한 풀이는 DFS를 진행하면서 우선 방향에 대한 중복순열을 구한 후, 구해논 중복 순열대로 돌려가면서 닶을 구하려 했다. 문제는 4방위에 맞도록 비슷한 함수를 4번이나 작성해야 한다는 점 이였다.... 이러한 문제를 해결하기 위해 2차원 .. Algorithm/백준 2022. 4. 27. [백준][C++] 1202번: 보석 도둑 <214> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 그리디(Greedy) 알고리즘에 우선순위 큐(Priority Queue) 를 사용하는 문제입니다. 1) 우선 입력으로 받은 가방의 무게와 보석의 허용 최대 무게를 기준으로 오름차순으로 정렬해줍니다. 2) 이후 가방의 수만큼.. Algorithm/백준 2022. 4. 25. [백준][C++] 12015번: 가장 긴 증가하는 부분 수열 2 <213> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 기존의 LIS 를 구하는 DP 방식만으로는 시간안에 해결할수가 없었다. 나또한 처음에 어떻게 해야 시간을 줄일 수 있을지 생각하지 못해 다른 블로그의 글을 참고하였다. 기존의 LIS 풀이와 거의 유사하지만, 저장할때 방식이 조금 달라진다! vec[i]는 길이가 i인 배열에.. Algorithm/백준 2022. 4. 24. [백준][C++] 10942번: 팰린드롬? <212> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 생각보다 간단한 DP 문제이다. 1) 길이가 1인 경우 모두 팰린드롬 수가 된다. 2) 길이가 2인 경우 바로 다음 칸의 수와 비교해서 같은지 확인하면 된다. 3) 길이가 3 이상인 경우 우리의 배열 input이 다음과 같다 해보자. 1 2 1 3 1 2 1 이중 가장 중간에 있는 P : [1, 2, 1] 은 팰린드롬 수 .. Algorithm/백준 2022. 4. 7. [백준][C++] 1005번: ACM Craft <211> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 위상정렬을 이용한 문제이다. 이 문제를 풀어본 후 다음 문제도 풀어보기를 권장한다. [백준][C++] 1766번: 문제집 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,.. Algorithm/백준 2022. 4. 6. 이전 1 2 3 4 5 6 다음
