QQ의 다이어리

문제https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이포인트는 자를 전력망을 방문처리 해두는 것!그것 외에는 일반 bfs와 같다bfs 문제를 오랜만에 풀어서 실수했던 것은 cnt를 증가시킬 때큐에서 팝 할 때 증가 시켜야 하는데, 방문하지 않는 노드 발견했을 때 증가시켜서 틀렸었다. 코드#include #include #include using namespace std;vector graph[101];bool visited[101];int cnt..

문제 https://www.acmicpc.net/problem/1327 1327번: 소트 게임 홍준이는 소트 게임을 하려고 한다. 소트 게임은 1부터 N까지 정수로 이루어진 N자리의 순열을 이용한다. 이 게임에선 K가 주어진다. 어떤 수를 뒤집으면, 그 수부터 오른쪽으로 K개의 수를 뒤집 www.acmicpc.net 풀이 일단 BFS로 풀어야 한다는 건 알겠는데 도대체 방문배열을 어떻게 처리해야할지 감이 안 잡혔다. 큐에 배열이 포함되어야 할텐데 배열을 어떻게 들고 다녀야할지도 모르겠어서 답을 좀 참고했다. 배열은 문자열로 바꾸면 되고, 방문배열은 값 존재 여부 확인을 편하게 하기 위해 set으로 만들었다. 그외에는 일반 BFS와 유사하게 가능한 경우를 다 돌면서 큐에 저장하면 된다. 코드 #includ..

문제 https://www.acmicpc.net/problem/1283 1283번: 단축키 지정 첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하 www.acmicpc.net 풀이 일단 1) 단어 첫 글자가 단축키로 지정되었는지 확인 2) 모든 첫 글자가 단축키로 지정되어 있다면 한 글자 한 글자 확인 3) 그래도 다 지정되어 있다면 그냥 출력 이 과정을 코드로 구현했다. 단축키로 지정되어 있는지 확인하기 위해 set을 사용했다.(검색이 쉬워서) c++로 문자열 문제 풀 때마다 공백 있는 문자열 입력받는 법, 공백 기준으로 나누는 법을 검색해서 풀고..

문제 : https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 일단 최소시간이니까 bfs로 풀어야겠다고 생각했고, 계속 가지고 다닐 값이 총 3개(화면에 있는 이모티콘 개수, 클립보드에 있는 이모티콘 개수, 시간)라서 tuple을 사용했다. 처음엔 방문배열을 1차원으로 만들어서 답이 잘 안 나왔다. 방문배열을 현재 화면과 클립보드 2개를 체크하도록 2차원으로 수정했는데 그래도 틀림.. 문제는 이모티콘 최대 길이를 잘못 생각한 것이었다. S가 최대..

문제 https://www.acmicpc.net/problem/23300 23300번: 웹 브라우저 2 첫째 줄에 접속할 수 있는 웹페이지의 종류의 수 N, 사용자가 수행하는 작업의 개수 Q 가 각각 주어진다.(1 ≤ N, Q ≤ 2,000) 둘째 줄부터는 Q개의 작업이 주어지며, 각 작업이 의미하는 바는 다음 www.acmicpc.net 풀이 덱을 이용해서 풀이하는 구현 문제이다. 문제 설명대로 차근차근 코드를 작성하면 해결할 수 있다. 뒤로 가기, 앞으로 가기 공간을 구현할 때 스택 대신 덱을 사용했는데, 압축 실행시 인덱스로 접근하고 싶었기 때문이다. 그리고 압축 실행시, 뒤로 가기 공간이 비어있으면 out of bounds 오류가 발생하므로, 먼저 비어있는지부터 확인해야 한다. 코드 #includ..

문제 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 이분탐색과 투포인터 문제이다. 벡터의 첫 원소를 시작으로 기준 원소를 정한다. 그 후, 그 외의 원소들을 이분탐색한다. 각 원소들과 기준 원소의 차이를 비교하며 가장 차이가 적은 원소 2개를 찾는다. 주의할 점! 용액 하나가 10억의 값을 가질 수 있으므로 넘을 수 있으므로 최소값에 넣어 둔 값을 20억 정도로 해줘야 함. 코드 #include #inc..

2차원 배열의 누적합을 구하는 방법을 알아보자. 핵심 포인트는 공통된 부분을 제거한다는 것! 원본 배열에 따른 누적합 배열은 위와 같다. (1,1)을 기준으로 특정 좌표까지의 합을 저장한 것이 누적합 배열이다. (2,2)의 누적합을 구하는 방법이다. 구간합을 구할때는 누적합 배열을 이용한다. 누적합이 (1,1)을 기준으로 구해졌으므로, 해당하지 않는 부분을 빼 준 후, 공통 부분의 누적합을 다시 더해주면 된다.(공통된 부분이라 값이 중복으로 빠졌으므로) 누적합과 구간합을 코드로 구현해보자. 아래의 코드를 2중 for문으로 (1,1)부터 마지막 좌표까지 돌면서 수행하면 된다. * 누적합 구하기 sumArr[i][j] = arr[i][j] + sumArr[i - 1][j] + sumArr[i][j - 1] ..

탐색 범위를 줄여가며 탐색하는 방법. mid 값을 정해서 범위를 줄여나간다. 숫자 정해두고 맞추는 업다운게임과 비슷한 방법. 시간 복잡도는 연산 한 번으로 범위를 절반으로 줄이기 때문에 Log N 이분탐색 코드는 두 부분으로 나뉜다. 범위를 줄여나가는 부분 -> 이분 탐색 범위를 줄일 기준을 정하는 부분(ask 함수 : T/F 반환) -> 결정 문제 1번 부분에서는 left, right, mid값을 정해서 2번 부분이 리턴하는 값에 따라 left, right의 값을 조절해 범위를 줄여나간다. 예시로 백준의 나무 자르기 문제(https://www.acmicpc.net/problem/2805)를 풀어보면, 1번 부분 코드 (이분 탐색) while (left < right) { mid = (left + rig..

문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 이분탐색 문제이다. mid 값을 블루레이 중 최소값으로 두고 이분탐색을 수행한다. 문제에 주어진 예제로 예를 들면, 9 3 1 2 3 4 5 6 7 8 9 mid 16 17 18 구간 [1 2 3 4 5] [6 7] [8 9] 8+9 > 16 => cnt++ [1 2 3 4 5] [6 7] [8 9] [1 2 3 4 5] [6 7] [8 9] cnt 3 2 2 위와 같이 mid 값이 최소값 이..

문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 다익스트라 알고리즘을 이용해서 푸는 문제. 나는 다익스트라를 우선순위 큐를 이용해서 풀었는데, 이 방법은 BFS와 유사하다. 주의할 점은 우선순위 큐를 만들 때, 비용을 기준으로 Min Heap 구조가 되도록 만들어야 한다는 것이다. priority_queue pq; 위와 같이 우선순위 큐를 생성하면 first 값을 기준으로 Min Heap으로 동작..