본문 바로가기

algorithm280

[프로그래머스/C++] 쿼드압축 후 개수 세기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 정사각형 안에 있는 숫자가 전부 같지 않으면 사각형을 4개로 나눠서 탐색하면 되는 문제다. 먼저 정사각형의 모든 숫자가 같은지 탐색한다. 이때 전부 숫자가 같다면 그 숫자가 0일 경우 0의 개수를 1 증가시키고, 1의 개수를 1 증가시키면 된다. 만약 다르다면 4개로 쪼개서 다시 탐색하면 된다. (재귀적으로 탐색) 4개로 쪼갤 때, x와 y좌표의 시작점과 끝점을 이용해 절반으로 나눠서 사용하면 된다. ex) [x좌표 시작, x좌표 중간], [x좌표 중간+1, x좌표 끝] 으로 경우를 나눌 수 있다 (y도 마찬가지) [아이디어 정리] 정사각형안의 모든 수가 같은지 검사한다. 만약 모든 수가 같다면, .. 2024. 4. 6.

[프로그래머스/C++] [1차] 다트 게임 (2018 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 문자열 구분만 잘하면 쉽게 해결할 수 있는 문제다. 먼저 숫자가 나오면 연속된 숫자를 탐색해 획득한 다트 점수가 몇인지 계산한다. 이후 나오는 문자열이 S, D, T인지에 따라 점수를 몇 제곱할지 구현한다. 만약 *이 나온다면 현재 점수와 앞 점수를 2배 해야하므로, 몇 번째로 다트를 던졌는지 기록하는 index를 선언해 사용했다. 여기서 숫자를 입력 받는 방법은 아래와 같이 구현했다. 먼저 num에 -1을 저장한다. 그리고 문자열을 탐색을 시작한다. 이때, 문자열에 있는 문자가 숫자라면 num에 어떤 수가 저장되어있는지 확인한다. 만약 -1이라면 아무 숫자도 입력이 안됐으므로 num의 숫자를 이번에 .. 2024. 4. 5.

[백준/C++] 양팔저울 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때, 정말 풀 수 있나? 의문이 들었다.왜냐하면 아무리 DP로 푼다고 해도, 시간 복잡도는 O(3^n)이 되기 때문이다. (n은 추의 개수) 여기서 3^n인 이유는 아래와 같이 3가지 경우가 존재하기 때문이다. 1. 구슬 쪽에 추를 올리는 경우2. 추를 사용하지 않는 경우3. 구슬 반대편에 추를 올리는 경우 그렇기 때문에 시간 복잡도는 O(3^n)이다. 한번 최악의 경우를 상상해 보면 추의 무게가 1, 3, 9 ,27 ... 처럼 3의 배수로 늘어나는 경우이다. (중복해서 만들어지는 추의 무게가.. 2024. 4. 5.

[프로그래머스/C++] 후보키 (2019 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때, 후보키가 될 수 있는 키들을 선정하려면 어떻게 해야할까 고민을 많이 했다. 이미 후보키가 된 조합이 포함되어 있다면 후보키가 될 수 없으므로 이를 구현하면 되지 않을까? 고민을 했다. 처음에는 재귀 함수를 만들어 가지치기를 하려고 했는데 잘 안돼서 그냥 키 하나로 만들 수 있는 경우, 키 2개로 만들 수 있는 경우... 의 모든 조합을 구하고, 이미 적은 키로 만들어진 경우는 제외하도록 코드를 구현했다. 나중에 다시 생각해보니 키들의 조합을 만드는 부분을 재귀함수로 가지치기 할 수 있을 것 같아서 재귀함수로 문제를 다시 풀었다. 예를 들어 1번 키를 무조건 포함, 2번 키를 무조건 포함.. 2024. 4. 4.

[백준/C++] 힘세고 강한 아침 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 풀 때, query가 들어올 때마다 계산을 했다. 그랬더니 시간초과가 나서 반복되는 계산을 줄이도록 문제를 풀었다. N이 100이기 때문에 첫 언어, 중간 언어를 정해 특정 언어로 변환하는데 걸리는 최소 비용을 계산할 수 있기 때문이다. 이 경우 O(N^2 * 최소 비용을 계산하는 시간복잡도) 이므로 문제가 해결될 것이라고 생각했다. 처음에 최소 비용을 계산할 때, priority queue를 이용해 탐색하지 않은 언어 중 항상 변환 비용이 가장 낮은 언어가 앞에 오도록 코드를 구현했다. 문제는 priority queue에 삽입하는데 O(logn)의 시간복잡도가 걸리기 때문에 시간초과가 또 났다... 2024. 4. 3.

[프로그래머스/C++] 문자열의 아름다움 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 풀이를 잘 생각해 구현하면 되는 문제다. 단, 크기가 300000이기 때문에 O(n^2)의 시간복잡도로는 해결할 수 없다. 그러므로 누적합을 활용해 O(n)의 시간복잡도로 문제를 해결했다. "aabba" 와 같은 문자열이 있다고 생각하자 이제 문자를 크게 두개로 나눠서 생각을 한다. 1. 양 끝 문자가 다른 경우 이 경우는 항상 문자열의 크기만큼의 아름다움을 갖게 된다. 2. 양 끝 문자가 같은 경우 이 경우는 양 끝 문자를 사이에 가장 아름다움을 갖는 문자를 찾아야 한다. 이제 아래와 그림을 보자 첫 문자 a부터 왼쪽으로 탐색을 시작한다. 탐색을 하다가 현재 문자가 b인데, 이전 문자가 a가 됐다. .. 2024. 4. 2.

[프로그래머스/C++] 빛의 경로 사이클 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때, 시작점이 정해져 있는지 아니면 정말 말 그대로 특정 격자에서 출발할 수 있는 모든 사이클을 구해야하는지 의문이 들었다. 제한사항을 보니 시작점 등의 제한사항이 없기 때문에 말 그대로 모든 사이클을 구하면 되겠다고 생각하고 문제를 풀었다. 이 문제에서 핵심은 사이클이다. 만약 한 격자에서 왼쪽으로 이동하는 경로가 있다면, 이 경로가 포함된 사이클은 몇 개일까? 정답은 무조건 한 개다. 왜냐하면 격자에서 특정한 방향으로 이동하게 되면, 결국에는 돌고 돌아 같은 사이클을 나타내기 때문이다. 그래서 사이클을 표시하기 위해 2차원 배열에 4가지 방향으로 이동했음을 저장하는 visited 배열을 .. 2024. 4. 1.

[프로그래머스/C++] 3 x n 타일링 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 경우만 잘 파악하면 쉽게 풀 수 있는 문제다. 가로 세로가 2*3 인 사각형에 2*3인 사각형을 더하면 4*3인 사각형을 만들 수 있다. 이를 이용하면 길이가 n인 사각형을 만들기 위해서는 [0*3인 사각형, n*3인 사각형] + [1*n인 사각형, (n-1)*3인 사각형] ... 을 전부 계산하면 된다. + 참고로 이 문제에서 길이가 홀수인 사각형은 만들 수 없다. 이를 이용하면 문제를 풀 수 있는데 그 전에 알고 넘어가야 되는 게 있다. 위 그림과 같이 길이가 6인 사각형은 [2*3인 사각형, 4*3인 사각형] 처럼 볼 수 있고, [4*3인 사각형, 2*3인 사각형] 으로도 볼 수 있다. 이 경우 .. 2024. 3. 31.

[프로그래머스/C++] 브라이언의 고민 (2017 카카오코드 예선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 이 문제는 많은 예외처리를 하느라 시간이 꽤 걸린 문제였다 반례도 많이 만들어 테스트를 했다... [문제 풀이] 이 문제에서 중요하게 봐야할 점들은 아래와 같다. 1. 광고 규칙은 2개가 있으며, 서로 다른 광고 규칙 2개는 같이 적용될 수 있다. 2. 하나의 광고규칙이 한 단어에 여러번 적용될 수는 없다. 3. 광고 규칙에 사용된 소문자는 다시 사용할 수 없다. 위 3가지 사항에 유의해서 문제를 풀어야 한다. 먼저 광고문구 sentence를 앞에서부터 탐색한다. 이때, 대문자가 나오면 tempString이라는 str에 더한다. 만약 소문자가 나오면 그 소문자가 sentence에 몇 개가 나오는지 센다. 여기서 소문자의 개수에.. 2024. 3. 30.

[프로그래머스/C++] 안티세포 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 이 문제를 처음 봤을 때 어떻게 풀지 많이 고민했다. 모든 경우를 계속해서 계산하기에는 너무 계산이 많아졌기 때문에 이전에 계산된 내용을 이용해 빠르게 문제를 풀 수 있을 것 같았다. 고민 후에 DP와 Map을 이용해 문제를 해결했다. [문제 풀이] 안티세포 X와 Y에 들어 있는 수 들을 아래와 같이 표현한다고 가정하자 $$ Y\,=\,(i_{ys},\, ...\, i_{ye})$$ $$ X\,=\,(i_{xs},\, ...\, i_{xe})$$ 여기서 안티세포 Y와 X의 합이 같아서 합쳐진다면 합쳐진 새 안티세포 N은 아래와 같이 표현할 수 있다. $$ N\,=\,(i_{ys},\, ...\, i_{xe})$$ 이제 N의 왼.. 2024. 3. 29.

[프로그래머스/C++] 튜브의 소개팅 (2017 카카오코드 본선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 보고 어떤 값을 기준으로 priority_queue를 사용하거나 BFS로 풀면 되겠다는 생각이들었다. 그런데 priority_queue를 사용하면 정렬하는데 시간이 걸린다. 게다가 내가 return 할 답은 거리가 가장 짧은 값 중에서 대화시간이 가장 짧은 값이기 때문에 거리를 기준으로 정렬을 할 것이라면, BFS를 이용하면 된다. 그래서 BFS로 문제를 풀었다. BFS를 이용하면 항상 원점에서 이동한 거리가 짧은 값이 queue에서 먼저 나온다. 그러므로 이를 이용해 특정 지점에 방문할 때 마다 가지치기를 해, 쓸모없는 경우들을 가지치기 해 주었다. 가지치기를 하기 위해서 visited라는 2차원 배.. 2024. 3. 28.

[프로그래머스/C++] 가사 검색 (2020 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 처음 이 문제를 봤을 때 trie 알고리즘을 사용하면 빨리 문제를 해결할 수 있겠다는 생각이 들었다. 왜냐하면 특정 문자가 같은지 비교하고 수를 세는 과정에서 trie 알고리즘을 사용하면 빠르게 해결 될 것 같았기 때문이다. 문제는 조건을 제대로 안읽어서 ab?cd와 같이 중간에 ?가 들어갈 수 있는 줄 알고 코드를 구현했다. 하지만 알고보니 양 끝에만 ?가 연속적으로 들어갈 수 있었다... [문제 풀이] trie 알고리즘으로 문제를 푼 방법은 다음과 같다. 예를 들어 trie라는 문자가 들어온다고 가정하자. 이 경우 위 그림과 같이 t 뒤에는 물음표가 3개 오는 경우가 올 수 있다. 이를 map를 이용해 [문자열의 길이: 개.. 2024. 3. 27.

[프로그래머스/C++] 표 병합 (2023 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 표 병합 문제에서 중요한 명령어는 MERGE와 UNMERGE다. 다른 명령어들은 vector를 이용하면 바로 수행할 수 있지만, MERGE나 UNMERGE된 셀일 수 있기 때문에 이를 파악하는게 중요하다. 이 문제를 풀기 위해 union-find 알고리즘을 이용했다. 예를 들어 (1, 1) 셀과 (2, 2) 셀이 병합 되었다고 가정하자. 이 경우 (2, 2) 셀은 (1, 1)셀의 집합에 포함되어 있다고 표시를 한다면, (2, 2)셀의 값을 업데이트 하거나 변경할 경우 (2, 2)셀의 집합의 값을 변경하면 문제가 해결된다. UNMERGE는 반대로 한 집합에 속한 모든 원소들을 초기화 시키고 마지막에 명령어에 있는 .. 2024. 3. 26.

[프로그래머스/C++] 징검다리 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 생각 났던 풀이는 가장 짧은 거리를 찾은 다음 어떤 돌을 제거할지 선택하는 방법이다. 하지만 이 방법은 최악의 경우 시간복잡도가 O(N^2)이 되기 때문에 다른 방법을 생각했다. 그러다가 바위 사이의 최소 거리를 정한 다음 돌을 몇 개 제거해야 하는지 계산하면 더 빠르게 연산이 될 것이라는 생각이 들었다. 여기서 바위 사이의 최대 거리는 도착점까지의 거리이므로 min Distance = 1, max Distance = 도착점까지의 거리로 이분탐색을 하도록 코드를 구현했다. 예를 들어 돌 사이의 최소 거리가 4라고 하면, 돌 A와 돌 B 사이의 거리는 최소 거리인 4보다 커야한다. 만약 돌 A, B 사이의 .. 2024. 3. 25.

[프로그래머스/C++] 몸짱 트레이너 라이언의 고민 (2017 카카오코드 본선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때, 규칙을 찾아보려고 생각했다. 규칙을 찾을 경우 인원이 최대 몇명 겹치는지 알면 쉽게 풀 수 있을 것 같았기 때문이었다. 인원이 최대 몇명 겹치는지를 계산하기 위해서 운동 시작시간을 기준으로 정렬을 한다. 운동이 끝나는 시간을 pq에 삽입하고, pq에 들어있는 시간이 다른 사람의 운동 시작 시간보다 빠르다면 그 사람은 운동이 끝났으므로 pq에서 빼준다. 이때 pq의 크기가 max인 경우가 최대 사람 수다. 하지만, 2명인 경우와 사람의 수가 n*n/2+n%2 보다 큰 경우를 빼고는 규칙을 찾기 힘들었다. 그래서 다음으로 생각한 풀이는 2명 이상일 경우에 최대 거리가 2*(n-1)이하로 나.. 2024. 3. 24.

이전 1 ··· 6 7 8 9 10 11 12 ··· 19 다음

티스토리툴바