본문 바로가기

알고리즘 문제풀이200

[백준 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.
[백준 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 배열 만들려다가 고군분투함..) 오답노트-.. 2024. 6. 20.
[백준 1439] 뒤집기 (C++) https://www.acmicpc.net/problem/1439 그리디, 문자열S=001100 이런 이진수로 구성된 문자열이 주어지고, 연속하는 같은 숫자는 한꺼번에 뒤집을 수 있음이때 모든 문자를 같은 문자로 만드려면 최소 몇번 뒤집어야할까! 가 문제임 접근방법1. 0과 1 각각 묶음의 갯수를 구함2. 둘 중 최소를 출력함 (단, 둘 중 하나가 0인 경우 = 원래도 모두 같은 문자로 구성된 문자열이었다는 거 -> 0 출력)끄읕~ 오답노트- C++에서 string.size()가 unsigned int 인가 그래서 바로 for문 조건에 넣어버리면 오류나서 한번 변수로 담아줘야함..(원래 이랬나..)- cur(현재 연속하고 있던 문자)를 안바꿔줘서 틀렸었음~앗차차- cout 안에 삼항연산자 안들어가고 밖에.. 2024. 6. 20.
[백준 3190] 뱀 (C++) https://www.acmicpc.net/problem/3190 구현그 snake 게임? 생각하면 될 듯N * N 보드에서 길이 1짜리 뱀으로 시작해서 한칸씩 늘리면서 이동하면서도처에 위치한 사과들을 먹으면 길이가 +1 되고, 못 먹으면 길이가 유지되는 (그래서 꼬리가 이동함 - 사라짐)입력으로는 사과의 위치와 S초후에 바뀌는 방향이 주어진다.-> 머리의 방향을 바꿔가면서 한칸씩 이동하는 스네이크 게임~종료 조건: 벽에 닿거나, 본인과 본인의 머리가 부딪힐 경우 접근방법구현문제여서 시뮬레이션으로 풀었다.- 정사각보드 구성: 2차원배열로 격자판을 만들어 놓고, 빈칸은 0, 뱀은 1, 사과는 2로 설정했다.- 뱀의 이동 방향: 오른쪽, 아래, 왼쪽, 위 순서대로 방향 배열 선언해둠 (dr, dc), 왼쪽으.. 2024. 6. 20.
[백준 1620] 나는야 포켓몬 마스터 이다솜! (Swift) https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 제목부터 킹받는 문제다 지하철에서 문제를 열심히 읽었는데 본문 전체가 문제 푸는데에는 영향을 주지 않는 빌드업이었다 ^_^ 문제를 읽기 전에 이 블로그를 먼저 보는 사람은 없겠지만 혹시 운 좋은 어떤 사람이 문제도 보기 전에 이 블로그를 먼저 봤다면 문제 설명 부분에서 오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가.. 2022. 6. 12.
[프로그래머스] 이중우선순위큐(C++) https://programmers.co.kr/learn/courses/30/lessons/42628?language=cpp 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr Heap 큐에 입력받은 숫자를 넣는 명령, 최댓값을 빼는 명령, 최솟값을 빼는 명령 들을 수행한 후에 큐에 남아있는 최댓값과 최솟값을 차례로 출력하는 문제 접근 방법 최대힙과 최소힙을 둘 다 사용해서 풀어야 하는 문제이다. 여기까지는 알겠는데 최대힙에서 top을 제거할 때 최소힙에 남아있는 수는 어떻게 하나..가 문제였다. (반대의 경우도 마찬가지) 손으로 여러번 시뮬레이션 해본 결과 최종적으로 최대힙의 top이 이미 최소힙에서 제거된 원소라면 큐에 남아있는 원소가 없음을 의미한다.는 것을 깨달았다. 따라서 실제로 .. 2022. 4. 30.
[프로그래머스] 디스크 컨트롤러 (Swift) https://programmers.co.kr/learn/courses/30/lessons/42627#qna 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr heap 이지만 정렬로만 풀은 문제.. 시뮬레이션이라고 하는게 더 맞지 않나..싶은 왜 이곳에 heap을 써야하지..싶은..문제였달까 접근 방법 최종 종료 시간을 앞당기는게 문제가 아니라 대기시간+처리시간의 평균을 줄이는게 목적이다. 즉 대기시간을 줄이는게 문제의 목적임 SJF : shortest job first 대로 풀면 될 것 같은 문제이다. .. 2022. 4. 29.
[프로그래머스] 징검다리 (Swift) https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 징검다리~! 각기 다른 간격으로 배치되어 있는 징검다리들 중 n개를 제거했을 때 간격의 최솟값들 중에 가장 큰 값을 반환하는 문제 접근방법 이번에는 이분탐색의 범위까지는 접근했지만 탐색하는 기준을 뭐로 해야할지 모르겠어서 블로그 탐색 후 힌트를 얻었다..ㅎ 모르겠으면 이렇게라도 배워야지..! 이분탐색 범위는 이번에도 역시 결과값의 범위다. 0~간격의.. 2022. 4. 20.

티스토리툴바