14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 안전 구역의 크기의 최댓값을 구하는 문제다. 벽은 3개 설치할 수 있는데, 벽은 안전구역에 설치할 수 있다. 전체 그래프 크기 N*M = 8*8 = n or ny = m: continue # 벽으로 간 경우 if graph[nx][ny] == 1: continue # 다른 바이러스의 칸으로 간 경우 # if graph[nx][ny] == 2: # continue if not visited[nx][ny]: if graph[nx][ny] == 0 or grap..
알고리즘/이것이 코딩테스트다
18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net BFS 문제다. 문제에서 모든 도로의 거리는 1이라고 했으니, 모든 간선의 비용이 1인 것이다. 이럴 때는 BFS를 활용해서 최단 거리를 구할 수 있다.(간선의 비용이 다른 경우에는 다익스트라) 노드의 개수 N은 300,000 이하이고, 간선의 개수 M은 1,000,000 이하이므로, 시간 복잡도는 O(N+M)에 의해 완전완전 가능하다. 기초적인 BFS 구현을 통해 풀 수 있는 문제다. 풀이..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현 문제다. 구현이 쉽지 않다. 내가 코드를 짜면 코드가 너무 복잡해진다. 그래서 풀이를 볼 수 밖에 없었다. 풀이 제한 조건을 봤을 때, weak 리스트와 dist 리스트의 길이가 매우 작으므로 완전 탐색 가능하다. -> 이건 알고 있었음 문제에서 찾고자 하는 것은 "투입해야 하는 친구 수의 최솟값"이다. 이 때 전체 친구의 수(dist의 길이)는 최대 8이므로, 모든 친구를 무작위로 나열하는 모든 순열의 개수를 계산하면 8P8 = 40,320으로 충분히 계산가능하다. -> 이것도 알고 있었음 그러므로 친..
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 이해는 쉽지만 구현이 까다로웠던 문제다. 완전탐색으로 풀려고하니, 내 구현에서는 4중 for문까지 들어가더라. 4중 for문으로 풀어도 되겠다는 생각이 들었던 이유는 대충 시간복잡도를 계산해보면 1초에 간당간당하게 들어간다고 판단했기 때문이다. 먼저 치킨 집을 최대 m개 뽑는다고 하는데 그래서 combinations를 사용했다. 먼저 전체 맵의 크기 N의 범위는 2
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현 문제다. 처음에는 기둥이나 보가 좌표에 있을 경우 1, 없을 경우 0으로 구현하려고 했으나, 그럴 경우에는 기둥과 보를 어떻게 구현해야 할지 모르겠더라. 그리고 기둥, 보 조건을 확인할 때, 인덱스를 넘어서는 경우는 또 조건문을 넣어서 구현해야하나? 라는 생각이 들었고 ,그럴 경우 코드가 너무 복잡해지는 것 같다는 생각이 들었다. 이러한 이유들로 끙끙대다가 풀이를 봤다. 풀이 코드 # 현재 answer 리스트 안의 구조물이 가능한 구조물인지 판단하는 함수 def is_possible(answer): fo..
3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 지렁이가 사과를 먹으면서 크기를 키우는 게임이다. 큐 자료구조를 사용했다. 큐 자료구조에는 2가지를 저장한다. 1. 입력받은 command 2. 뱀의 몸이 위치하고 있는 칸 입력받은 command는 (시간, 방향) 정보를 저장하고 있는데, 왜 큐를 사용했냐면 문제 조건에서 방향 전환 정보는 시간이 증가하는 순서대로 주어진다고 했기 때문이다. 그러므로 큐 자료구조를 사용해서 popleft() 메소드를 통해 다음 방향 전환 정보를 얻을 수 있다. 그리고, 뱀의 몸이 위치하..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 읽고나서 처음에는 이렇게 생각했다. 자물쇠의 크기는 열쇠 크기 이상이므로 열쇠를 꽂을 수 있는 모든 경우의 수에 꽂아봐서 맞는 경우에는 True, 아니면 False를 리턴하자라고 생각했다. 문제 제한시간이 1초였고, 자물쇠와 열쇠의 크기는 20이하였다. 1초에 2,000만번 정도의 연산이 가능하므로 O(N^4) 이상도 가능한 수치여서 완전 탐색으로 풀 수 있는 문제이다. 첫 풀이 처음에는 lock에서 0인 부분은 key에서 1이여야하고, lock에서 1인 부분은 key에서 0이여야 한다고 생각했다. 그..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문자열을 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 리턴하면 되는 문제이다. 문자열 s의 길이가 1000이하고 시간 제한은 1초이므로 O(S^2)도 가능한 문제라서 완전탐색으로 풀면 된다. 내 풀이 s = input() def solution(s): answer = 987654321 previous = "" temp = 0 check = True for i in range(1, len(s) + 1): index = 0 while index < len(s) - 1: if previous == s[inde..
숫자(0~9)와 알파벳 대문자로 이루어진 문자열 중, 모든 알파벳을 오름차순으로 먼저 출력하고, 그 후 모든 숫자를 더한 값을 이어서 출력하면 되는 문제다. 시간 제한은 1초고, 문자열의 길이는 최대 10,000이다. -> O(NlogN)까지 가능하다는 생각 간단한 구현문제다. 1. 문자열의 원소들을 하나씩 확인한다. 2. 만약 확인한 원소가 문자일 경우 다른 문자열에 삽입한다. 3. 만약 확인한 원소가 숫자일 경우 total 변수에 숫자를 더한다. 4. 1~3과정을 마친 후 문자만 들어가 있는 문자열을 오름차순 정렬한다. 5. 문자만 들어있는 문자열을 출력하고, total변수를 출력한다. 내 코드 # Q_08_문자열 재정렬 s = list(input()) arr = [] total = 0 for cha..
18406번: 럭키 스트레이트 첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. www.acmicpc.net 시간 제한이 1초였고, N도 99,999,999이하인데 어차피 반으로 나눠서 더하므로 sum 함수를 이용해서 더해주면 된다. 내 풀이 # Q_07_럭키 스트레이트 arr = list(map(int, input())) length = len(arr) if sum(arr[:length // 2]) == sum(arr[length // 2:]): print("LUCKY") else: print("READY") 풀이 코드 # Q_07_럭키 스트레이트 n = input() length = len(n) summary = 0 ..
