문제 https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 처음에는 일일히 다 구현하느라 힘들어 죽는줄알았는데... 분명 잘 했는데... 맞왜틀? 이라서 그냥 해설을 봤다.. 알고보니 한 번에 좋아하는 학생수, 비어있는 칸을 계산해두고 정렬을 하는 문제였다. 그리고 candidate = sorted(candidate, key=lambda x:(-x[0],-x[1],x[2],x[3])) 여기서 sorted는 정렬을 해서 candidat..

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 삼성 SDS 가고싶다. 코테 준비 열심히 해야지. 합격할래... ㅠㅠㅠ 이제 시작하지만 열심히 해보겠습니다. - BFS를 매번 돌려서 매번 먹을 수 있는 물고기를 찾아줘야함. - 이때 정렬 조건이 까다로우므로 lambda를 사용. - 물고기 먹고 상어위치 업데이트 하고, 크기 증가하나 체크하고... 따질게 많아서 무조건 메모장에 정리하면서 해야할 듯. 코드 from collect..

문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 다익스트라 제일 기본문제.. 코드 import heapq import sys read = sys.stdin.readline INF = int(1e9) v, e = map(int,read().split()) graph = [[] for _ in range(v+1)] #연결이 어디어디 되어있나 확인 k = int(read()) #입력받기 for _ in..

문제 https://www.acmicpc.net/problem/17129 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106) 이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다. 2, www.acmicpc.net 풀이 처음에는 모든 거리를 다 구한뒤, 3,4,5까지의 거리가 모두 -1인 경우만 NIE를 출력했고 이외의 경우에는 -1을 제외하고 최솟값을 구해주었다.. 근데 어차피 BFS는 근처에 있는거 먼저가니까 BFS하는 와중에 3,4,5를 만나면 믿음을 가지고 chk 변수를 두어보았더니 성공했다. ..

문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 이진 탐색을.. 완전히 이해하고 싶었다. 간단한 문제인줄 알았는데 난관을 많이 만나버렸다.. 일단, Test case로 2 10 3 9 가 주어진다면 답이 0이 아니라 1이 되어야한다. 즉 처음 시작할 때 start값을 1로 세팅해주어야 한다. 그리고.. 시간초과가 자꾸 나서 뭐가 문제인지 찾아보다가.. for문 사용 방식에 있어서 1번으로 하니 ..

이진 탐색: 반으로 쪼개면서 탐색하기 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 이미 정렬되어 있다면 매우 빠르게 데이터 찾을 수 있음. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 변수 3개 사용: 탐색하고자 하는 범위의 시작점, 끝점, 중간점 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교. 시간 복잡도 : O(logN) 반복문으로 구현 def binary_search(array, target, start,end): while startend되면 끝 mid = (start+end) // 2 #내림 if arr[mid] == target: return mid #찾았으면 중간지점 인덱스 반환 elif arr[mid] > target: #찾는게 중간지점 값보다 작으면 왼쪽..

문제 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 1. 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다.라는 조건을 잘봐야한다. 큐에 들어갈 때 바이러스 번호를 기준으로 정렬을 한 다음 넣어주면 매 초마다 큐에 바이러스 번호가 작은 순서대로 남게 된다. 그리고 매 초마다 큐에 들어오는 칸 수만큼 반복해서 상하좌우 검사를 해준다. 이 문제를 예시로 - 맨 처음에는 3개의 바이러스가 큐 안에 들어있다..

조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모이제이션(Memoization) 다이나믹 프로그래밍을 구현하는 방법 중 한 종류 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져옴 캐싱이라고도 함. 한 번 구한 정도를 리스트에 저장하는 방식으로 사용 → 사전 자료형 사용할 수 있음. 탑다운(하향식): 재귀 함수를 이용, 큰 문제 해결하기 위해 작은 문제 호출 피보나치 수열 #한번 계산된 결과 메모이제이션 하기 위한 리스트 초기화 d = [0] * 100 #피보나치 함수를 재귀함수로 구현(탑다운) def fibo(x): #종료 조건 if x==1 or x==2: return 1 #이미 계산한 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에 스테이지에 도달한 플레이어 수와 스테이지에 도달했으나 아직 클리어하지 못한 플레이어수를 if문을 통해 각각 구해주니 시간 초과가 떴다. 따라서 if문을 줄이고자, 실패한 유저만 계산하고, 스테이지에 도달한 플레이어 수는 처음 스테이지 길이에서 실패한 유저수를 빼주는 식으로 코드를 바꾸었더니 정답! 정렬을 연습하고자, lambda를 사용하였다. lambda 사용법은, arr=sor..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 BFS로 문제를 풀었다. dq.popleft한 값을 저장하고 그 값에 연결된 노드를 탐색해야하는데.. 계속 삽질했다 코드 from collections import deque def solution(n, computers): answer = 0 vis = [False]*n for i in range(n): #컴퓨터 개수만큼 순회 if(vis[i] == False): #i번째 방문 안했으..