[프로그래머스] 등산코스 정하기 - Python
2023. 6. 30. 01:10
Algorithm/프로그래머스
🤔 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 😀 풀이 해당 문제는 최단 경로 문제의 변형으로 최단 경로문제가 익숙하시다면 다익스트라 알고리즘을 떠올리기까지는 비교적 쉬울 것 같습니다. 다만 저처럼 아무생각 안하고 다익스트라를 적용하게되면 시간초과를 맞게됩니다..ㅠ 처음 생각했던 풀이는 모든 출입구에 대하여 (출입구 -> 산봉우리 -> 출입구)의 최단경로를 구하는 방식을 사용했는데 이렇게 되면 N번의 다익스트라를 수행해야해서 시간초과가 나게되죠. 문제를 다시 천천히 읽어보니 2가지 포인트를 찾을 수 있었습니다. 첫 번째는 (출입구 -> 산봉우리)..
[프로그래머스] 길 찾기 게임 - Python
2023. 3. 1. 05:12
Algorithm/프로그래머스
🤔 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 😀 풀이 위 문제는 BST를 구현해본 경험이 있다면 쉽게 풀이할 수 있는 문제입니다. 전체적인 풀이 방향이 BST의 insert, 전위 순회, 후위 순회를 구현하는 문제이기 때문에 이에 대한 내용을 중점적으로 설명해보도록 하겠습니다. 먼저 문제에서 y축의 크기가 클수록 BST 상단에 위치해야하므로 아래 코드와 같이 문제에서 주어진 nodeinfo를 정렬해줍니다. 이때 노드의 y값을 기준으로 정렬합니다. y값을 기준으로 정렬하게 되면 순서대로 노드들을 확인했을 때 부모 노드부터 트리에 삽입할 수 있게 ..
[BOJ] 2143 두 배열의 합 - Java
2022. 7. 19. 17:03
Algorithm/백준
🤔 문제 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 😀 풀이 본 문제는 백준에 표기된 알고리즘 분류와 다르게 Map 자료구조를 사용하여 풀이했습니다. 문제에서 원하는 바는 주어진 두 배열의 부분합의 합이 문제에서 주어진 값(T)과 같아지는 경우가 몇 가지인지를 구하는 것 입니다. 문제에서 주어진 입력의 크기가 1,000 임을 고려해보았을 때 브루트 포스로 풀이하게 되면 시간초과가 날 것이라 판단하여 아래와 같은 풀이를 사용했..
[BOJ] 14500 테트로미노 - Java
2022. 6. 11. 13:58
Algorithm/백준
🤔 문제 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 😀 풀이 위 문제는 적절한 구현과 완전 탐색을 하여 풀이하였습니다. 주어진 종이 정보에 도형 5가지를 각각 놓아보아야 하는데 이 때 각 도형을 회전, 대칭시켜서 놓아보는 작업 역시 해봐야 합니다. 저의 풀이에서는 편의를 위해 도형을 회전하는 과정은 종이 정보를 회전하는 방식을 사용해 풀이했습니다. 풀이 과정을 간략하게 요약하면 아래와 같습니다. 종이의 모든 점에 도형을 하나씩 놓아본다. 점수를 계산한다. 1번 과정에서 도형을 회전하고 대칭해보는 과정을 포..
[LeetCode] 33. Search in Rotated Sorted Array - Python
2022. 5. 5. 17:53
Algorithm/LeetCode
🤔 문제 Search in Rotated Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 😀 풀이 해당 문제는 이진 탐색을 조금 더 응용하여 풀이할 수 있는 문제입니다. 특정 인덱스를 기준으로 rotate 되어 기존 방식으로 이진 탐색을 하는 것이 불가능하여 한 단계 더 과정을 거쳐야 문제 조건에 맞게 풀이할 수 있습니다. 가장 처음 생각한 방법은 다음과 같습니다. rotate가 몇 번 되었는지 확인한다. 즉, 배열에서 가장 작은 값의 ..
[BOJ] 9663 N-Queen - Python
2022. 5. 4. 05:01
Algorithm/백준
🤔 문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 😀 풀이 위 문제는 백트래킹으로 유명한 N-Queen 문제입니다. 처음에는 해당 문제를 2차원 배열을 사용하여 퀸들의 위치 정보를 담아 풀이를 하려했는데 구글링 도중 1차원 배열을 사용해 푸는 좋은 방법이 있어 해당 부분을 차용해보았습니다. 자세한 내용은 아래와 같습니다. rows라는 1차원 배열을 가지고 퀸들의 정보를 담습니다. 만약 rows[i] = j 라는 값을 가진다면 이는 i 행의 j 열에 퀸이 놓여져있다라는 의미가 됩니다. 또한 문제 풀이 과정에서 두 가지 ..
[LeetCode] 42. Trapping Rain Water - Python
2022. 4. 27. 15:13
Algorithm/LeetCode
🤔 문제 Trapping Rain Water - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 😀 풀이 해당 문제는 벽 높이 정보를 가지고 있는 배열을 이용하여 비가 온 뒤 벽 사이에 고인 빗물 양을 계산하는 문제입니다. 각 위치마다 고일 빗물의 양을 계산하는 과정을 통해 문제 풀이를 진행했는데 이 때 고려해야 할 것은 다음과 같습니다. # 현재 위치 기준으로.. 좌측에 있는 벽들 중 최대 높이 우측에 있는 벽들 중 최대 높이 위 두 가지를 안다면 두 가지 중 ..
[LeetCode] 49. Group Anagrams - Python
2022. 4. 26. 01:10
Algorithm/LeetCode
🤔 문제 Group Anagrams - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 😀 풀이 위 문제는 주어진 문자열 배열들을 anagram 끼리 모아보는 문제입니다. 문제 풀이에서 핵심이 된 아이디어는 "anagram이라면 문자열을 정렬했을 경우 같은 값이 나온다" 입니다. 따라서 풀이를 진행한 흐름은 아래와 같습니다. 문자열 배열을 하나씩 살펴보는 과정에서 각 문자열을 정렬해본다. 정렬한 뒤 dict에 문자열을 넣는다. 이 때 key는 정렬된 문자열, va..
[프로그래머스] 조이스틱 - Python
2022. 4. 4. 04:20
Algorithm/프로그래머스
🤔 문제 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 😀 풀이 해당 문제는 프로그래머스의 그리디 유형으로 올라온 문제인데.. 테스트 케이스 추가 전에는 정답 처리가 되었다가 다시 채점해보니 틀렸다고 나와 재풀이한 문제입니다. 그리디로 풀었던 방법은 현재 위치를 기준으로 'A'가 아닌 곳 중 가장 짧은 곳으로 가서 변경하고 이를 반복하는 작업을 했습니다. 그런데 이런식으로 풀면 반례가 생깁니다...! 대표적으로 "BBBBAAAABA" 가 있습니다. 그리디 방식을 사용할 경우 아래와 같이 ..
[프로그래머스] 양과 늑대 - Python
2022. 3. 4. 22:45
Algorithm/프로그래머스
🤔 문제 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 😀 풀이 해당 문제는 DFS를 사용하여 풀이했습니다. 우선 문제 풀이를 위해 아래 두 가지 기능이 필요하다고 생각하여 함수 두 개를 작성했습니다. 현재 노드에서 어떤 노드를 가볼 수 있는지 체크하는 함수(getCanGoEdges) 가볼 수 있는 노드에 가보며 양과 늑대의 개수를 갱신하는 함수(DFS) # ..