본문 바로가기

Algorithm46

[백준] 17837번 : 새로운 게임 2 (C++) (삼성 SW 역량테스트) https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 삼성 기출답게 빡구현 문제였다. 이 문제에서 핵심은 deque horse[12][12]를 통해 각 좌표마다 쌓여있는 말들의 번호를 저장하는 것이었다. vector가 아닌 deque를 사용한 이유는 말 이동 시 말의 순서를 유지해야했기 때문이다. 또 하나 신경썼던 부분은, 파랑색인 경우나 범위 밖인 경우를 제일 먼저 확인해서 방향을 바꾸어주었고, 새로운 방향으로 탐색했을때 또다시 범위밖이거나 파.. 2021. 9. 19.
[백준] 1759번: 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 브루트포스 알고리즘 + 백트래킹으로 구현하였다. 우선, 알파벳을 오름차순으로 정렬 한 후 백트래킹을 통해 정렬된 순서를 유지하면서 L개를 선택하는 모든 경우를 탐색하였다. 그 후, 조건에 맞으면 출력하였다. 백트래킹 함수에서 처음엔 매개변수를 cnt로만 두었다. 하지만, 그렇게 하면 정렬된 순서를 유지하지 못하고 뽑았던 문자 조합을 순서가 바뀐 모양으로 또 선택하게 되서 비효율적이었다. 따라서, 현재 .. 2021. 9. 17.
[백준] 1753번 : 최단경로 (C++, 다익스트라) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 우선순위 큐에 { 노드번호, 가중치 } 순서로 넣으면 정렬이 노드 번호가 작은 순서, 같으면 가중치가 작은 순서로 우선순위 큐가 작동하기 때문에 시간초과가 떴다. 따라서, { 가중치, 노드번호 } 순으로 넣어 해결하였다. #include #include #include using namespace std; int V, E,K; vector vec[20001]; int D.. 2021. 9. 17.
[프로그래머스] 정수 삼각형 (C++) https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr DP문제이다. 아래와 같은 삼각형이 있을때, 위에서 밑으로 내려가는 방향으로 2차원 dp배열을 통해 최대 누적합을 갱신시켜주었다. 그리고, 맨 아래에 있는 누적합 결과중 가장 큰 값을 출력해주었다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 ↓ 7 10 15 18 16 15 20 25 20 19 24 30 27 25 24 => 제일 큰 누적합은 30 #include #include #include #include using n.. 2021. 9. 16.
[백준] 1197번 : 최소 스패닝 트리 (C++) https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 크루스칼 알고리즘으로 구현하였다. #include #include #include using namespace std; int V, E; int A, B, C; int getParent(int parent[], int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent, par.. 2021. 9. 15.
[프로그래머스] 거리두기 확인하기 (C++) (2021 카카오 채용연계형 인턴십) https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 2021 카카오 채용연계형 인턴십 코테에서 직접 풀었던 문제이다. 그때도 이 문제는 해결했.. 2021. 9. 11.

티스토리툴바