brute-Force
[백준] 17089. 세 친구 - Python
[Gold V] https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net 풀이 Brute-Force로 모든 경우를 순회하며 검사하면 되는 문제. 다만 정말 생각없이 3중첩 for문으로 구현한다면, N(3 ≤ N ≤ 4,000) 이기 때문에, O(N^3) 으로는 시간초과를 받을 수밖에 없다. 아래와 같이 순회를 돌게 되면, line 17~20 의 두 번째 for문까지의 시간 복잡도가, "사람의 수"가 아닌 "친구..
[백준] 2615. 오목 - Python
[Silver I] https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 풀이 19x19의 모든 칸을 순회하며, 오목이 되는 지 여부를 Brute-Force로 검사하면 된다. 오목이 될 수 있는 모든 경우는 하향 직선 5개, 우하향 대각성 5개, 우향 직선 5개, 우상향 대각선 5개가 이어지는 4가지의 경우가 존재하며, 시작하는 돌의 바로 이전 칸과, 5개째가 아닌 6개째의 칸까지 같이 확인하여 6목이 되지 않는 지를 검사해야 한다. AC. b = ..
[프로그래머스] 양궁대회 - 파이썬
2022 KAKAO BLIND RECRUITMENT - 92342. 양궁대회 [Lv. 2] https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음 보았을 때는, Greedy하게 접근해야 할 지, DP로 접근해야 할 지.. 고민이였으나, 정확성 테스트로 제한 시간이 10초, 성능 테스트가 없었으며, 배열의 길이도 11이므로 2^11 = 2048가지 정도의 경우의 수를 다 따져보아도, TLE가 나지 않을 것이라 생각. 따라서, Brute-For..
[백준] 14939. 불 끄기 - 파이썬
[Platinum V] https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 백조의 호수 이후로 오랜만에 풀어보는 플래티넘 문제. ^ㅁ^ 풀이 우선, 10x10 배열 - 100칸이기에, 너무 무모한 Brute-Forcing만 아니면, TLE는 나오지 않겠거니 하고 생각했다. 처음 보자마자 떠올린 것은, 한 번 누른 칸은 다시 누를 일이 없지 않을까? 라는 것. 한 번 눌린 칸을 다시 누르게 되면, 5칸이 결국 누르기 전의 상태와 같아지는 ..
[백준] 17142. 연구소 3 - 파이썬
[Gold III] https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 이 문제는... 사실 토마토나, 백조의 호수 같은 문제와 유사한 문제였으나, 시간이 조금 걸렸다. 문제를 푸는 핵심은, '비활성화된 바이러스 또한 전염이 진행될 수 있도록 처리할 것.' 그리고, '비활성화된 바이러스가 활성화되는 것은 최소 시간을 측정하는 데에 고려하지 않아야 할 것.' 이것들을 유념하며 문제를 풀어 나가야 한다. 풀이 1 일단 BFS 문제라..
[프로그래머스] 이모티콘 할인행사 - 파이썬
2023 KAKAO BLIND RECRUITMENT - 150368. 이모티콘 할인행사 [Lv. 2] https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 우선, 문제를 다 읽자마자 확인한 것은- "Brute-Force로 해결할 만 한가?" 였다. 이모티콘의 각 할인율은 10%, 20%, 30%, 40% 중 하나이고, 1 ≤ emoticons의 길이 = m ≤ 7 에서 볼 수 있듯, 이모티콘이 최대 7개이므로, 7^4 = 2041가지 경우의 ..
[백준] 12100. 2048 (Easy) - 파이썬
[Gold II] https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 유명한 2048 게임을 구현하는 문제였다.. 일단 보드의 크기도 최대 1 0: row[j] = row[j-1] j -= 1 row[0] = 0 temp = 0 # 합쳐져서 한 칸 당겼다면 다시 그 index부터 검사 index += 1 else: temp = row[index] index -= 1 return board def up(board):..
[백준] 1107. 리모컨 - 파이썬
https://www.acmicpc.net/problem/1107 풀이 이것저것 여러 방법을 생각해 봤으나, 마땅한 수가 생각나지 않았음. 문제 조건에서 채널이 500,000개 정도였기 때문에 Brute-Force로 시도해볼 만하다고 생각해서 Brute-Force로 실행. 다만 0~500,000 까지의 수를 모두 대입해 보기보다는, 고장난 버튼을 염두에 두고, 조합 가능한 모든 6자리까지의 경우의 수를 미리 만들어 두고, 그 이후 처리하는 것이 속도 면에서 이득이다. # 100에서 움직일 때와 버튼을 누르고 움직일 때, 둘 중 최솟값을 채택 channels[ch] = min(abs(goal - 100), len(str(ch)) + abs(goal - ch)) 0 ~ 500,000 까지의 모든 수를 대입한..