티스토리

SiO2whocodes

검색하기

블로그 홈

SiO2whocodes

sio2whocode.tistory.com/m

SiO2whocode 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

[프로그래머스] 도둑질 (C++) DP 동적프로그래밍이런 배치로 되어있는 마을에서 각 집이 보유하고 있는 돈이 배열로 주어짐누군가 이 집들을 털 계획을 하고 있는데, 두집을 연속으로 털지 못함 (!주의! 첫집과 끝집도 함께 털지 못함)최대로 털 수 있는 금액을 반환하는 문제 접근방법dp문제라서 작은 문제로 쪼개서 하면, dp배열에 i번째 인덱스에 저장되는 값은 i번째까지의 금액이다.dp배열의 값을 입력하는 점화식은 아래와 같음dp1[i] = max(dp1[i-1] , dp1[i-2]+money[i]) --> 바로 전 집까지의 최대값(바로 전 집이 포함되어 있을 수 있음) vs 두칸 전 집까지의 최댓값(i바로 전 집은 포함하지 않음) + 현위치의 집 금액 dp배열이 두개 필요한데, 이유는 첫집은 무조건 포함하고 끝집을 포함하지 않는 조건으.. 공감수 2 댓글수 1 2024. 11. 29.
[프로그래머스] 사칙연산 (Swift) DP 동적프로그래밍["1", "-", "3", "+", "5", "-", "8"] 이런 사칙연산을 담은 문자열 배열이 주어진다.빼기의 결합법칙에 따라 계산 결과가 달라지는 것을 고려해서, 어떤식으로 결합했을 때 이 사칙연산의 결과값이 가장 큰 지그 최댓값을 반환하는 문제 접근방법https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.4-%EC%82%AC%EC%B9%99%EC%97%B0%EC%82%B0 [프로그래머스] LV.4 사칙연산사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집.. 공감수 0 댓글수 0 2024. 11. 21.
[프로그래머스] 등굣길 (C++) 탐욕알고리즘 (Greedy)n*m 그리드에서 1,1부터 n,m까지 가는 최단 경로의 경우의 수를 1000000007 로 나눈 나머지를 반환하는 문제가는 경로에 침수된 지점이 k 개 주어진다 (좌표로 주어짐) 접근방법n*m만큼의 2차원 배열 map을 만들고, 0으로 초기화한 후, 침수된 지점은 -1로 표시한다.1,1부터 n,m까지 순회하면서 각 자리에 이 지점까지 오는 경우의 수를 저장한다.즉, r,c 지점은 한칸 왼쪽 자리까지 오는 경우 + 한칸 위쪽 자리까지 오는 경우, 이 두 경우의 수를 합한 경우다.1,1자리에 처음에 1을 넣고 차례로 순회하고나면 n,m에는 학교까지 오는 데 최단거리의 경우의 수가 담긴다.(최단거리인지 체크하지 않는 이유는, n과 m이 1보다 크거나 같고, 오른쪽과 아래쪽으로 밖에.. 공감수 0 댓글수 0 2024. 11. 8.
[프로그래머스] 단속카메라 (C++) 탐욕알고리즘 (Greedy)N개의 차량의 진입지점과 진출지점이 주어지면 모든 차량을 단속할 수 있는 단속카메라의 최소 설치 개수를 반환하는 문제 접근방법진출지점을 기준으로 먼저 나가는 차가 앞에 오도록 차들을 정렬한 후에,첫번째 차 부터 이 차가 나가는 지점에 단속카메라를 설치한다고 할 때, 차례로 차를 순회하며 현재 단속카메라가 단속할 수 있는 차량인지 확인한다.= 반복문에서 가리키고 있는 차의 진입지점이 현재 단속카메라의 위치와 같거나 그 전에 위치하면,해당차는 이미 단속할 수 있으므로 넘어가고,만약, 이 차의 진입지점이 현재 단속카메라의 위치보다 이후에 위치한다면, 해당 카메라로는 단속할 수 없으므로 다시 이 차의 진출지점에 단속카메라를 설치하고, 단속카메라의 총 개수를 1 추가한다. 이렇게 반복문.. 공감수 0 댓글수 0 2024. 11. 7.
[프로그래머스] 구명보트 (C++) 그리디 (Greedy)최대 두명이 탈 수 있으며, limit 만큼의 무게를 감당할 수 있는 구명보트가 있고, N명의 사람들의 무게를 담은 배열이 하나 주어진다. 이때 최소 필요한 구명보트 수 구하기 접근방법힌트를 얻어서 투포인터로 풀었다. 우선 배열을 오름차순으로 정렬하고,왼쪽 포인터 s, 오른쪽 포인터 e 를 배열 양 끝을 가리키도록 한 다음두 포인터가 교차될 때 까지 반복하는 반목문을 들어간다.이 반복문에서는1) 두 포인터가 가리키고 있는 값을 더했을 때 limit 이하이면, 둘다 보트에 탈 수 있으므로 두 포인터 모두 안쪽으로 옮긴다.2) 그러나 더한 값이 limit을 초과하면, 무게가 더 많이 나가는 사람만 탈 수 있다는 의미이므로 오른쪽 포인터 (e) 만 한칸 앞으로 옮긴다. (구명보트 limi.. 공감수 1 댓글수 0 2024. 11. 6.
[프로그래머스] 모음사전 (C++) 완전탐색A, E, I, O, U 으로만 이루어진 단어 사전이 있다. 이 사전에 수록된 단어의 최대 길이는 5일때,특정 단어가 주어지면, 이 단어의 순서를 반환하는 문제 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU" 접근방법어차피 한번에 단어 한개만 주어져서 저장해두고 쓰는 것도 불필요해서, 그냥 매번 순서를 셌다..(이게맞나 암튼 완전탐색임)DFS처럼 순서대로 단어를 체크했고, 이 문제에서는 의외로(?) 관건이 언제 재귀함수를 종료할 것인가 였다.1. cnt 증가 (단어 순서)2. 찾아야할 단어의 순서인지 확인 -> 맞으면 answer = cnt 담고 함수 종료3. 단어의 길이가 5이면 함수 종료 (이래야 단어의 길이가 6인 .. 공감수 0 댓글수 0 2024. 11. 5.
[프로그래머스] 주식가격 (C++) 스택/큐 (근데 이제 안쓴..) 카테고리는 그랬는데 스택이랑 큐를 쓰지 않고, 이중 for문에 중간에 나오는 것만 잘 해줘도 통과됐다..스택으로 푼 케이스를 봤는데, 로직이 어려워서 아직 100%이해하진 못하고 나왔음.. 문제는 N일에 거친 주가가 주어지고, 첫날 부터 차례로 해당 날짜의 주식가격이 떨어지기까지 얼마나 걸리는지 기간을 구하는 문제, 그래서 반환하는 값이 N일의 주가 유지기간을 담은 배열이 된다. 접근방법 스택으로 푸는 방법이 아니라 단순히 해당 날의 주식가격과 다음 날들의 주식가격을 비교하면서카운트를 증가시킨다. 이때 다음 날 중 어느 하나가 본인(해당 날의 주식가격)보다 더 떨어질 경우 반복문에서 나온다.나오면 당시 카운드를 정답 배열에 추가한다. *바로 떨어졌어도 1초?동안은 유지했다.. 공감수 4 댓글수 3 2024. 11. 4.
[프로그래머스] 전력망을 둘로 나누기 (C++) 완전탐색 N개의 송전탑이 하나의 트리를 구성하며 연결되어 있는데, 간선 하나를 잘라서 두개의 트리로 분리할 때이 두개의 트리의 송전탑 개수 차가 최소가 되는 그 최소값을 반환하는 문제 두 송전탑을 잇는 간선이 이렇게 wires 라는 배열로 주어짐 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]간선은 한개씩만 주어지지만 양방향 간선임접근방법 완전탐색인 만큼..모든 간선을 잘라보면서 두 그래프의 노드 수 차이를 구해보면 된다.우선 인접행렬을 만들어서 사용했고,하나의 간선 (1,3) 을 자르면, 1로 시작해서 갈 수 있는 노드들을 모두 센다 큐를 하나 만들어서 bfs처럼 풀었음근데, 노드를 방문할 때 3이면 방문하지 않음 => 3으로부터 뻣어갈 수 있는 노드들은 방문하.. 공감수 2 댓글수 0 2024. 11. 4.
[프로그래머스] 폰켓몬 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krHash 해시폰켓몬 - [3,3,3,2,2,4] 이렇게 n개의 포켓몬?에 대해 포켓몬종 번호가 주어짐, 이중 n/2(n은 늘 짝수)개를 뽑는데, 가능한 다양한 종을 뽑을 때, 최대로 뽑을 수 있는 종의 수를 구하는 문제 접근방법- 포켓몬종 : 수 - 형식의 map을 만든다.- 그러면 최소 1개는 있는 종들로 map이 만들어짐 (즉, 없는 종은 아예 맵에 데이터가 만들어지지 않음) = map의 크기가 최대로 뽑을 수 있는 종의 수- 이 존재하는 최.. 공감수 0 댓글수 0 2024. 10. 31.
[프로그래머스] 순위 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr그래프 Graph경기결과(a승 b패)가 주어지면, 정확한 순위를 알 수 있는 선수의 수를 반환하는 문제 접근방법첨에 진짜 막막했는데, 선수들의 경기를 간선으로 그래프를 이어보면 본인의 부모노드갯수(본인보다 점수가 높은) + 자식노드갯수(본인보다 점수가 낮은) 값이 총 선수의 수 n - 1(본인) 과 같으면 본인의 순위가 분명한 경우인 것을 고려해서 풀 수 있는 문제다. 인접행렬 두개를 만들어서, 하나는 각 노드의 부모노드를 저장하는 2차원 배열,.. 공감수 1 댓글수 0 2024. 10. 31.
[프로그래머스] 더 맵게 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krHeap 힙 (우선순위 큐)n개의 음식의 스코빌지수가 배열로 주어지고, 이 음식들의 최소 스코빌 지수가 K이상이 되도록 음식을 섞을 수 있다고 할 때, 최소 몇번 섞어야 하는지 반환하는 문제. (모든 음식을 섞어도 스코빌지수가 K를 넘지 않는다면 -1을 반환)음식을 섞는 다는 것은, 섞인 음식의 스코빌 지수 = 최저스코빌지수 음식의 스코빌 지수 + 두번째로 스코빌지수가 최저인 음식의 스코빌 지수*2 이다. 접근방법 갱신되는 음식들의 스코빌지수를.. 공감수 0 댓글수 0 2024. 10. 31.
[프로그래머스] 가장 먼 노드 (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부터 해당 노드까지 도달하는 최단 경로를 구하고, 그 중 가장 먼 거리에 있는 노드는 몇개인지 묻는 문제.즉, (ㅇㄴ) 최단 경로 중에 최댓값을 뽑고, 이 최댓값이랑 거.. 공감수 3 댓글수 3 2024. 10. 31.
[프로그래머스] 정수 삼각형 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krDP 동적계획법 이런 정수 삼각형이 2차원 벡터 배열로 주어지고, 대각선 왼쪽 한칸 혹은 오른쪽 한칸으로만 이동하면서 내려갈 수 있다고 할 때, 거치는 수들의 합이 최대값을 반환하는 문제. 접근방법2차원 배열을 똑같은걸 하나 복사해두고, 이걸 각 위치까지 오는데 거친 수들의 합의 최댓값을 저장해두는 용도로 사용한다. (accTri) = 최대누적트리라고 하겠다.그리고 맨위에서 부터 맨 마지막 바로 전 줄까지 보면서, 내가 갈 수 있는.. 공감수 0 댓글수 0 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) 적은 비용으로 가는 것.그래서 이미 방문한 섬으로부터 갈 수 있는 섬들 중, 가장 .. 공감수 1 댓글수 0 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 재귀 방식으로 풀었는데, 종료조건을 어떻게 두어야 할지 고민했다. 그래서 처음에는 모든 던전을 실제로 들어갔거나, 더이상 들어갈 수 있.. 공감수 0 댓글수 0 2024. 10. 28.
[백준 1916] 최소비용 구하기 (C++) https://www.acmicpc.net/problem/1916다익스트라도시를 연결하는 단방향 버스 (출발점, 도착점, 비용)이 주어지고임의의 출발점과 도착점이 주어졌을 때, 이 둘을 잇는 최소 비용을 출력하는 문제 접근방법 음수인 비용이 없어서 다익스트라로 풀어도 된다. (벨만포드로 안풀어도 됨)이거 풀다가 내가 다익스트라를 제대로 이해하고 있는게 맞나 의심했음..다시 공부해야 할 것 같다..다익스트라 기본 개념은 임의의 출발점 하나에 대해 모든 노드에 대한 최소 거리를 저장하고 있는 1차원 배열이 하나 있고,방문한 노드를 하나씩 추가해 가면서 이 배열을 갱신하는 방식이다. 이 문제를 풀 때는,- 인접행렬 (각 노드에 대해 연결된 버스 노선을 담고 있는 2차원 배열. ex. 1번: {(2번도시, 비용.. 공감수 0 댓글수 0 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 이하이다 = 못올라가는.. 공감수 2 댓글수 0 2024. 10. 22.
[백준 1700] 멀티탭 스케쥴링 (C++) https://www.acmicpc.net/problem/1700그리디 Greedy멀티탭 구의 개수랑 전기용품 사용 순서가 주어지면 플러그를 뺐다 꽂는 횟수의 최솟값을 출력하는 문제 접근 방법우선 꽂혀있는지 확인 (isOn 배열 사용 - 기기별 꽂혀있는지 여부 저장), 멀티탭에 여유공간이 있는지 확인(멀티탭 여유공간 count)꽂혀있지도 않고, 멀티탭이 모두 사용중인 경우에 대해,1. 뽑을 기기 번호 (target), 지금 사용 순서와 꽂혀있는 기기의 사용 순서 사이의 거리 (distance) 초기화2. 꽂혀있는 기기에 대해서 하나씩 스케쥴상의 거리 계산2-1. 이때 이미 등장했던 기기가 또 나올 수 있기 때문에, 기기가 처음 등장하는 순서와의 거리만 계산해야 하기 때문에, existLater라는 변수를.. 공감수 1 댓글수 0 2024. 10. 22.
[프로그래머스] 프로세스 (Swift) https://school.programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 스택/큐 (Queue)N개의 프로세스에 대해 우선순위를 나타낸 배열이 하나 주어지고처음부터 프로세스를 보면서 우선순위가 더 높은 게 뒤에 있을 경우 큐의 맨 뒤로 보내는 식으로프로세스를 실행할 때, 특정 프로세스의 위치(인덱스)를 입력받아 해당 프로세스가 몇번째로 실행되는지 반환하라는 문제 접근방법스위프트는 Queue가 collection에 없기 때문에 array를 사용해서 dequeue은 remo.. 공감수 0 댓글수 0 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에 비해서는 커질 수 .. 공감수 0 댓글수 0 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.. 공감수 2 댓글수 0 2024. 10. 15.
[백준 14719] 빗물 (C++) https://www.acmicpc.net/problem/14719 문제각 열의 기둥 높이가 주어지고 그 사이에 채워지는 칸의 수를 출력하는 문제 접근 방법이게 맞는 방법인진 모르겠지만 W가 최대 500이어서 왔다갔다 두번하는 식으로 했다.처음에는 왼쪽에서 오른쪽으로 가면서 지금까지 가장 높았던 기둥(curMax)의 높이와 인덱스를 저장한다.그러면서 현재 보고 있는 기둥이 curMax 기둥보다 낮을 경우 -> curMax - 현재 기둥 높이 를 tmp에 더한다.이때 tmp는 임시로 고인 빗물의 양이다.그리고, 현재 보고 있는 기둥이 curMax 기둥보다 같거나 높을 경우 -> 지금까지의 고인 물이 고이는 것이 확정되므로tmp 값을 result 에 더해주고 tmp를 0으로 초기화한다. 문제는 tmp에 임시.. 공감수 0 댓글수 0 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를 곱한다. 이제 앞으로 나오는 계산에는.. 공감수 0 댓글수 0 2024. 8. 1.
[백준 1987] 알파벳 (C++) https://www.acmicpc.net/problem/1987DFS알파벳으로 구성된 보드판에서 좌측상단부터 시작해서 중복되지 않은 칸을 지나면서 상하좌우로 이동할 수 있다.이때 최대 몇칸까지 지날 수 있는지 구하는 문제 접근 방법상하좌우 이동하는 경우들로 DFS로 풀었다. 오답노트처음에 지나온 알파벳들을 기억하려고 벡터에 지나온 문자들을 담아두고 찾는 식으로 했다가 시간초과나서알파벳 개수 (26)만큼 boolean 배열에 방문 여부 체크하면서 가는걸로 고쳤다. 아 그리고 visit 배열 처음에 0으로 초기화 안해줬더니 랜덤값 들어가던데 (아니 그냥 Int 배열은 다 0 들어가더만) 근데 왜 DFS함수 시작할 때 방문하는걸로 하면 왜 안될까유그러면 visit배열을 다시 false로 바꿔주지 않아도 되는.. 공감수 0 댓글수 0 2024. 7. 9.
[백준 9935] 문자열 폭발 (C++) https://www.acmicpc.net/problem/9935 평범한 문자열1개와 폭발 문자열1개를 입력받고, 평범한 문자열에서 폭발 문자열은 모두 사라지게 한 결과를 출력하는 문제폭발문자열이 사라짐으로 인해 합쳐진 문자열이 또다시 폭발 문자열을 포함한다면 그것도 폭발시켜야함! 접근방법Swift String의 range와 replacesubrange를 사용해보았는데 대차게 시간초과 떠서,,얌전히 C++로 풀었다네요ㅋㅋ,,Stack문제는 Stack으로..접근방법을 한마디로 요약하면 "Stack에 문자를 하나 넣을 때 마다 폭발물을 검사하자"입니다.평범한 문자열을 모두 순회하면서 한글자씩 Stack에 넣을 건데요, 이때 한글자가 들어갈 때마다폭발물 문자열 길이 만큼 스택 상단의 문자열을 뽑아서 폭발물인지.. 공감수 0 댓글수 0 2024. 7. 3.
[백준 9184] 신나는 함수 실행 (C++) https://www.acmicpc.net/problem/9184if a 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)if a 이 문제는 -50~50 범위의 정수인 a,b,c가 주어지면 w(a,b,c)를 구해서 출력하는 문제다. 접근방법입력받는대로 계산할 수도 있지만 그러면 재귀함수를 너무 많이 호출하게 돼서 시간복잡도가 커지는 문제 -> 그래서 DP로 풀어야 하는데이번에도 다 저장해두고 사용하는 방법으로 풀었다. 그래도 계산하는 횟수가 101*101*101 정도라 시간초과가 안나는 것 같다.3차원 배열 arr[a][b][c]에 3중 반복문을 돌면서 차례차례 값을 저장한다. 숫자 하나라도 0 이하면 함숫값이 1이기 때문에 차곡차곡 .. 공감수 0 댓글수 0 2024. 7. 2.
[백준 11660] 구간 합 구하기 5 (C++) https://www.acmicpc.net/problem/11660 DP 동적계획법이런 표에서 주황색 점 위치(시작점)와 파란색 점 위치(끝점)가 주어지면, 빨간테두리의 박스에 속한 숫자들의 합을 구하는 문제근데 이제 빨간 박스가 M개 주어지고 M이 100,000까지 될 수 있고, NxN에서 N은 1024까지 될 수 있는.. 접근 방법처음에 엥 표 저장해두고 [r1][c1] ~ [r2][c2] 까지 다 더하면 되는거 아닌가? 했지만 실버1인걸 보고 DP로 풀었음..이전에 내가 생각해온 DP는 미리 구해놓고 쓰기 였는데 예를들면 한 행에서 각 원소의 값을 그 원소까지의 합으로 치환한다.위의 표에서 첫번째 행을 예로들면, 1 2 3 4 -> 1 3(1+2) 6(1+2+3) 10(1+2+3+4).이때 치환할.. 공감수 0 댓글수 0 2024. 6. 24.
[백준 15664] N과 M (9) (C++) https://www.acmicpc.net/problem/15663 백트래킹N과 M (5)와 비슷하게 N개의 자연수 중에 M개를 뽑아 만들 수 있는 수열을 모두 사전순으로 출력하는 문제인데차이점은 N개의 자연수가 중복가능임그래도 N개의 숫자 중에 M개를 뽑아야 하는 것을 변함이 없어서그냥 중복된 숫자가 있는 숫자 카드가 N개 있고, 그 중 M개를 뽑아서 나열한 수열을 중복되지 않게, 사전순으로 출력하믄댐! 접근방법N과 M(5) 코드에서 수열을 담고 있는 배열을 vector가 아닌 set으로 바꿔주면 됨~setvectorint>, lessvectorint>>> 이렇게 선언하면 사전순으로 수열이 정렬되어서 set에 들어감 오답노트set에서 vector 정렬 안될 줄 알고 string으로 넣었다가 9, 10 .. 공감수 0 댓글수 0 2024. 6. 22.
[백준 15654] N과 M (5) (C++) https://www.acmicpc.net/problem/15654 백트래킹N개의 서로 다른 정수가 주어지고, 그 중에 M개를 뽑아서 만들 수 있는 가능한 수열을 사전순으로 모두 출력하는 문제 접근 방법백트래킹으로 재귀함수 써서 풀었다.재귀함수 파라미터로는 n, m, 수열을 담고 있는 배열(candidate), n개의 숫자의 방문여부를 담고 있는 배열을 갖고 다녔음입력받은 n개의 숫자를 num array에 넣어두고(sort해줌 - 사전순으로 출력하려고), 수열의 첫째자리 부터 담아가면서 방문여부 체크하고재귀함수 호출하기 반복그러다가 수열이 m자리가 되면 결과 배열에 넣고 재귀함수를 종료함 코드를 좀..지저분하게 쓴 것 같긴한데..차차 나아지겠죠머 오답노트아 근데 C++ 백준에서 돌릴 때 vector.si.. 공감수 0 댓글수 0 2024. 6. 22.
[백준 18406] 럭키 스트레이트 (C++, Swift) https://www.acmicpc.net/problem/18406 구현, 문자열머선 문제냐 하면123402 라는 문자열이 주어지면, 반갈죽!해서 양쪽 자릿수 합이 같은지 확인하는 문제임같으면 LUCKY 출력, 다르면 READY 출력*문자열은 늘 짝수자릿수 (즉 12345 같은 5자릿수 안들어옴) 1234021+2+3 = 6, 4+0+2 = 6 이니 이건 LUCKY 접근방법C++for 문을 두개 써서 front, back 변수에 각각 앞부분의 합과 뒷부분의 합을 저장하고 둘을 비교함swift배열하나 두고, prefix, suffix로 배열 쪼개서 reduce로 합 구해서 바로 비교하고 출력 (고차함수 쓰고 싶어서 swift로도 풀었는데, string -> int 배열 만들려다가 고군분투함..) 오답노트-.. 공감수 0 댓글수 0 2024. 6. 20.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.