본문 바로가기
728x90
반응형

알고리즘 (C++)19

[백준]11501번: 주식 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 주어진 예시에서 주가가 10 7 6이면 최대 이익이 0이고 주가가 1 1 3 1 2 면 최대 이익이 5다. 접근 방법은 다음과 같다. 1) 배열에 주가를 담아놓는다. ex) 1 1 3 1 2 2) 최대 주가(maxStock)와 최종 이익(totalProfit) 변수를 선언한다. maxStock은 가장 큰 주가를 의미하며 totalProfit은 최대 이익을 의미한다. 3-1) maxSt.. 2023. 11. 27.
[백준]11652번: 카드 https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 문제를 보면 가장 중복이 많은 수를 뽑는게 핵심이다. 접근 아이디어는 다음과 같다. 1. 우선 카드 배열에 정수를 다 입력 받는다. 2. 오름차순으로 정렬한다. 3. 현재 중복된 카드 횟수를 저장할 변수 (dupliCnt)와 지금까지 가장 많이 중복된 카드 횟수를 저장할 변수 (maxDupliCnt)를 선언한다. 4. for문을 돌면서 카드가 중복되면 dupliCnt를 증가시키고 이 값이 m.. 2023. 11. 24.
[백준]15900번: 나무 탈출 https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 문제를 간단하게 요약하면 다음과 같다. - 1은 루트 노드다. - 초기 모든 리프 노드에만 말이 있다. - 말이 루트 노드(1)에 도착하면 제거한다. - 게임은 성원이가 먼저 시작하며 우리가 원하는건 성원이가 이기면 "Yes"를 지면 "No"를 출력하는 것이다. 접근 아이디어 - 몇 개의 트리를 그리고 시뮬레이션 해보면 다음과 같은 규칙을 발견할 수 있다. - 루트노드에서 모든 리프 노드까지의 d.. 2023. 11. 23.
[백준]16948번: 데스 나이트 https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net BFS()를 통해 해결한다. 처음 이런 문제를 해결할 때 항상 2개의 2차원 배열을 만들어 방문을 체크하는 배열과 현재 지점까지의 움직인 횟수를 저장하는 배열을 만들어 사용했다. 조금만 더 최적화를 생각하다보니 2차원 배열 하나를 -1로 초기화 해두 시작하면 될 것으로 생각하여 코드를 작성했다. 1) 초기 map의 모든.. 2023. 11. 23.
[백준] 10867번: 중복 빼고 정렬하기 https://www.acmicpc.net/problem/10867 10867번: 중복 빼고 정렬하기 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. www.acmicpc.net 오늘 문제는 정렬 알고리즘을 이용한 풀이입니다. 사실 for문을 돌면서 중복 체크를 해도 되지만... C++의 강력한 STL을 적재적소 해야겠죠? set을 이용해 중복을 방지하며 기본적으로 오름차순으로 정렬 받습니다! (만약 오름차순을 명시하고 싶다면 set s; 형태로 명시하면 됩니다.) 여기서 중요한 점은 set의 출력인데 Iterator 형태로 출력해야 합니다. #include #include #include #defin.. 2023. 11. 21.
[백준] 15886번: 내 선물을 받아줘 2 요즘... 생각이 많아 잠시 휴식 타임을ㅠㅠ 여튼 지금부터 다시 힘내보려 합니다! https://www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직 www.acmicpc.net 이 문제를 처음 접했을 때 무슨 소리인지 이해하는데 한참 걸렸다. 구사과의 위치를 모르지 이동을 시작하는 위치와 관계없이 선물을 줘야한다. 문제에서 이동은 E와 W인 경우에 이동한다. 그렇다면 결론은 E에서 W로 바뀌는 즉 이동이 바뀌는 순간 E에 선물을 놓는다면 구사과를 무조건 얻을 수 밖에 없다. 이.. 2023. 11. 20.
728x90
반응형

티스토리툴바