본문 바로가기

분류 전체보기103

[백준] 11005번 : 진법 변환 2 (C++, JAVA) https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 2가지 방법으로 풀어보았다. 기억해야할 것은 정수형 숫자에 + '0' 하면 '숫자' 꼴인 char형으로 변환이 되고 정수형 숫자 + 'A'를 하면 숫자만큼 알파벳이 증가한다. 예시) 0 + 'A' = 'A' 1 + 'A' = 'B' 2 + 'A' = 'C' 5 + '0' = '5' 6 + '0' = '6' #include #include using namespace std; int N, B;.. 2021. 9. 21.
[백준] 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.
[알고리즘] 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 사용하는 특징을 가지며, 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있다. 작동 과정 0. 모든 노드의 최소비용을 INF로 초기한다. 1. 시작 노드를 설정하고, 해당 노드의 비용을 0으로 해준다. 2. 시작 노드를 기준으로 각 노드의 최소 비용을 저장한다. 3. 방문하지 않은 노드 중에 가장 비용이 적은 노드를 선택한다. 이 때, 비용이 같은 노드가 여러개 있다면 맨 앞에 있는 노드를 선택한다. 4. 해당 노드를 거쳐서 특정한 노드를 가는 경우를 고려하여 최소 비용을 갱신한다.. 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.

티스토리툴바