본문 바로가기

내일배움캠프 안드로이드 3기

 (68)
[TIL] 24.02.08 1. 알고리즘 문제 해결 DSLR(백준 9019): BFS를 이용한다는 것과 로직은 이전 문제들과 흡사하다. 처음에는 큐에 현재까지의 명령어 문자열도 함께 담기도록 했는데, 시간 초과가 났다. 아무래도 문자열의 복사가 반복되다보니, 명령어가 길어질수록 문제가 생길 수 있을 것 같았다. 그래서 그냥 큐에서는 명령어 문자열 대신 직전 값과 직전 명령어가 담기게 했고, 방문 배열에 이를 기록할 수 있도록 했다. 이후 원하는 값에 도달했을 때, 방문 배열을 통해 다시 처음의 값까지 역추적 해서 출력하도록 했고 시간 초과가 나지 않고 통과했다. #pragma GCC optimize("Ofast") #include #include #include using namespace std; int D(int n) { re..
[TIL] 24.02.07 1. 알고리즘 문제 해결 불(백준 5427): 이것도 BFS로 풀 수 있다. 불이 옮겨진 칸을 비롯해 불이 붙으려는 칸도 이동할 수 없으므로, 시간이 지났을 때 불의 번짐처리를 먼저 해주면 된다. 처음에 메모리를 아끼겠답시고, 방문 행렬을 따로 사용하지 않고 기존의 지도 행렬에서 ','를 이용해 방문처리를 해주려고 했다. 그렇게 하니까 불이 먼저 번짐 처리 되었을 때, 방문처리를 동시에 할 수가 없어서 조금 난감했다. 그래서 방문 체크를 조금 느슨하게 했더니 바로 메모리 초과가 났다. 물론 불인데 방문한 곳을 뜻하는 문자를 하나 더 지정했다면 해결할 수 있었을 거 같다. 하지만 직관적으로 짜는게 나중에 코딩 테스트나 사후 리뷰 때 유리한 부분이 있을 것 같아서 그냥 방문 행렬을 따로 만들어 이용했고 바로..
[TIL] 24.02.06 1. 알고리즘 문제 해결 나이트의 이동(백준 7562): 앞서 풀었던 BFS 문제들과 같다. 큐에 좌표 값 및 이동횟수를 집어넣고 BFS를 이용한다. 크게 어려울 거 없는 문제. 토마토(백준 7576): 이것도 BFS 문제인데 관성적으로 풀다가 조금 헤맸다. 익은 토마토들의 위치를 저장해놨다가 각각에 대해 BFS를 하는 식으로 처리하려고 했다가 시간초과가 났다. 매번 모든 부분을 탐색하게 되지 않도록, 숙성에 걸리는 일 수를 업데이트 해주며 나름 pruning을 했음에도 그랬다. 생각을 바꿔서 처음부터 큐에 모든 익은 토마토의 위치를 넣어두고 시작하고서야 해결할 수 있었다. 시작할 때 큐에 꼭 원소를 하나만 넣고 시작할 필요는 없는데, 생각이 갇혀 바로 떠올리지 못한게 아쉬웠다. #include #inc..
[TIL] 24.02.05 1. 알고리즘 문제 해결 숨바꼭질 2(백준 12851): 저번에 풀었던 숨바꼭질 문제와 유사하지만 조금 다르다. 이번에는 가장 빠른 시간으로 동생을 찾는 방법의 수도 출력해야하기 때문에, 저번처럼 BFS를 하면서 단순하게 방문여부로 pruning 할 수 없다. 단순한 방문여부 대신 가장 처음 방문했을 때가 몇 초인지를 저장하는 방식으로 접근해볼 수 있다. 이렇게 되면 이후 탐색 도중 같은 점을 방문하게 되었을 때, 현재의 초와 방문기록에 저장된 초를 비교해 현재의 초가 더 크다면 pruning 할 수 있다. 그리고 반복문의 초반부에 최단 시간으로 찾는 방법이 찾아진 상태인지 확인하고, 그 여부에 따라 가망이 없는 탐색을 중단할 수도, 또다른 최단 시간 도달 방법이라면 카운트에 더해줄 수 있을 것이다. 실..
[TIL] 24.02.02 1. 알고리즘 문제 해결 소문난 칠공주(백준 1941): DFS로 탐색할 때, 행렬 내에서 여러 갈래로 나뉘어지는 것도 고려하는 방법이 없을까 하다가 문제에서 주어지는 행렬이 5*5라서 브루트 포스 및 백트래킹으로 조합을 모두 따지기로 했다. 알고리즘을 간단하게 정리하면 다음과 같다. - 25명의 학생 중 7명을 선택하는 모든 조합을 탐색한다(브루트 포스 및 백트래킹 이용). 누구를 선택했는지, 현재까지 선택된 이다솜파 학생이 몇 명인지 전역변수를 통해 관리한다. - 7명을 선택했을 때, 이다솜파의 학생이 4명 이상인지 확인하고 DFS를 실행한다. - DFS에선 7명의 학생 중 한 명을 선택해(마지막에 추가된 학생) 스택에 넣고 DFS를 진행하게 되는데, 이 때 탐색하며 스택에 담을 수 있는 경우는 인접..
[TIL] 24.02.01 1. 알고리즘 문제 해결 연결 요소의 개수(백준 11724): 방문노드를 체크하는 배열을 따로 저장해두고, 모든 정점에 대해 DFS를 돌려 방문처리를 하되 이미 방문한 노드에 대해 DFS를 돌릴 차례라면 패스한다. 이 때 DFS를 돌린 횟수를 카운트해주면 된다. 바이러스(백준 2606): DFS 구현 후, 1번 컴퓨터를 시작으로 방문처리 해주면서 카운트 해주면 된다. 출력에서 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터 수를 출력하도록 하고 있으므로, 1번 컴퓨터는 제외한다. 빙산(백준 2573): 주어지는 배열의 크기가 최대 300*300으로 크지 않다. 그래서 필요하다면 배열 전체 탐색을 활용할 수 있다. DFS 함수를 만들어 좌표값을 주면, DFS를 통해 인접한 다른 빙산들을 방문하며 방문..
[TIL] 24.01.31 1. 앱개발자 JD 분석 24년 1월 31일 현재, 채용 공고가 올라와있는 기업들로 몇 개를 골라 리스트업 했다. -KB캐피탈 [KB캐피탈(케이비캐피탈)] KB차차차 안드로이드 개발자 채용 공고 | 원티드 (wanted.co.kr) [KB캐피탈(케이비캐피탈)] KB차차차 안드로이드 개발자 채용 공고 | 원티드 KB캐피탈(케이비캐피탈)의 KB차차차 안드로이드 개발자 포지션을 확인해 보세요. 취업·이직에 성공하면, 합격보상금 50만원을 드립니다. www.wanted.co.kr -버킷플레이스(오늘의 집) 채용 공고 | 프로그래머스 (programmers.co.kr) 채용 공고 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들..
[TIL] 24.01.30 1. 알고리즘 문제 해결 트리의 지름(백준 1167): 정점의 개수가 100,000개까지 들어올 수 있기 때문에, 브루트 포스나 인접행렬을 이용할 순 없다. 가장 긴 거리를 이루는(사이의 가중치가 큰) 두 정점 중 하나를 알 수 있다면, 그 정점에서 DFS로 가장 멀리 있는 정점을 찾아낼 수가 있다. 그래서 두 정점 중 하나를 알아내는 방법을 떠올리는 것이 핵심이라고 생각했다. 트리에서 지름을 이루는 부분을 일자로 길게 펼친다고 생각해보면, 트리 내의 어떤 정점에서든 가장 멀리 떨어진 정점이 지름을 구성하는 두 정점 중 하나라는 사실을 직관적으로 떠올릴 수 있다. 이를 바탕으로 구현하기 위해 특정 정점에서부터 가장 멀리 떨어진 정점 및 그 가중치 합을 리턴하는 DFS 함수를 만들었다. 그리고 1번 정점을..

티스토리툴바