목록DFS (9)

슈뢰딩거의 고등어

[프로그래머스] DFS 여행경로 (C++ / Python3)

https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr [풀이방법] c++/ python 둘다 같은 로직으로 풀었습니다. 1. 주어진 tickets 을 알파벳 순으로 정렬한다. 2. 첫 시작공항인 ICN을 start 로 설정한 후 dfs 탐색을 시작한다. 3. start를 첫번째 인자로 하는 티켓을 탐색한다. 4. 해당 티켓의 두번째인자는 목적지이므로 두번째 인자를 start 로 설..
알고리즘 2022. 7. 2. 17:58
[2019 카카오 개발자 겨울 인턴십] 불량 사용자 (lv3)

https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr [풀이 방법] 이 문제는 중복을 허용하지 않는 조합에 관한 문제이다. 1. 질문을 하나씩 돌면서 체크가 안되어있고 질문과 일치하는 단어를 체크한다. 2. 모든 문제를 다 돌았다면 체크된 단어들을 저장한다. 3. 모든 경우를 다 체크했다면 저장된 결과들을 중복 제거한다. 4. 중복제거해서 남은 결과의 갯수가 answer 이다. #include #include #i..
알고리즘 2022. 4. 17. 15:04
[2021 카카오 채용연계형 인턴십] 거리두기 확인하기 (lv2)

https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr [풀이] 1. 사람이 앉아 있는 위치를 선택 탐색한다. 2. 상하좌우로 움직이면서 벽이 없..
알고리즘 2022. 4. 5. 19:38
[2021 Kakao blind recruitment] 메뉴 리뉴얼

https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr DFS 로 풀 수 있다.. 초기에 바로 DFS를 떠올리지 못해서 삽질을 했다. [풀이방법] 1. order 가 "abcfg" 라고 하고 course 가 2 일 경우, abcfg 에서 2개를 선택하는 조합을 구한다. (dfs) ab, ac, af, ag ... 이거 하기전에 order 를 알파벳기준으로 정렬해주는 것도 필요하다. 2. 구한 경우들을 map 에 업데이..
알고리즘 2022. 3. 23. 18:05
[2022 Kakao blind recruitment] 양궁대회

https://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr [초기코드] 더보기 틀렸던 원인 : 라이언이 어피치를 이겼을 때 가질 수 있는 최대 점수를 구하려고 했다. 하지만 문제를 잘 읽어보니 최대 점수가 아닌 어피치를 이길경우의 어피치점수와의 최대 격차를 구하는 문제였다. 또한, 같은 격차로 이기는 케이스가 여러개일 경우, 더 낮은 점수를 많이 맞추는 경우를 리턴했어야 했는데 이 부분 로직이 잘못되었었다. #include ..
알고리즘 2022. 3. 22. 21:29
[백준] 1107 리모컨

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net [처음 틀린 풀이방법] 1. 각 자리수를 비교하면서 가장 작은 차인 원소를 선택한다. 2. 모든 자리수를 선택한 후 비교한다. 차이만큼 버튼 클릭수에 + 해준다. ex) 타켓넘버 5457 이고 사용가능한 숫자버튼이 0, 1, 2, 3, 4, 5, 9 일 경우 첫째자리 5 와 가장 차이가 작은 원소인 5 선택 두번째자리까지 54 와 가장 차이가 작은 원소인 4 선택 세번째 자리까지 ..
알고리즘 2022. 3. 20. 18:30
DFS (순열, 조합)

조합 조합은 전의 요소는 다시는 쳐다도 안본다는 것이 중요 #include #include using namespace std; // 조합 // 123 != 213 int Arr[10] = {0,1,2,3,4,5,6,7,8,9}; bool Select[10]; void DFS(int Idx, int Cnt, int target_num) { if (Cnt == target_num) { for (int i=0; i
알고리즘 2022. 2. 8. 10:43
[백준] 17085 십자가 2개 놓기

https://www.acmicpc.net/problem/17085 17085번: 십자가 2개 놓기 첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 1. dfs 로 가능한 위치 2개를 뽑는다. 2. 맵을 카피한다. 3. 첫번째 위치에서 구할 수 있는 최대 길이를 구한다. 4. 첫번째 위치에서 넓이를 하나씩 넓혀가면서 두번째 위치에서 만들 수 있는 최대의 십자가의 넓이를 구한다. 5. 4. 의 과정을 거치면서 첫번째 넓이 * 두번째 넓이를 answer 값과 비교하여 answer 보다 크면 update 해준다. 처음에 실패한 이유는 십자가..
알고리즘 2022. 1. 27. 13:47
이전 Prev 1 2 Next 다음