Algorithm115 [백준][C++] 5525번: IOIOI <225> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 'I' 가 나올때 마다 매번 Pn이 포함됬는지 확인하기는 시간안에 해결이 불가능하다. while문을 돌면서 'OI' 를 하나의 단위로 보고, 단위로 확인을 한다. while(str[i+1] == 'O' && str[.. Algorithm/백준 2022. 6. 2. [백준][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++] 3055번: 탈출 <220> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 기존의 BFS 알고리즘을 적용하는 문제들과는 조금 다른 점이 있는 문제이다. 이 문제는 두더지가 이동하는 동시에 물도 함께 차오르기 때문에 Queue를 2개 사용해야하는 문제였습니다. 물이 차오를 예정인 위치로는 두더지가 움직일 수 없기 때문에 1) 먼저 물이 차오르는 과정을 진행한 다음 2) .. Algorithm/백준 2022. 5. 13. [백준][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++] 17387번: 선분 교차 2 <218> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 vector의 외적에 대한 지식이 없다면 다음글을 먼저 읽어보길 권장한다. https://degurii.tistory.com/47 [알고리즘] CCW로 세 점의 방향성 판별하기 0. 들어가기 전에 첫 알고리즘 포스트입니다. 이번에 쓸 내용은 CCW입니다. 원래는 기하 알고리즘들을 전반적으로 다루려고 했는데 생각보다 글이 길어져서 CCW만 .. Algorithm/백준 2022. 5. 9. [백준][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. 이전 1 2 3 4 5 6 7 8 ··· 10 다음
