알고리즘/백준
-
[C++] 백준 11497 통나무 건너뛰기알고리즘/백준 2023. 1. 12. 15:41
HTML 삽입 미리보기할 수 없는 소스 문제 접근법 ** 통나무 개수가 최대 10000개 이므로 이중 for문을 돌리면 테스트 케이스 수에 따라 시간초과가 날 수 있다. 그렇기에 2중 for문을 사용하지않고 문제를 풀려면 그리디 알고리즘으로 접근해야한다. 통나무들의 마지막은 처음과 연결되어 있기 때문에 원형큐와 모양이 비슷하다.하지만 c++에는 원형큐 stl이 없고 굳이 원형큐를 만들 필요가 없으므로 덱을 이용해 마지막과 처음을 편하게 삽입할 수 있도록 했다.
-
[C++] 백준 2638 치즈알고리즘/백준 2023. 1. 6. 14:35
HTML 삽입 미리보기할 수 없는 소스 단순 구현인줄 알고 접근했다가 뒤통수 맞은 문제 bfs 생각을 했다면 한시간은 더 빨리 풀었을텐데 bfs를 사용할 생각을 왜 못했을까.. 1. checkAir 메소드를 호출해 외부 공기와 내부 공기를 체크해야한다. 2. checkMelting 메소드를 호출해 외부 공기와 접촉하는 면이 2 이상일 경우 배열의 값을 0으로 바꿔준다. 3. 전체 배열을 순회하며 배열의 모든 값이 0 일 경우 시간을 출력하고 반복문을 종료한다. 이렇게 쓰고보니 어려울거 하나 없는 문제인데 골드 3이라고 괜히 쫄아서 꼬아 생각했다.
-
[C++] 백준 7490 0 만들기알고리즘/백준 2023. 1. 6. 11:13
HTML 삽입 미리보기할 수 없는 소스 문자열 + 완전탐색을 이용하는 문제 N 의 값이 최대 9 이므로 최대 시간 복잡도는 O(3^9) 로 완전탐색이 가능하다 1. N 의 값을 입력받아 완전탐색 실행 HTML 삽입 미리보기할 수 없는 소스 ** DFS 인자로 공백 문자열 두개를 주는 이유 문제에서 수식을 출력할때 공백을 포함하라 했는데 공백을 포함하게되면 스택을 이용한 계산에 문제가 생기기 때문에 첫번째 인자는 공백을 포함하지 않는 문자열 (스택 계산을 위함), 두번째 인자는 공백을 포함하는 문자열(출력을 위함)을 만들었다. 2. 완전탐색을 이용해 계산한 후 스택의 최종값이 0 이면 결과 벡터에 저장 3. sort 함수를 이용해 결과 메소드 정렬 후 출력 4. 테스트 케이스 수 만큼 반복
-
[C++] 백준 1043 거짓말알고리즘/백준 2023. 1. 4. 17:13
HTML 삽입 미리보기할 수 없는 소스 살짝 말을 어렵게 풀어낸 bfs 문제 1. 진실을 아는 사람이 참가하는 파티를 큐에 저장 2. 진실을 아는 사람이 참가하는 파티에 참가하는 사람들이 참가하는 파티 또한 큐에 저장 (이 논리를 생각하는게 어렵다) 진실을 아는 사람이 참가하는 파티 == x 진실을 아는 사람이 참가하는 파티에 참가하는 사람들 == party[x][i] 진실을 아는 사람이 참가하는 파티에 참가하는 사람들이 참가하는 파티 == person[party[x][i]][j] HTML 삽입 미리보기할 수 없는 소스 중요한건 거짓말을 칠 수 있는 파티를 계산하는 것이기 때문에 큐를 돌릴때 큐의 인자가 파티가 기준이 되어야한다. 역시 거짓말 치는건 주변인의 주변인까지 속여야 하는 어려운 작업이니까 거짓..
-
[C++] 백준 10836 여왕벌알고리즘/백준 2023. 1. 4. 13:39
HTML 삽입 미리보기할 수 없는 소스 아이디어를 생각해내면 쉽게 풀 수 있는 문제 날짜 수는 1,000,000 이고 가로 세로가 700 이므로 날짜 하루당 모든 배열을 초기화 해주면 O(1,000,000 * 50,000) 으로 시간초과가 나게 될 것이다. 결국 O(1,000,000) 으로 처리를 해야하는데 어떻게 해야할까?? 1. 여왕벌이 자라는 값은 고정값이므로 위치에 따른 증가값을 누적해서 갱신해준다. 2. N번 만큼 갱신이 끝났으면 증가값을 왼쪽 아래 부터 차례대로 더해준다 3. 1,1 부터 시뮬레이션 알고리즘을 이용해 완전탐색 해서 좌, 좌상, 상 세가지 값중 가장 큰 값을 찾아 갱신해준다. 결국 제일 왼쪽 열과 제일 위쪽 행을 초기화 하고 (1,1) 부터 탐색하면 좌, 좌상, 상 세가지 값을 ..