전체 글247 [백준 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. [백준 1987] 알파벳 (C++) https://www.acmicpc.net/problem/1987DFS알파벳으로 구성된 보드판에서 좌측상단부터 시작해서 중복되지 않은 칸을 지나면서 상하좌우로 이동할 수 있다.이때 최대 몇칸까지 지날 수 있는지 구하는 문제 접근 방법상하좌우 이동하는 경우들로 DFS로 풀었다. 오답노트처음에 지나온 알파벳들을 기억하려고 벡터에 지나온 문자들을 담아두고 찾는 식으로 했다가 시간초과나서알파벳 개수 (26)만큼 boolean 배열에 방문 여부 체크하면서 가는걸로 고쳤다. 아 그리고 visit 배열 처음에 0으로 초기화 안해줬더니 랜덤값 들어가던데 (아니 그냥 Int 배열은 다 0 들어가더만) 근데 왜 DFS함수 시작할 때 방문하는걸로 하면 왜 안될까유그러면 visit배열을 다시 false로 바꿔주지 않아도 되는.. 2024. 7. 9. [백준 9935] 문자열 폭발 (C++) https://www.acmicpc.net/problem/9935 평범한 문자열1개와 폭발 문자열1개를 입력받고, 평범한 문자열에서 폭발 문자열은 모두 사라지게 한 결과를 출력하는 문제폭발문자열이 사라짐으로 인해 합쳐진 문자열이 또다시 폭발 문자열을 포함한다면 그것도 폭발시켜야함! 접근방법Swift String의 range와 replacesubrange를 사용해보았는데 대차게 시간초과 떠서,,얌전히 C++로 풀었다네요ㅋㅋ,,Stack문제는 Stack으로..접근방법을 한마디로 요약하면 "Stack에 문자를 하나 넣을 때 마다 폭발물을 검사하자"입니다.평범한 문자열을 모두 순회하면서 한글자씩 Stack에 넣을 건데요, 이때 한글자가 들어갈 때마다폭발물 문자열 길이 만큼 스택 상단의 문자열을 뽑아서 폭발물인지.. 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이기 때문에 차곡차곡 .. 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).이때 치환할.. 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 .. 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.. 2024. 6. 22. 이전 1 2 3 4 5 6 ··· 21 다음
