C++
[프로그래머스] 프렌즈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을 사용해 구할 수 있다..
[백준] 17070번 - 파이프 옮기기 1
💡 깊이 우선 탐색 (DFS) 삼성 A형 기출문제라 해서 풀어봤는데, DFS로 손쉽게 풀 수 있는 알고리즘 문제였다. 먼저 파이프를 밀어 옮겨야하는 상황에서 파이프에 옮기는 방법은 가로 2가지, 세로 2가지, 대각선 3가지인데 DFS를 이용해 조건을 잘 맞추어 모든 상황을 고려해 만들어주면 된다. 가로인 경우 - (x,y+1), (x+1,y+1) 세로인 경우 - (x+1,y), (x+1,y+1) 대각선인 경우 - (x,y+1), (x+1,y), (x+1,y+1) 이때 주의할점은 옮겨야 할 곳이 1인 곳은 가지 못하도록 해줘야하는데 가로와 세로는 각각 (x+1, y)와 (x, y+1)만 고려해주면 되지만 대각선은 (x-1,y) (x,y-1) (x,y), 총 3가지를 고려해줘야 한다. ✏️ 구현 코드 #in..
크루스칼 알고리즘 (Kruskal Algorithm)
👉 크루스칼 알고리즘은 MST(최소 스패닝 트리) 찾는 알고리즘들 중 하나입니다. (나머지 하나는 Prim 알고리즘) 💡 MST란? 그래프의 연결성을 그대로 유지하는 가장 '저렴한' 그래프를 찾는 문제 크루스칼 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 가는 방식으로 동작합니다. 하지만, 가중치가 작다고 해서 무조건 간선을 트리에 더하는 것이 아닌, 사이클이 생기는 간선을 고려해 제외 해줍니다. 👉 동작하는 과정 위 그래프를 보면 가중치가 1인 간선, 2인 간선, 3.. 순서대로 선택해 가고 있습니다. 이때 4번째에서 5번째를 보면 가중치가 3인 간선들이 남아 있는데도 불구하고, 4인 (c,d) 간선이 추가됩니다. 그 이유는 3인 간선들이 추가되면 트리..