본문 바로가기

전체 글

 (166)
[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번 정점을..
[TIL] 24.01.29 1. 알고리즘 문제 해결 2022는 무엇이 특별할까?(백준 24268): 간단한 백트래킹 문제이다. 브루트 포스가 아닌 어떤 수학적인 솔루션이 있지 않을까 계속 고민하다가 오히려 애를 먹었다. 한참 구현하다보니 코드 분기 처리가 너무 난잡해져서, 그제서야 브루트 포스로 구현했다. 단순하게 모든 경우를 고려하려고 하면 d^d 개의 케이스를 탐색해야해서 시간 초과가 난다. 처음에 이 생각 때문에 곧장 브루트 포스로 풀지 않았던건데, 다시 생각해보니 등장한 숫자들을 따로 저장해주는 배열이 있다면 d! 개의 케이스로 줄어들어서 충분히 풀 수 있었다. 또, d^(d-1) 자리는 문제 조건에 의해 0이 들어갈 수 없기 때문에 더 줄일 수 있다. 저정도 조건만 가지치기 해주고 백트래킹으로 풀었더니 무난하게 통과했다...
[TIL] 24.01.26 1. 알고리즘 문제 해결 Z(백준 1074): 간단한 분할 정복 문제, 한번 분할 할 때마다 크기가 4분의 1로 줄어든다. 먼저 배열의 중심을 기준으로 좌상단, 우상단, 좌하단, 우하단으로 나누어 찾으려는 좌표가 어디에 속하는지 찾는다. 이제 기준이 되는 배열 좌표를 수정하고, 좌표가 속한 위치에 따라 order값을 더해둔다(ex - 좌하단이었다면 변의 길이*변의 길이*2). 변의 길이를 절반으로 줄이고, 변의 길이가 1이 될 때까지 반복한다. 반복이 끝나면 order값을 출력한다. 시간복잡도는 O(N). 쿼드트리 (백준 1992): 마찬가지로 간단한 분할정복 문제이다. 재귀를 이용해서 문제 내용을 그대로 구현하면 쉽게 해결된다. 압축 함수를 만들고 전달받은 범위 내 원소가 모두 같은지 확인해서 같다면 ..

티스토리툴바