목록알고리즘 문제 풀이 (239)

반갑습니다!

[백준] 2631줄 세우기

2631번: 줄세우기 boj.kr 풀이 이 문제는 LIS 알고리즘을 통해 해결할 수 있다. 키 순서가 오름차순으로 정렬된 아이들은 이동시킬 필요가 없다. 나머지 아이들을 최장 증가 수열에 속해있는 아이들 사이에 넣어주면 되기 때문에 LIS 알고리즘을 통해 최장 증가 수열의 길이를 계산한 뒤, 전체 어린이 숫자에서 빼주면 정답이 된다. 아래의 코드는 O(nlogn)의 복잡도를 갖는 LIS 알고리즘을 구현했다. 코드 C++
알고리즘 문제 풀이 2020. 10. 22. 15:28
[프로그래머스] 최고의 집합

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이 문제는 그리디하게 해결했다. 이 문제의 핵심 아이디어는 곱하는 수들 간의 차이가 가장 적게 하는 것이다. 만약 s가 9이고, n이 3이라고 가정해보자. 이 때는 3, 3, 3을 곱해야 가장 크다는 것을 직관적으로 알 수 있을 것이다. 이번엔 s가 24이고 n이 6을 생각해보자. 이 역시 4, 4, 4, 4, 4, 4를 곱해야 최대값이 된다는 것을 알 수 있다. 지금까지의 예시는 모두 s를 n으로 나눈 나머지가 0인 경우였다. 이번엔 s가 n으로 나누어떨어지지 않는 경우를 생각해보자. s가 11이고 n..
알고리즘 문제 풀이 2020. 10. 22. 00:00
[프로그래머스] 섬 연결하기

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 모든 섬을 연결하라는 의미는 결국 MST를 만들라는 말과 같다. 아래의 코드에서는 입력으로 들어온 costs 벡터를 edges 벡터에 저장하고 kruskal 알고리즘을 사용해 MST를 생성해서 해결했다. 코드 C++
알고리즘 문제 풀이 2020. 10. 21. 23:40
[백준] 1915 가장 큰 정사각형

1915번: 가장 큰 정사각형 boj.kr 풀이 이 문제는 동적 계획법을 사용해야한다. 이 문제의 핵심 아이디어는 위에서부터 탐색하면서 최대 크기의 정사각형을 갱신하는 것이다. 즉 dp[i][j] = (j, i)에서의 최대 정사각형의 길이가 된다. (수학에서 사용하는 좌표계를 기준으로 x, y 순으로 좌표를 표현했음을 참고할 것) 배열을 board[][]라고 하겠다. 그러면 board[i][j]가 1인 곳은 변의 길이가 1인 정사각형이다. 변의 길이가 2인 정사각형은 board[i][j], board[i-1][j], board[i][j-1], board[i-1][j-1]이 모두 1이어야 한다. 이 문제의 풀이는 여기서 힌트를 얻을 수 있다. 아래의 예시를 보면서 좀 더 알아보자. (0, 0 ~ 3, 0)..
알고리즘 문제 풀이 2020. 10. 20. 14:21
[백준] 17472 다리 만들기 2

17472번: 다리 만들기 2 boj.kr 풀이 [프로그래머스] 지형 이동과 유사한 문제인데 개인적으로 조금 더 까다로웠다. 상당히 구현할 것이 많은 문제이다. 해당 문제는 완전탐색으로도 해결할 수 있다고 한다. 아래의 코드는 MST를 사용해서 해결하였다. 이 문제에서 MST를 만들어서 문제를 해결하려면 크게 3단계로 나누어서 풀어야한다. 섬들 라벨링 하기 섬들 간의 거리 구하기 MST 생성하기 우선 섬 라벨링은 BFS 알고리즘을 통해 할 수 있었다. visited[][] 배열을 선언해 중복 방문을 막아주었다. // 섬들을 구분하기 위해 bfs 알고리즘 사용 void bfs(int x, int y, int idx) { queue q; q.push({ x, y }); visited[y][x] = idx; ..
알고리즘 문제 풀이 2020. 10. 19. 14:44
이전 Prev 1 2 3 4 5 6 7 ··· 48 Next 다음