CS/Algorithm6 프로그래머스 - (PCCP 모의고사) 보물 지도 c++ https://school.programmers.co.kr/learn/courses/15009/lessons/121690 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr bfs를 약간 변형한 문제로, 이동시 신비로운 신발을 사용하여 두칸을 한번에 이동할 수 있다. 방문여부를 확인할 배열을 2차원 배열이 아닌 3차원 배열을 사용하여 방문여부를 확인한다. visited[1001][1001][2] ex) (2,3)을 지날 때 신비로운 신발을 사용 했으면 visited[2][3][1] = true; (2,3)을 지날 때 신비로운 신발을 사용 안했으면 visited.. 2023. 5. 19. 프로그래머스 - 순위 (c++) https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 보통 그래프 문제가 주어지면 양방향 그래프로 주어지는 경우가 많은데, 이 문제는 단방향 그래프이다. A가 B를 이겼다는 경우가 주어지면 'A -> B' 이렇게 노드를 저장한다. 또, 이 문제에는 '플로이드-와샬' 이라는 최단거리 알고리즘이 사용된다. (다익스트라도 최단 거리 알고리즘!) boolean값을 저장하는 2차원 배열을 만드는데, win[a][b]에 저장되어 있는 값은 a가 b를 이겼으면 .. 2023. 5. 17. 프로그래머스 - 전력망을 둘로 나누기 (c++) https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 완전탐색 카테고리에 있는 레벨2 문제 입력으로는 하나의 네트워크로 뭉쳐있는 트리가 주어지고 전선을 한개씩 자르면서 네트워크가 두 개로 나누어지고 네트워크간 송전탑 개수의 차이가 최소로 하는 값을 구하면 된다. 결론적으로 나는 완전탐색 + 크루스칼 을 사용해서 풀었다. 전선을 하나씩 자르면서 생기는 네트워크가 몇개인지 파악하고 각 송전탑이 어떤 네트워크에 속하고 있는지 알기 위해 크루스칼을 사용했.. 2023. 5. 16. 백준 - 최소 환승 경로(2021번) c++ https://www.acmicpc.net/problem/2021 2021번: 최소 환승 경로 첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발 www.acmicpc.net 출발역에서 도착역까지 환승 최소 횟수를 구하는 문제 뭔가 bfs 또는 dfs를 사용하면 뚝딱 풀릴듯 말듯.. 아이디어를 떠오르기가 쉽지 않았다. 결국 답을 구해야 하는것은 환승 최소 횟수이므로 각 역을 기준으로 탐색을 하는 것이 아닌 노선을 기준으로 탐색을 해보기로 했다. 입력이 다음과 같을때 10 3 1 2 3 4 5 -1 9 7 10 -1 7 6 3 8 -1 1 .. 2023. 4. 11. 삼성 SW 역량 테스트 - 시험 감독 (c++) https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 이 문제에서 가장 중요한 조건은 '각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.' 이다. 언뜻 보면 총감독관은 없어도 된다는 말 같지만 '각각의 시험장에는 총감독관은 무조건 1명이 있어야 한다' 로 해석해야 문제를 풀 수 있다. 첫 번째 반복문에서 (각 교실의 학생수 - 총감독관이 감독할 수 있는 학.. 2023. 3. 21. 프로그래머스 레벨3 - 숫자 게임 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/12987 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제에서 가장 중요한 조건은 1. 각 사원은 딱 한 번씩 경기를 합니다. 2. A팀은 빠르게 출전순서를 정했다. 요 두개의 조건 이다. A팀의 출전순서가 이미 정해져 있는 상태이므로 백터A와 벡터B를 각각 정렬하여 비교 할 수 있다. 정렬이 왜 가능하지? -> 벡터A를 정렬했다고 해서 A팀의 출전순서가 바뀌는 것은 아니다. 단순히 벡터B와의 비교를 위해 각 사원의 자연수만을 정렬한 것이다. '.. 2023. 3. 16. 이전 1 다음
