분류 전체보기
level1_3진법 뒤집기
문제 https://programmers.co.kr/learn/courses/30/lessons/68935 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr 접근방법 1) 접근 사고 처음에 넣은것을 뒤집어야 하므로 처음부터 뒤집은 상태를 넣어줄려고 큐를 사용해서 구현해 봤습니다. 2) 시간 복잡도 O(n) 3) 실수 없습니다. 4) 배운점 없는거 같네요 5) PS 정답 코드 #include using namespace std; int solution(int n) {..
level1_내적
문제 https://programmers.co.kr/learn/courses/30/lessons/70128 코딩테스트 연습 - 내적 길이가 같은 두 1차원 정수 배열 a, b가 매개변수로 주어집니다. a와 b의 내적을 return 하도록 solution 함수를 완성해주세요. 이때, a와 b의 내적은 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1] 입니다. (n은 a, b의 programmers.co.kr 접근방법 1) 접근 사고 그대로 구현하시면 됩니다 2) 시간 복잡도 O(n) 3) 실수 원큐에 했습니다. 4) 배운점 없는거 같습니다. 5) PS 정답 코드 #include using namespace std; int solution(vector a, vector b) { ..
2019 KAKAO BLIND RECRUITMENT 풀이 모음
1번 https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 접근방법 단순 구현 문제였다. 해시를 활용해서 아이디를 이름에 매칭 시켜서 풀면 쉽게 해결이 된다. 실수 한 큐에 해결했습니다. O_O 정답 코드 #include using namespace std; map db; vector solution(vector record) { vector answer; vector log; for(auto s : record)..
2020 KAKAO BLIND RECRUITMENT 풀이 모음
1번 https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 접근방법 1. 문자열을 탐색하면서 문자열에서 같은 문자가 나오는 지점의 숫자가 몇 번 나오는지 계산하면서 탐색을 진행합니다. 2. 같은 문자가 나오는 경우가 멈출 경우 숫자와 문자를 문자열에 더하고 정답에 값을 넣어줍니다. 3. 이때 사이즈가 1인 경우는 문제의 조건의 따라 예외처리를 진행해줍니다. 실수 1. 문자열 탐색을 진행한 뒤 다음 문자열을 ..
level4_매출하락최소화(2021 KAKAO BLIND RECRUITMENT)
문제 https://programmers.co.kr/learn/courses/30/lessons/72416 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr 접근방법 1) 접근 사고 DFS + DP 문제였습니다. 주석에 자세히 첨부하였습니다. 2) 시간 복잡도 3) 실수 4) PS 하... 정답 코드
level3_카드짝맞추기(2021 KAKAO BLIND RECRUITMENT)
문제 https://programmers.co.kr/learn/courses/30/lessons/72415 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr 접근방법 1) 접근 사고 문제를 정리하면 카드를 뒤집는 모든 순서를 고려해서 카드와 카드 사이의 최단 거리를 구할 경우 전체 최단거리르 구해야 하는 문제였습니다. 백트래킹을 활용하여 카드의 모든 뒤집는 순서를 고려하고 다이젝스트라를 활용하여 최단거리를 구해주면 되는 문제입니다. 2) 시간 복잡도 3) 실수 63번, 64번줄에서 cur값을 더 해주는 실수를 함 ..
level3_광고삽입(2021 KAKAO BLIND RECRUITMENT).cpp
문제 https://programmers.co.kr/learn/courses/30/lessons/72414 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 접근방법 1) 접근 사고 문제를 다 읽고 정리하면 "광고의 누적시간을 구하세요"가 문제에서 제시하는 핵심이다. 처음에 어떻게 구현을 해야할 지 감이 안잡혔다. 완전탐색으로 구현을 하게 되면 범위 때문에 시간초과가 발생할 게 당연하였기 때문에 O(longN)이나 O(N)으로 해결하는 알고..
level3_합승택시요금(2021 KAKAO BLIND RECRUITMENT)
문제 https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 접근방법 1) 접근 사고 백준의 "특정한 최단 경로"의 쉬운 버전이었습니다. ..
level2_순위검색(2021 KAKAO BLIND RECRUITMENT)
문제 https://programmers.co.kr/learn/courses/30/lessons/72412
level2_메뉴리뉴얼(2021 KAKAO BLIND RECRUITMENT)
문제 https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 접근방법 1) 접근 사고 n의 범위를 확인하고 완전탐색 + 구현으로 구현하면 된다고 생각하여 문제를 구현했습니다. 그러나 테스트 케이스를 다 통과했지만 반례를 찾지 못하여 다시 재구현했습니다. 백트래킹을 활용해서 모든 조합을 구해주는 방법으로 접근하였습니다. 조합 중에 course에 들어있는 값으로 이루어진 조합의 사이즈 중 가장 큰 사이즈를 기억하는 배열 ..
level1_신규 아이디추천(2021 KAKAO BLIND RECRUITMENT)
문제 https://programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 접근방법 1) 접근 사고 정말 단순한 구현 문제였습니다. 각 조건 순서별로 구현하면 되는 문제입니다. 디버깅 실수만 줄이면 쉽게 구현 가능합니다. 2) 시간 복잡도 O(n) 3) 실수 없었습니다. 4) PS 문자열 라이브러리를 좀 더 잘 다뤘다면 더 쉽게 풀 수 있었을꺼 같다. 정답코드
12100번-2048(easy)
문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 접근방법 1) 접근 사고 1.상하좌우로 기울이는 모든 경우를 DFS로 탐색 2.이때 탐색이 5가 되면 배열중 가장 큰 값을 찾고 비교해준다. 2) 시간 복잡도 O(n ^ 2) 3) 실수 1. 113번째 줄에서 처음에 memcpy를 사용하여 배열의 복사와 갱신을 진행해주려고 하였다. 그러나 DFS 재귀함수에 매개변수 배열을 넘겨서 재귀함수 상태에서 배열의 사이즈는 ..
좋은 객체 지향 설계의 5가지 원칙(SOLID)
개요 클린코드로 유명한 로버트 마틴이 좋은 객체 지향 설계의 5가지 원칙을 정리한것 1.SRP: 단일 책임 원칙(single responsibility principle) 한 클래스는 한나의 책임만 가져야 한다. 하나의 책임이라는 것은 모호하다. 클 수 있고, 작을 수 있다. 문맥과 상황에 따라 다르다. 중요한 기준은 변경이다. 변경이 있을 때 파급 효과가 적은 단일 책임 원칙을 잘 따르는 것이다. 예) UI변경, 객체의 생성과 사용을 분리 2.OCP: 개방-폐쇄 원칙 (Open/closed principle) 소프트웨어 요소는 확장에는 열려 있으나 변경에는 닫혀 있어야 한다. 위의 문장은 모순이 존재한다. 다형성을 활용해서 생각해보자 인터페이를 구현한 새로운 클래스를 만들어서 새로운 기능을 구현해보자 ..
20058번-마법사 상어와 파이어스톰
문제 https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 접근방법 1) 접근 사고 1. 입력받은 배열들을 2^L * 2^L 로 나눈다. 2.이후 모든 분리된 격자를 시계 방향으로 90도 회전한다. 3.Board에 모든 얼음들을 돌면서 인접해 있는 얼음이 3개가 아닌 경우는 1씩 감축한다. 4.이중 반복문을 활용한 얼음의 총합값과, BFS를 활용한 가장 큰 얼음 덩어리를 탐색하여 정답을 반환한다. 2) 시간 복잡도 O(n ^ 3)..
20057번 - 마법사 상어와 토네이토
문제 https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 접근방법 1) 접근 사고 태풍에 대한 구조체를 두어 태풍의 이동을 계산하기 쉽게 작성했다. 1. 태풍이 이동한다. 2. 이동한 위치에 모래가 존재한 지 파악한다. 모래가 있을 경우 태풍의 구조체 중 c.perBoard에 담긴 수치 값을 활용하여 비율에 맞게 모래를 전파한다. 없을 경우 다음 탐색으로 넘어간다. 3. 범위가 초과하여 합계에 더 해줘야 하는지 bo..
20055번-컨베이어 벨트 위의 로봇
문제 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 접근방법 1) 접근 사고 문제에서 주어진 그대로 구현하면 되는 문제엿다. 1.컨베이어벨트와 로봇들을 한 칸씩 회전시킨다 2.로봇들만 앞으로 한 칸 전진한다. 이때 내리는 위치에 가면 로봇이 사라진다.(내린다는 표현이 애매한거 같다. 컨베이어 벨트 밑으로 로봇을 내린다는 의미로 해석해서 푸는데 어려움이 있었다.) 3.첫 번째 위치에 가중치가 있고 로봇이 없다면 로봇을 둔다..
19238번-스타트택시
문제 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 접근방법 1) 접근 사고 1. 내가 태울 승객을 BFS 탐색으로 정한다, 이때 소모한 가스값은 갱신해준다. 2. 태울 승객의 위치에서 도착지까지 BFS 탐색을 한다, 이때 소모한 가스값은 갱신해준다. 2) 시간 복잡도 O(V + E) 3) 배운 점 여러 번 시도한 문제이다. 테스트 케이스는 다 통과하나 문제가 자꾸 틀렸습니다가 나와서 힘들었다 이에 대해..
BFS, DFS 탐색 팁
저는 항상 BFS 문제를 풀 때 구현을 다한 뒤 테스트 케이스를 다 통과하고 맞왜틀을 정말 많이 겪었습니다. 한 번 갇힌 사고에서는 탈출하기 정말 어려운 게 알고리즘 문제이고 이러한 경우를 어떻게 하면 줄일 수 있을까 정말 많이 고민했습니다. 그래서 저의 안좋은 습관을 찾고자 노력하였고 치명적이 안 좋은 습관을 한 가지 찾았습니다. 안 좋은 습관은 BFS 탐색의 조건절에서 저는 "찾고자 하는 경우"를 조건으로 넣어주는 습관을 가지고 있었습니다. "이게 뭔소리냐 찾고자 하는 경우를 조건으로 넣는 게 왜 안 좋은 습관이냐?"라고 하실 수 있습니다. 하지만 찾고자 하는 경우를 찾는 것보다는 안 되는 경우를 찾는 게 더 쉽고 정확합니다. 밑에 문제로 예시를 들어보겠습니다. 백준 https://www.acmicp..
19237번-어른 상어
문제 https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 접근방법 1) 접근 사고 1. 상어의 이동 1-1. 상어의 방향에서 냄새가 없는 경우 1-2. 냄새가 없다면 상어의 방향에서 냄새가 있는 경우 2.냄새 1씩 감축 2.현재 상어의 위치에 상어의 냄새 추가 의 알고리즘인데 사실 특별한 알고리즘도 없고 그냥 구현하면 되는 문제였다. 그러나 디버깅 단계에서 런타임 오류를 잡아내지 못해서 시간이 정말 오래..
19236번-청소년상어
문제 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 접근방법 1) 접근 사고 런타임 에러 때문에 거의 3일을 고민하면서 푼 문제라서 죽을 때까지 잊지 못할 문제인 거 같습니다. 알고리즘의 단계는 밑에 단계로 이루어져 있습니다. 1. 입력값을 받는다. 2. 물고기를 이동시켜준다. 이때 죽은 물고기의 방향은 -1로 표시한다.(모든 물고기를 각 단계마다 움직여야 하는데 -1 물고기는 죽은 물고기 이므로 움직이지 않는다.) 3. 상..
17779번-게리멘더링2
문제 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 접근방법 1) 접근 사고 전체적인 로직은 각 구역의 가능한 인덱스 범위를 먼저 구합니다. 그리고 완전탐색을 통하여 각 구역의 범위들과 일치하는 조건을 통하여 구역별로 값을 구합니다. 이후 정렬을 하여 가장 큰 값과 가장 작은 값을 마이너스 연산을 한 뒤 최소값 갱신을 진행해주면 됩니다. 더 자세한 설명은 주석 첨부하였습니다. 실제 시험 문제로 나온다면 식 정리를 하다가 실수해서 못 풀거 같습니다...
17142번-연구소3
문제 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 접근방법 1) 접근 사고 바이러스의 경우를 조합으로 구현하여 바이러스가 퍼질 수 있는 모든 경우의 수를 BFS를 사용하여 탐색하였습니다. 주의해야 할 점은 BFS를 사용하여 시간을 측정할 때 0의 갯수를 cnt해서 바이러스가 모두 퍼져있는지의 유무의 형태로 작성하신다면 중간에 탐색을 통한 cnt 갯수가 0의 모든 갯수와 일치한 경우 탐색을 종료하는 조건절을 추가하셔야 합니다. 그렇지 않으면 모두 탐색..
17140번-이차원 배열과 연산
문제 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 접근방법 1) 접근 사고 까다로운 구현 문제였습니다. 자세한 로직은 주석으로 첨부하였습니다. 2) 시간 복잡도 O(N^2) 3) 배운 점 특별히 없는거 같습니다. 4) PS 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40..
17143번-낚시왕
문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 접근방법 1) 접근 사고 구현 문제 였습니다. 상어를 잡는 구현은 쉬우나 상어의 이동 부분을 구현하는 것이 까다로운 문제였습니다. 나머지 위치를 통해서 위치를 구해야겠다는 생각은 했으나 왼쪽 벽에서 떨어진 위치와 오른쪽 벽에서 떨어진 위중 어느곳에서 위치를 정해야 하는지 구현하는데 시간을 많이 소모했습니다. 2) 시간 복잡도 O(N^3) 3) 배운 점 이런 이동 기법은 코..
17144번-미세먼지 안녕
문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 접근방법 1) 접근 사고 특별한 알고리즘이 없지만 인덱스의 값 설정에 주의해서 풀어야 하는 문제였습니다. Spread, upper_move, Bottom_move 3가지 함수로 각 동작들을 정의하여 문제를 해결하였습니다. 2) 시간 복잡도 O(N^2) 3) 배운 점 람다식을 사용할때 캡쳐영역을 전체로 사용할 때 밖에 있는 변수와 이름이 같은 것을 사용하면 안된다는것을 알게 되었습니다. 만약..
16236번-아기상어
문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 접근방법 1) 접근 사고 개인적으로 구현이 어려웠던 문제였습니다. 상어가 탐색하는 경우를 q 배열에 넣어주었고 경로중 문제에서 주어지는 최적의 조건을 탐색하기 위해 우선순위 큐(코드에서 pass 변수)를 사용했습니다. 물고기를 먹을 수 있는 경우도 문제에서 최적의 조건이 주어지므로 우선순위 큐를 한 개 더 사용(문제에서 pq)하여서 이동한 경우를 다시 q배열에 넣어주고 반복하였습니다...
16235번-나무재테크
문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 접근방법 1) 접근 사고 그대로 구현하면 되는 문제였습니다. 저는 봄을 구현하는 과정에서 잘못된 구현으로 시간을 많이 낭비하였습니다. 양분을 먹고 새로 추가해주는 과정에서 새로운 배열에 담은 뒤에 기존 배열을 갱신해야하는데 그렇게 하지 않고 같은 배열에 두고 값을 넣어서 죽은 나무, 갱신 전에 나무의 값이 남아있어서 틀린 답이 나왔습니다. 이 부분을 제외한 계절의 구현은 정확..
16234번-인구이동
문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 접근방법 1) 접근 사고 구현량이 많은 구현 문제였습니다. 갱신 이후에 갱신을 할 것인지 말 것인지 구분하는 부분을 작성하는 부분이 핵심 구현입니다. 처음에 visited로 갱신 부분과 중복 부분을 같이 사용하였으나 값을 갱신할 때 값이 중복되는 부분이 생기는것을 알았습니다.(국가와 국가가 i, j번 타이밍에 연합되는 것을 i, j + 1 때에도 가져가는 실수를 저지름) 그래서..
15686번-치킨배달
문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 접근방법 1) 접근 사고 문제를 요약하면 치킨집을 m개의 경우를 선택했을때 각 집마다의 치킨 거리가 최소가 되는 것들의 합을 구하는 문제였습니다. 저는 치킨이 가능한 경우의수 m개를 numArr에 넣어주고 m - chicken.size()의 개수만큼 0을 넣은뒤 next_premutaion을 통해 모든 경우의 수를 만든뒤 집과의 거리를 연산하였습니다. 2) 시간 복잡도 ..
15685번-드래곤커브
문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 접근방법 1) 접근 사고 단순 구현 문제인데 "드래곤 커브의 회전을 어떻게 구할 것인가?"라는 명제가 핵심인 문제였습니다. 처음에는 재귀함수로 구현을 할 생각을 했었는데 0 ~ n 세대 순으로 증가하기 때문에 각 방향에서 방향의 크기만큼 한 번더 회전을 해주면 총 드래곤 커브의 회전량이 나오기 때문에 재귀함수로 구현하지는 않았습니다. 2) 시간 복잡도 O(n^2) ..