OSNIM

Level 3, Graph 문제 : https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제 설명 n개의 노드를 가진 그래프 각 노드는 1부터 n까지 번호가 매겨짐 1번 노드에서 가장 멀리 떨어진 노드의 개수 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미 간선에 대한 정보가 담긴 2차원 배열 vertex 1번 노드로부터 가장 멀리 떨어진 노드 개수 반환 제한사항 2

문제: https://www.acmicpc.net/problem/10026 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2,..

Level 3, DFS/BFS 문제: https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결 > 컴퓨터 A와 컴퓨터 C도 간접적으로 연결된 하나의 네트워크 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주..

Level 4, DP 문제: https://programmers.co.kr/learn/courses/30/lessons/42897# 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 문제 설명 접한 두 집을 털면 경보 처음과 마지막이 연결된 원형 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값 출력 제한사항 3

문제 : https://programmers.co.kr/learn/courses/30/lessons/59413 코딩테스트 연습 - 입양 시각 구하기(2) ANIMAL_OUTS 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블입니다. ANIMAL_OUTS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, NAME, SEX_UPON_OUTCOME는 각각 동물의 아이디, 생물 programmers.co.kr 문제 설명 컬럼 명 컬럼 정보 ANIMAL_OUTS: 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블 ANIMAL_ID 아이디 ANIMAL_TYPE 생물 종 DATETIME 입양일 NAME 이름 SEX_UPON_OUTCOME 성별 및 중성..

1번: 고양이와 개는 몇 마리 있을까 문제: https://programmers.co.kr/learn/courses/30/lessons/59040 코딩테스트 연습 - 고양이와 개는 몇 마리 있을까 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr ANIMAL_INS 테이블 예시 ANIMAL_ID ANIMAL_TYPE DATETIME INTAKE_CONDITION NAME SEX_UPON_INTAKE A373219 Cat 2014-07-29..

1번 최댓값 구하기 https://programmers.co.kr/learn/courses/30/lessons/59415 코딩테스트 연습 - 최댓값 구하기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr ANIMAL_INS 테이블 ANIMAL_ID ANIMAL_TYPE DATETIME INTAKE_CONDITION NAME SEX_UPON_INTAKE A399552 Dog 2013-10-14 15:38:00 Normal Jack Neut..

문제 : https://www.acmicpc.net/problem/1181 첫번째 풀이 (정답) import sys from collections import defaultdict input = sys.stdin.readline n = int(input().strip()) datas = set() # 1. 중복제거 dic = defaultdict(list) # 디폴트딕셔너리 = 키값이 없어도 바로 키랑 값 넣을 수 있음 for i in range(n): s = input().strip() datas.add(s) #2. 순서대로 정렬 datas = sorted(list(datas), key=lambda x:len(x)) # 3. 길이에 따라 딕셔너리에 구분 for s in datas: dic[len(s)]..

문제 : https://www.acmicpc.net/problem/2609 첫번째 제출 코드 (정답) import sys A, B = map(int, sys.stdin.readline().split()) GCD = 0 LCM = 1 for i in range(1, min(A+1, B+1)): if A%i == 0 and B%i==0: GCD = i SET = set() for i in range(1, max(A+1, B+1)): if A%i == 0: SET.add(i) DividendA = A DividendB = B LCMList = [] divider = 2 while DividendA and DividendB: if DividendA % divider == 0 and DividendB % divi..

문제 : https://www.acmicpc.net/problem/2096 첫번째 제출 코드 (메모리 초과) import sys def solve(): MAX = 0 MIN = 0 for i in range(1, N): for j in range(3): if j == 0: dp[i][0] = arr[i][0] + max(dp[i-1][j], dp[i-1][j+1]) elif j == 1: dp[i][1] = arr[i][1] + max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) else: dp[i][2] = arr[i][2] + max(dp[i - 1][j], dp[i - 1][j - 1]) MAX = max(dp[-1]) for i in range(1, N): for j i..

DP, Level 3 문제 : https://programmers.co.kr/learn/courses/30/lessons/42898 문제 설명 물에 잠기지 않은 지역을 통해 등교 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1) 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n) 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 제한사항 격자의 크기 m, n은 1 이상 100 이하인 자연수 m과 n이 모두 1인 경우는 없음 물에 잠긴 지역은 0개 이상 10개 이하 집과 학교가 물에 잠긴 경우는 없음 주의사항 웅덩이의 좌표는..

DP, Level 3 문제 : https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 첫번째 제출 코드(오답) def solution(N, number): answer = 0 dp = [9] * 32001 check = [N] dp[N] = 1 cnt = 1 while cnt

구현, 문자열 문제 : https://www.acmicpc.net/problem/2941 제출 코드 import sys input = sys.stdin.readline string = input().strip() croatia = ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z='] cnt = 0 for alpha in croatia: string = string.replace(alpha, '*') print(len(string)) 첫번째 문자가 크로아티아 알파벳에 있는 문자중 첫번째 문자와 같으면 2자리 또는 3자리를 비교하는 방식으로 풀려고 했습니다. 그런데 너무 복잡해지고 풀이가 산으로 가는 것 같아 검색으로 힌트를 얻었습니다. 크로아티아 알파벳의 문자들을 rep..

수학, 구현, 브루트 포스 문제 : https://www.acmicpc.net/problem/4673 제출 코드 import sys print = sys.stdout.write check = [0] * (10001) for i in range(1, 10001): string = str(i) temp = i for j in string: temp += int(j) if temp < 10001: check[temp] = 1 for i in range(1, 10001): if not check[i]: print(f"{i}\n") 결과 및 정리 처음에 문제가 단순한 수학 함수여서 쉽게 풀 수 있을 줄 알았습니다. 하지만 10 이하의 셀프넘버 중 2, 4, 6, 8이 안되는 이유를 못찾았습니다. 그런데 자기 자신..

Level 3, Greedy 문제 : https://programmers.co.kr/learn/courses/30/lessons/42884?language=python3 코딩테스트 연습 - 단속카메라 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 1. 나간 기준 오름차순 정렬 2. 카메라 위치 -30001로 초기화 3. if 나간 지점 >= 다음 차량 진입 지점 ( 두 차량이 겹치는 경우) continue (다음 차량 확인) else: 차량 나간 지점에 마지막 카메라 위치 초기화 answer += 1 제출 코드 def solution(routes): answer = 0 routes.sort(key = lambda x : x[1]) lastC..

문제: https://programmers.co.kr/learn/courses/30/lessons/42861?language=python3# 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 첫번째 제출 코드 (오답) import heapq as hq def solution(n, costs): answer = 0 visited = set() q = [] SUM = 0 costs.sort(key=lambda x: (x[2], x[0], x[1])) for start, end, cost in costs: if start in visited and end in visited: continue answer += co..

힙을 이용한 최단 경로 알고리즘 구하기 import heapq as hq def dijkstra(start, graph, distance): q = [] # 시작 노드로 가기 위한 최단 거리는 0으로 설정 hq.heappush(q, [0, start]) distance[start] = 0 while q: #최단 거리의 섬과 거리 dist, now = hq.heappop(q) #현재 섬이 처리 되었다면 스킵 if distance[now] < dist: continue #현재 섬과 연결된 다른 섬들을 확인 for e, c in graph[now]: #도착지, 비용 cost = dist + c # 현재 노드를 거쳐 다른 섬으로 이동하는 거리가 더 짧은 경우 if cost < distance[e]: distan..

Level 1 Greedy(탐욕법) 문제 : https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3# 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 첫번째 정답 코드 def solution(n, lost, reserve): answer = 0 reserve.sort() lost.sort() temp = reserve[:] for i in reserve: if i in lost: lost.remove(i) temp.remove(i) r..

완전탐색, Level 3 문제 : https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 정답 코드 def solution(brown, yellow): answer = [] # m : 노란 카펫의 가로 # n : 노란 카펫의 세로 for m in range(1, yellow+1): if yellow%m == 0: n = yellow//m if (m+2)*(n+2) == brown + yellow: answer.a..

level 2 힙 문제 : https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr import heapq def solution(scoville, K): answer = 0 q = [] for i in scoville: heapq.heappush(q,i) while len(q) > 1: if q[0] >= K: break food1, food2 = heapq.heappop(..