Algorithm/Problem and Strategies
[백준] 2213번 - 트리의 독립집합
https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 �� www.acmicpc.net 💡 원리 트리의 정점에 가중치가 있으며, 독립집합을 찾는 문제이다. 문제를 잘 읽어보면 트리의 동적 프로그래밍을 사용하면 풀리는 문제인데, 이 문제는 더 나아가 출력으로 가장 큰 독립집합의 값의 정점을 찾아 출력을 해야한다. 우선 동적 프로그래밍을 사용해 가장 큰 독립집합을 찾아보자 트리의 형태이기 때문에 root=0 부터 차례대로 정점을 탐색할 수 있고, 동..
[프로그래머스] 프렌즈4블록
2018 카카오 블라인드 채용 1차 코딩테스트에서 나온 난이도는 상에 해당하는 문제이다. https://programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙�� programmers.co.kr 처음에 이 문제를 봤을 때 그래프와 같은 표가 나와 그래프 자료구조(BFS,DFS)로 접근하려고 했었는데, 좀 더 생각해보니 지워야할 코드의 수는 2X2로 제한되어 있었기 때문에 간단한 반복문으로 해결 할 수 있는 문제였다. 이 문제에서 가장 신경 썼..
[백준] 15684번 - 사다리 조작
https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 💡 원리 문제의 정답 비율을 보고 풀기에 무서웠던 문제였다. 하지만 문제를 잘 읽고, 잘 생각하면서 코드를 짜면 생각보다 쉽게 풀어지는 문제였다. 이 문제는 쉽게 주변에서 볼 수 있는 사다리 타기 게임과 같은 원리의 문제이다. 하지만 사다리 타기 게임과 다른 점은 두 가로선이 연속하면 안 되는 것에 있었다. ( 이 조건은 이 문제를 정말 쉽게 풀 수 있게 해주는 조건이였다.) 이 문제의 가장 중..
[백준] 2580번 - 스도쿠
https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 💡 스도쿠란? 스도쿠는 숫자 퍼즐로, 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐이다. 숫자넣기로도 불린다. “숫자는 한 번씩만 쓸 수 있다”(数字は独身に限る 수'지와 독'신'니가길[*])[1]를 줄인 말로 2005년 전 세계적으로 이 말과 퍼즐이 퍼져나갔다. 퍼즐을 푸는 방법은 아홉 가로줄, 세로줄, 3X3 칸에 1에서 9까지의 숫자를 중복되지 않게 한 ..
[백준] 14888번 - 연산자 끼워넣기
ps://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 처음에 연산자가 아닌 수들의 순서도 바뀔 수 있는줄 알고 푸는 방법을 생각해내는데 애를 먹었었다. 하지만 나중에 수들의 순서는 고정된 것을 알아채고, 연산자의 순서만 바뀐다는 것을 알고 해결방법을 쉽게 생각해낼 수 있었다. 만약 수들이 모여 있고, 이 수들의 모든 경우의 수를 구하고 싶다면 next_permutation을 사용해 구할 수 있다..
[백준] 9205번 - 맥주 마시면서 걸어가기 (카스텐라우프)
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 문제 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발 www.acmicpc.net ✏️원리 Kastenlauf 카스텐라우프는 독일에서 주로 하는 술게임이라고 한다. 이 문제는 위 게임과 룰이 같으며, 맥주 20병을 담을 수 있는 박스를 들고 페스티벌까지 50m씩 맥주를 마시면서 맥주가 동이 안 날 때까지 마시면서 갈 수 있는지 없는지를 해결해야 하는 문제이다. 이 문제를 보고 나서 처음에 DFS로 풀어야지하며, DFS로 풀어보았다. 하지만 계속 시간초과가 나와, 계속 시간..