본문 바로가기

전체 글

 (65)
2022/08/22 (월) 오늘은 백준 9376 탈옥 문제를 공부했다. 해당 문제에서 deque를 통해 우선적으로 탐색할 경우를 앞쪽에 배치하고, 그렇지 않은 경우는 deque의 뒤에 배치하여 우선적으로 탐색하는 0-1 BFS알고리즘에 대해 공부할 수 있었다. 해당 알고리즘과 비교하여 노드 탐색의 최소 거리를 저장하는 다익스트라 알고리즘을 복습하는 계기가 되었다. 끝!
[백준 9376][C++] 탈옥 문제 https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 풀이 과정 [참고 링크 1] [참고 링크 2] [0-1 BFS 알고리즘 링크] 필자는 링크 1의 코드를 기반으로 풀이를 작성했다. 해당 문제는 0-1 BFS 알고리즘을 통해 다익스트라 알고리즘보다 효율적으로 구현할 수 있다. 주변의 위치에 존재하는 BFS탐색 시, 문이거나 문이 아닌 경우로 나뉘기 때문이다. 이 문제의 핵심은 아래 3가지 경우를 모두 고려해야 한다는 점이다. 1) 1번 죄수가 탈출하며 문..
2022/08/19 (금) 오늘은 백준 11049 행렬 곱셈 순서 문제를 공부했다. 분명 풀이가 이전에 풀었던 문제와 굉장히 유사함에도 구현하는 것이 어려웠다. 아직 DP에 대한 깊은 생각과 구현의 실마리를 찾는 것이 어려웠다. 토익 단어장 1 회독을 마쳐서 다음엔 어떤 영어 공부를 할지 고민 중이다. 각 Day마다 점수별 추가 단어가 있는데 이 것들을 복습하면서 다시 시작할까 생각 중이다. 끝!
[백준 11049][C++] 행렬 곱셈 순서 문제 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 과정 [참고 링크] 해당 문제는 11066 파일 합치기 문제와 매우 유사하다. 파일 합치기 문제를 풀이했을 때 사용했던 알고리즘과 동일한 구조로 동작하도록 구현하기 위해 위의 링크를 참고했다. 해당 문제와 동일한 블로그의 포스팅이다. 설명이 매우 자세하고 충분히 이해하고 DP를 적용한 코드를 사용할 수 있었다. 해당 포스팅을 보고 공부 중 어려웠던 부분을 다른 사람들이 더 ..
2022/08/17 (수) 오늘은 백준 1956 운동 문제를 풀었다. 2학년 때 알고리즘 시간에 배웠던 내용이라 떠올리기 쉬웠고, 구현이 어렵지 않아서 쉽게 풀 수 있었다. 하지만 해당 문제에서 여러 번 '틀렸습니다'를 받았는데, 결국 INF 값 설정이 생각보다 작아서였다. 이러한 max 값 설정에 주의를 기울이지 않은 것을 반성할 수 있었다. 토익 단어장 Day 1 진행 opening 공석, 결원; 개장, 개시 / applicant 지원자, 신청자 / candidate 후보자, 지원자 / confidence 확신, 자신; 신임 / highly 매우, 대단히 / eligible 자격이 있는, 적격의 / managerial 관리의 / diligent 성실한 / proficiency 숙달, 능숙 / prospective 장래의, 미래..
[백준 1956][C++] 운동 문제 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 풀이 과정 플로이드-워셜(floyd-warshall) 알고리즘을 이용한다. 해당 알고리즘은 2차원 배열을 이용하여 두 노드를 잇는 최단거리를 구하는 알고리즘이다. 이때 노드의 최단 거리를 구할 때 자기 자신의 노드는 0으로 설정하는데, 이 부분만 수정한다면 위의 문제를 해결할 수 있다. 아래의 그림은 플로이드 워셜 알고리즘이 적용되기 전, 후의 상태를 나타낸..
2022/08/16 (화) 오늘은 백준 2933 미네랄 문제를 풀었다. 메모리 초과가 queue에서 발생한 것 같다. 이전 백조의 호수 문제에서와 같이 메모리 초과가 계속 발생했다. queue 사용에서 아직 많이 문제가 있는 것 같다. queue에 넣고 map을 수정하는 것으로 안 되는 것인지, BFS풀이에 visited 배열을 통해 방문 체크를 추가했을 때도 메모리 초과가 발생했는데, 더 공부를 해봐야 할 것 같다... DFS로 변환해서 풀었더니 답을 얻을 수 있었다! 토익 단어장 Day 2 진행 attire 복장, 옷차림새 / code 규범, 관례; 암호 / concern 우려, 걱정; 문제, 일 / policy 규정; 보험 증권 / comply 준수하다, 따르다 / adhere 지키다, 고수하다 / refrain 자제하다, ..
[백준 2933][C++] 미네랄 문제 https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 풀이 과정 1. 문제 조건에 맞게 입력을 받는다. 2. 순서대로 발사하여 미네랄을 부순다. 3. 부순 미네랄을 기준으로 주변을 탐색하여 미네랄 군집(cluster)을 파악하고, 중력에 의한 이동을 수행한다. 4. 최종 형태를 출력한다. 세부 풀이 (1) 초기 형태와 이후 던질 막대의 높이에 대한 정보도 한 번에 입력받아 order 배열에 넣어 저장한 뒤 사용했다. (2) shoot 함수 order 배열에 ..

티스토리툴바