본문 바로가기

전체 글241

[프로그래머스] 가장 먼 노드 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr그래프 Graph  이런식의 그래프가 주어집니다. 간선에 붙은 가중치는 없구요. 양방향 간선이고, [점1, 점2] 을 요소로 갖는 배열이 하나 주어짐. 노드는 n개, 노드 번호는 1~n. 이때, 1로 부터 최단 경로가 가장 먼 노드는 몇개인가.즉, 1을 제외한 모든 노드에 대해 1부터 해당 노드까지 도달하는 최단 경로를 구하고, 그 중 가장 먼 거리에 있는 노드는 몇개인지 묻는 문제.즉, (ㅇㄴ) 최단 경로 중에 최댓값을 뽑고, 이 최댓값이랑 거.. 2024. 10. 31.
[프로그래머스] 정수 삼각형 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krDP 동적계획법 이런 정수 삼각형이 2차원 벡터 배열로 주어지고, 대각선 왼쪽 한칸 혹은 오른쪽 한칸으로만 이동하면서 내려갈 수 있다고 할 때, 거치는 수들의 합이 최대값을 반환하는 문제.         접근방법2차원 배열을 똑같은걸 하나 복사해두고, 이걸 각 위치까지 오는데 거친 수들의 합의 최댓값을 저장해두는 용도로 사용한다. (accTri) = 최대누적트리라고 하겠다.그리고 맨위에서 부터 맨 마지막 바로 전 줄까지 보면서, 내가 갈 수 있는.. 2024. 10. 30.
[프로그래머스] 섬 연결하기 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/42861?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr그리디N개의 섬과 그 섬을 잇는 다리 건설 정보가 2차원 배열로 주어진다.costs배열은 (출발점, 도착점, 비용)을 원소로 갖는 배열임이때, 모든 섬이 서로 연결되도록 다리를 설치하는 데 드는 최소비용을 반환하는 문제 접근방법처음에는 DFS로 풀어보려고 했다가 안돼서 그리디 문제 답게 그리디하게 풀었다 (?)목적은 1) 새로운 섬을, 2) 적은 비용으로 가는 것.그래서 이미 방문한 섬으로부터 갈 수 있는 섬들 중, 가장 .. 2024. 10. 29.
[프로그래머스] 피로도 (Swift) https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=swift 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr완전탐색 (DFS)N개의 던전을 탐색하는 문제인데, k만큼의 체력을 갖고 있을 때, 각 던전에 들어갈 때 필요한 체력과, 각 던전을 들어갔을 때 실제로 사용되는 체력이 주어지고, 최대한 많은 던전을 탐색할 수 있는 경우를 구하는 문제탐색 순서가 달라질 수 있다는 게 문제다 접근방법dfs 재귀 방식으로 풀었는데, 종료조건을 어떻게 두어야 할지 고민했다. 그래서 처음에는 모든 던전을 실제로 들어갔거나, 더이상 들어갈 수 있.. 2024. 10. 28.
[백준 1916] 최소비용 구하기 (C++) https://www.acmicpc.net/problem/1916다익스트라도시를 연결하는 단방향 버스 (출발점, 도착점, 비용)이 주어지고임의의 출발점과 도착점이 주어졌을 때, 이 둘을 잇는 최소 비용을 출력하는 문제 접근방법 음수인 비용이 없어서 다익스트라로 풀어도 된다. (벨만포드로 안풀어도 됨)이거 풀다가 내가 다익스트라를 제대로 이해하고 있는게 맞나 의심했음..다시 공부해야 할 것 같다..다익스트라 기본 개념은 임의의 출발점 하나에 대해 모든 노드에 대한 최소 거리를 저장하고 있는 1차원 배열이 하나 있고,방문한 노드를 하나씩 추가해 가면서 이 배열을 갱신하는 방식이다. 이 문제를 풀 때는,- 인접행렬 (각 노드에 대해 연결된 버스 노선을 담고 있는 2차원 배열. ex. 1번: {(2번도시, 비용.. 2024. 10. 23.
[프로그래머스] 다리를 지나는 트럭 (Swift) https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr스택/큐 (Queue)N대가 올라갈 수 있는 다리가 있고, 이 다리는 W만큼의 무게만 견딜 수 있음.이때, 대기하고 있는 M개의 트럭의 무게가 순서대로 담긴 배열이 주어진다.1초에 한칸씩 이동할 수 있다는 설정이 있는듯(ex. 트럭이 1개여도 다리 길이가 100이면 101초가 걸림)이때 모든 트럭이 다 다리를 건더는 데 몇초가 걸리는지 반환하는 문제(모든 트럭 한 대의 무게는 W 이하이다 = 못올라가는.. 2024. 10. 22.
[백준 1700] 멀티탭 스케쥴링 (C++) https://www.acmicpc.net/problem/1700그리디 Greedy멀티탭 구의 개수랑 전기용품 사용 순서가 주어지면 플러그를 뺐다 꽂는 횟수의 최솟값을 출력하는 문제 접근 방법우선 꽂혀있는지 확인 (isOn 배열 사용 - 기기별 꽂혀있는지 여부 저장), 멀티탭에 여유공간이 있는지 확인(멀티탭 여유공간 count)꽂혀있지도 않고, 멀티탭이 모두 사용중인 경우에 대해,1. 뽑을 기기 번호 (target), 지금 사용 순서와 꽂혀있는 기기의 사용 순서 사이의 거리 (distance) 초기화2. 꽂혀있는 기기에 대해서 하나씩 스케쥴상의 거리 계산2-1. 이때 이미 등장했던 기기가 또 나올 수 있기 때문에, 기기가 처음 등장하는 순서와의 거리만 계산해야 하기 때문에, existLater라는 변수를.. 2024. 10. 22.
[프로그래머스] 프로세스 (Swift) https://school.programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  스택/큐 (Queue)N개의 프로세스에 대해 우선순위를 나타낸 배열이 하나 주어지고처음부터 프로세스를 보면서 우선순위가 더 높은 게 뒤에 있을 경우 큐의 맨 뒤로 보내는 식으로프로세스를 실행할 때, 특정 프로세스의 위치(인덱스)를 입력받아 해당 프로세스가 몇번째로 실행되는지 반환하라는 문제 접근방법스위프트는 Queue가 collection에 없기 때문에 array를 사용해서 dequeue은 remo.. 2024. 10. 18.
[백준 1062] 가르침 (C++) https://www.acmicpc.net/problem/1062  Back tracking (백트래킹) k개의 글자를 가르칠 수 있을 때, 주어진 N개의 문자열 중 최대 몇개를 읽을 수 있게 할 수 있는지 출력하는 문제단, N개의 문자열은 모두 anta로 시작하고 tica로 끝난다. = 최소 acnti 는 가르칠 수 있어야 단어를 한개라도 가르칠 수 있음 접근 방법처음에는 N개의 문자열을 dfs로 순회하면서 읽을 수 있는 문자열 그룹의 경우를 모두 확인하려고 했는데,26개의 알파벳 중 가르칠 문자 그룹의 모든 경우에 대해서 각각 그룹이 읽을 수 있는 문자열의 갯수를 구하면서최댓값을 찾는 것이 시간초과가 나지 않는 풀이법이었다. N이 50개까지 밖에 안가지만 그래도 시간복잡도가 26에 비해서는 커질 수 .. 2024. 10. 17.
[프로그래머스] 베스트 앨범 (Swift) https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr해시 Hash N개의 노래에 대해 장르 배열 1개, 재생수 배열 1개가 주어지고장르별로 2곡을 뽑아 하나의 앨범을 만들어야 함. > 앨범 트랙리스트 (배열 인덱스 = 노래의 고유번호)를 반환하는 문제앨범에 수록 되는 노래 순서 중요곡 선정 과정 1) 총합 재생수가 높은 장르의 곡 먼저 수록, 2) 재생수가 많은 곡 먼저 수록, 3) 재생수가 같을 경우 고유번호가 작은 순으로 수록 접근방법Swift di.. 2024. 10. 15.
[백준 14719] 빗물 (C++) https://www.acmicpc.net/problem/14719 문제각 열의 기둥 높이가 주어지고 그 사이에 채워지는 칸의 수를 출력하는 문제 접근 방법이게 맞는 방법인진 모르겠지만 W가 최대 500이어서 왔다갔다 두번하는 식으로 했다.처음에는 왼쪽에서 오른쪽으로 가면서 지금까지 가장 높았던 기둥(curMax)의 높이와 인덱스를 저장한다.그러면서 현재 보고 있는 기둥이 curMax 기둥보다 낮을 경우 -> curMax - 현재 기둥 높이 를 tmp에 더한다.이때 tmp는 임시로 고인 빗물의 양이다.그리고, 현재 보고 있는 기둥이 curMax 기둥보다 같거나 높을 경우 -> 지금까지의 고인 물이 고이는 것이 확정되므로tmp 값을 result 에 더해주고 tmp를 0으로 초기화한다. 문제는 tmp에 임시.. 2024. 8. 1.
[백준 2504] 괄호의 값 (C++) https://www.acmicpc.net/problem/2504문제주어진 올바른 괄호 문자열에 대해서만 규칙대로 값을 계산해서 출력하는 것규칙은 (()[[]]) 이런 문자열이라면 2*(2+3*3) = 22 가 된다. 접근방법다른 블로그들을 참고해서 풀었는데, 풀이 방법은 '겉 괄호는 본인이 끝날때까지 안쪽 괄호 모두에게 영향을 미친다'라고 생각하면 될 것 같다.그리고 계산식을 모두 풀어서 최대한 긴 다항식으로 만든다. 가 포인트인듯뭔말이냐면 위에서 2*(2+3*3) -> 2*2 + 2*3*3 으로 만든다는 것임이걸 만드는 방향으로 코드를 짜서 풀었다. 따라서 tmp 변수를 선언해두고 answer 변수에 값을 더해가면서 풀어야 함(, [ 가 나오면 우선 tmp에 2를 곱한다. 이제 앞으로 나오는 계산에는.. 2024. 8. 1.

티스토리툴바