본문 바로가기

Algorithm/프로그래머스131

[프로그래머스/C++] 코딩 테스트 공부 (2022 KAKAO TECH INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 모든 문제를 풀기 위한 알고력과 코딩력을 상승시키고, 이때 최소 시간을 구하는 문제다. 여기서 문제를 풀기 위해서는 문제에서 요구하는 알고력과 코딩력을 만족해야 하므로, 모든 문제를 풀기 위해서는 각 문제에서 요구하는 알고력과 코딩력의 값 중 가장 큰 값 이상으로 능력을 올리면 된다. 여기서 최소 시간을 구해야 하는데 DP를 이용하면 쉽게 풀 수 있다. 특정 수치의 알고력과 코딩력을 갖추는데 걸리는 최소시간을 구하면, 이 최소 시간을 이용해 다른 특정 알고력과 코딩력을 갖추는데 걸리는 최소시간을 구할 수 있기 때문이다. (즉, 작은 문제를 해결하는 것으로 전체 문제를 해결할 수 있기 때문에 DP를 이용.. 2024. 3. 4.

[프로그래머스/C++] 단어 퍼즐 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 최솟값을 어떻게 찾을지만 고민하면 쉬운 문제다. 이전에 작은 문제들을 바탕으로 다음 문제를 해결하는 DP로 쉽게 풀 수 있는데, 왜냐하면 특정단어까지 만드는데 사용되는 최소횟수를 이용해 다음 문자까지 만드는데 사용되는 단어의 최소 횟수를 구할 수 있기 때문이다. 아래 그림을 보면 특정 문자가 주어지면 그 문자의 i번쨰 문자를 만드는데 단어가 사용되는 최소 횟수가 적혀있다. 이제 d라는 문자까지 만드는데 사용되는 최소 횟수는 다음과 같이 구해 볼 수 있다. 1. a에 "bacd"라는 문자를 더하기 2. b에 "acd"라는 문자를 더하기 3. a에 "cd"라는 문자를 더하기 4. c에 "d"라는 문자를 더.. 2024. 3. 3.

[프로그래머스/C++] 짝수 행 세기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 아이디어가 정말 안 떠올랐다. 규칙을 발견해 조합으로 해결이 될 것처럼 보였는데, 아무리 고민을 해도 짝수개의 열을 만드는 작업이 잘 안됐다. 그러다가 다른사람의 질문에서 홀수와 짝수라는 힌트를 얻고 방법이 떠올라 문제를 해결할 수 있었다. 먼저 문제의 조건에서 a 배열의 특정 열에 1이 포함된 개수와 b 배열의 특정 열에 있는 1의 개수가 같아야 된다. 그렇기 때문에 이 조건을 만족하기 위해 a의 각 열 당 몇 개의 1이 있는지 개수를 센 다음에 그 열에 있는 1들의 개수만큼 각 행에 배치를 해주면 된다. 여기서 1의 개수를 배치하는 방법을 조합으로 나타낼 수 있는데, n개의 행에서 1을 배치할 r개.. 2024. 2. 29.

[프로그래머스/C++] 모두 0으로 만들기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 트리를 따라서 트리에 저장되어 있는 수들을 0으로 만드는 문제다. 이때 서로 연결된 노드를 기준으로 한쪽 노드는 +1, 한쪽 노드는 -1을 수행할 수 있다. 이를 요약하면 a노드에서 b노드로 숫자를 옮긴다고 볼 수 있다. a노드에 5가 저장되어 있고, b노드에 3이 저장되어 있다면, a노드의 5를 b노드에 더하고 a노드를 0으로 만들 수 있다. (이 때 연산의 횟수는 a노드에 저장된 수의 절댓값인 5 이다.) 여기서 모든 노드를 0으로 만들때 필요한 연산의 횟수를 return하라고 했는데, 이를 계산하기 위해서는 특정 노드를 기준으로 DFS 탐색을 하면서 계산하면 된다. 예를 들어 0번 노드를 기준으로.. 2024. 2. 27.

[프로그래머스/C++] 표 편집 (2021 카카오 채용연계형 인턴십) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 문제 자체가 어렵지는 않은 문제다. 하지만 효율성 테스트가 있기 때문에 문제를 효율적으로 풀기 위한 방법이 필요하다. 삭제를 한 칸은 제외하고 이동을 하는게 문제인데, 왜냐하면 삭제한 칸은 제외하고 이동을 해야하기 때문이다. 그렇기 때문에 삭제한 칸이 많다면, 삭제했는지 확인을 하면서 이동을 하기 때문에 효율성이 떨어지게 된다. 그렇다면 어떻게 삭제했는지 확인을 줄이면서 효율성을 높일 수 있을까? 방법은 여러가지가 있겠지만, 이 문제에서는 U와 D의 총 이동의 횟수가 제한되어 있으므로 삽입과 삭제를 빨리하면 효율성 테스트를 통과할 수 있겠다는 예상을 할 수 있다. 그래서 삽입과 삭제를 빨리 할 수 있는.. 2024. 2. 26.

[프로그래머스/C++] 광고 삽입 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] HTML 삽입 미리보기할 수 없는 소스 그렇게 별 생각 없이 문제를 풀려고 했더니 전혀 다른 문제라는 것을 알게 됐다. 이 문제는 광고는 길이가 포함되어 있기 때문에, 실제로 광고를 시청한 시간이 가장 긴 부분을 계산해야 됐기 때문이다. 그래서 어떻게 문제를 풀까? 고민을 하다가 어차피 특정 구간에 광고를 시청했는지 파악을 하려면 누적합을 이용하면 총 [3600*100(시간) - 광고길이] 만큼만 크기 비교를 하면 되니까 풀리겠다는 생각이 들었다. 문제는 여기서도 고민이 생겼다. 누적합으로 문제를 해결하는 것은 어렵지 않은데, 누적합을 구하기 위해 특정 구간에 몇명이 광고를 보고 있는지 표시를 해야했다. 영상을 .. 2024. 2. 25.

[프로그래머스/C++] 110 옮기기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 어떤 방법으로 풀어야 할까 고민을 많이 했던 문제다. "110"이라는 숫자를 찾을 때 마다 위치를 옮기는 방법은 비 효율적이고 "110"이라는 문자를 찾아 옮겼을 때, 합쳐진 문자열에서 다시 "110"이라는 숫자가 나오는 경우도 생기기 때문이다. 그래서 실제로 숫자를 옮기지 않고, 특정 위치들을 기준으로 0과 1만 바꿀까? 생각했지만, 이 방법도 생각해야할 예외가 많았다. 그래서 고민하던 중 위치를 옮기는 대신 '0'이라는 글자가 나올 때 마다 "110"이라는 글자가 만들어지는지 확인하고 제외시키는 방법을 생각했다. 이 문제에서 중요한 점은 사전에서 빠른 순으로 배치를 하는 것이다. 우리가 옮길 수.. 2024. 2. 24.

[프로그래머스/C++] 블록 게임 (2019 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 3가지 모양의 블럭을 90도로 회전한 모양이 존재할 수 있으며, 위에서 1*1 크기의 사각형을 떨어뜨려 사각형 모양으로 채울 수 있으면, 블럭이 삭제되는 문제다. 즉, 블럭이 삭제되기 위해서는 1*1 크기의 블럭이 위에서만 떨어지기 때문에 삭제가 가능한 블럭을 쉽게 구분이 가능하다는 뜻이다. 예를 들면 L 모양 또는 ㅗ 모양의 블럭은 위에서 블럭을 떨어뜨려 사각형을 만들 수 있지만, ㄱ 모양 ㅜ 모양의 블럭은 위에서 블럭을 떨어뜨려도 사각형으로 만들지 못한다. 그러므로 아래 5가지 경우의 블럭만 제거가 가능하다. 이제 제거가 가능한 블럭들을 알았으므로, 제거가 가능한 조건에 대해 생각해보자 블럭을 제거.. 2024. 2. 23.

[프로그래머스/C++] 트리 트리오 중간값 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 풀면서 고민을 많이 했던 문제다. n의 범위가 250000 이기 때문에 2차원 vector로 거리를 저장 하기에는 무리였다. 그렇다고 하나의 노드가 들어올 때 마다 노드들의 거리를 측정해 계산하자니, 약 250000*250000이기 때문에 이것도 무리라는 생각이 들었다. 그래서 노드들의 관계가 트리로 주어지기 때문에 하나의 노드를 부모 노드로 지정하고, 반복해서 자식 노드들을 잘 탐색하면 문제가 풀리지 않을까? 라는 생각을 했다. 여기서 먼저 짚고 가야하는 점이 있다. f(a, b, c)를 구할 때, 중간값을 가장 크게 하려면 어떻게 해야할까? 정답은 가장 거리가 긴 노드들을 알면 된다. 예를 들어 특.. 2024. 2. 22.

[프로그래머스/C++] 기둥과 보 설치 (2020 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 보와 기둥을 잘 구분하면 해결되는 문제다. 여기서 보를 건설 할 수 있는 조건은 양쪽에 보가 있거나, 한쪽 끝이 기둥위에 닿아있으면 된다. 기둥은 보의 한쪽 끝 위에 세우거나, 바닥, 기둥 위에 세울 수있다. 이를 고려해 보와 기둥이 세워졌는지 기록을 할 2차원 vector를 만들었다. 그리고 세워지는 위치를 기준으로 아래와 같이 정의했다. [x ,y]에 기둥이 세워졌다면 이 기둥은 [x, y]와 [x, y+1]을 차지한다는 뜻이다. [x ,y]에 보가 세워졌다면 이 보는 [x, y]와 [x+1, y]을 차지한다는 뜻이다. 이렇게 보나 기둥을 세울 수 있는지 검사하고 세울 수 있다면 보, 기둥을 세우도.. 2024. 2. 21.

[프로그래머스/C++] 리틀 프렌즈 사천성 (2017 카카오코드 본선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제의 사천성은 일반 사천성과 다르게 딱 한번만 방향을 꺾을 수 있다. 그리고 제한도 까다롭지 않기 때문에, A부터 Z까지 글자들의 위치를 저장해 뒀다. A부터 Z까지의 글자를 찾을 때, x를 기준으로 먼저 찾고 없다면 y를 증가시켜서 찾는 식으로 찾았기 때문에 특정 글자 중 y가 더 작은게 먼저 저장되도록 코드를 짰다. (y가 같다면 x가 작은 게 먼저 저장된다) 이렇게 코드를 짤 경우 두 좌표를 크게 직선과 꺾인 경우로 나눌 수 있다. 예를 들어 A라는 문자가 저장된 위치가 a, b라고 하자. 만약 a와 b의 y좌표가 같거나, x좌표가 같다면, 직선으로만 연결해 카드를 지울 수 있다. (한번만 꺾을 수 있.. 2024. 2. 20.

[프로그래머스/C++] 무지의 먹방 라이브 (2019 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때, 어떻게 풀까 고민을 많이 했다. 고민 끝에 크기 비교와 나누기를 잘 이용하면 쉽게 풀리겠다는 생각이 들었다. 먼저 음식을 먹는 시간인 food_times를 정렬한다. 여기서 음식을 먹는데 걸리는 시간이 가장 적은 음식을 다 먹기 전까지는 모든 음식의 개수가 그대로다. 만약 가장 시간이 적게 걸리는 음식을 다 먹었다면, 음식의 개수가 줄어든다. 그림을 보면 이해가 쉽다. 음식을 먹는데 걸리는 시간이 위와 같다고 가정하자. 그러면 먹는데 걸리는 시간이 가장 적게 드는 음식은 첫번째 음식(2) 이다. 그렇기 때문에 이 회전판이 두바퀴 돌 때 까지는 음식의 길이에 영향을 미치지 않는다. 만약.. 2024. 2. 19.

[프로그래머스/C++] 경주로 건설 (2020 카카오 인턴십) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 최소 비용을 구하는 탐색 문제다. 길을 연결하기 위해 드는 비용이 음의 값을 갖지 않고 시작위치와 끝 위치가 정해져있기 때문에 쉽게 풀 수 있는 문제다. 나는 BFS와 memoization을 이용해 풀기로 했다. 코너를 만들 때 비용이 추가가 되므로, 이를 구분하기 위해 방향을 구분할 필요가 있다. 그래서 내가 세로 방향으로 이동중이였는지 가로방향으로 이동중이였는지를 구분하고, 만약 가로 방향에서 세로로 방향을 바꾸거나 세로에서 가로로 방향을 바꾸면 비용을 추가해 비교하도록 코드를 구현했다. 그리고 이전에 y, x 지점을 세로방향으로 방문했을 경우 이번에 방문한 경우의 비용이 더 적다면 다시 탐색을 하.. 2024. 2. 17.

[프로그래머스/C++] 미로 탈출 (2021 카카오 채용연계형 인턴십) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 트랩이 있어서 경로가 계속 바뀌는게 특징인 문제다. 만약 트랩이 없다면, 특정 지점에 방문하는 가장 빠른 경로를 구하는 문제와 같기 때문에 최단 경로 알고리즘 중 다익스트라 알고리즘으로 풀 수 있다. 처음에는 최단 경로 문제인 것은 알았지만, 트랩 때문에 완전 탐색을 먼저 해보자는 생각이 들었다. 여기서 중요한 점은 특정 노드를 방문처리할 때, 트랩이 있기 때문에 한번 방문하면 다시는 방문하지 못하는게 아니라 최대 2번까지 방문이 가능하다는 점이다. 여기서 최대 2번까지 방문이 가능한 이유는 트랩을 처음 밟으면 방향이 바뀌는 경우고, 트랩을 그 다음 밟으면 원래 방향으로 바뀌는 경우다. 이후 3번 방문.. 2024. 2. 16.

[프로그래머스/C++] 자물쇠와 열쇠 (2020 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 열쇠로 자물쇠를 열 수 있는지 확인하는 문제다. 여기서 중요한 점은 열쇠의 블럭과 자물쇠의 블럭이 일치해야 하는데, 만약 열쇠의 블럭이 있는 부분이 자물쇠에 블럭이 있는 부분이라면 열지 못한다는 점이다. 그러므로 열쇠와 자물쇠가 정확히 일치해야 하는데, 자물쇠 밖에 있는 열쇠의 범위는 블럭이 있어도 되고 없어도 된다는게 특징이다. 그래서 문제를 풀 때 열쇠의 오른쪽 하단이 자물쇠 왼쪽 상단부터 시작해 전부 탐색하는 방식으로 코드를 구현했다. 위 그림에 보이는 것처럼 열쇠와 자물쇠가 겹치는 최소 범위부터 시작해 왼쪽으로 이동하고, 자물쇠의 가장 왼쪽과 열쇠의 가장 오른쪽이 겹치면 한칸 아래로 내려 다시 .. 2024. 2. 16.

이전 1 2 3 4 5 6 7 ··· 9 다음

티스토리툴바