OSNIM

문제 : https://www.acmicpc.net/problem/12865 정답 코드 import sys def knapsack(N, capacity): for i in range(1, N+1): W = weight[i-1] V = value[i-1] for j in range(1, capacity+1): if W > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(V+dp[i-1][j-W], dp[i-1][j]) return dp[N][capacity] if __name__=="__main__": input = sys.stdin.readline N, K = map(int, input().split()) #행은 아이템의 개수 #열은 가방의 최대 무대 #dp[i][j] ..

Level 2 해시 문제 : https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 제출 코드 def solution(clothes): answer = 1 dic = {category : 0 for name, category in clothes} for name, category in clothes: dic[category] += 1 if len(dic) == 1: print(dic[category]) answer = dic[category] return answer for k in dic.keys(): answer *= (dic[k]+1) answer -= 1 return answer 정리 및 복습 ..

Level 2 해시 문제 : https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 제출 코드 def solution(phone_book): answer = True phone_book.sort(key = lambda x : (x, len)) for i in range(len(phone_book)-1): left = phone_book[i] right = phone_book[i+1] if left == right..

Level 1 해시 문제 : https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 시행착오 첫번째 코드는 동명이인을 해결하지 못했습니다. 그래서 딕셔너리와 count를 이용했으나 테스트 케이스는 맞았지만 효율성 문제에서 틀렸습니다. 따로 남겨놓지 못해서 코드가 없습니다. 정답 코드 정렬해서 이름이 다른 것이 나오면 바로 출력하게 만들었습니다. 1명만 완주를 못했으니까 정렬로 빠르게 해결이 가능했..

Level 1 해시 문제 : https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 접근 방법 이름을 key, 번호를 value로 하여 딕셔너리로 저장 각 ID 별로 2차원 배열을 생성 > reportList[i][j] i인덱스가 j인덱스를 신고를 했으면 1 안했으면 0 reportList를 같은 열끼리 더한 것이, k를 넘으면 reportList[i][j]가 1인 것만 answer[i] 1증가 def fin..

문제 : https://www.acmicpc.net/problem/11724 첫번째 풀이 처음에 서로소 방법인 줄 알고 그래프 이론의 서로소 구하는 방법을 이용하여 구현하려고 했습니다. 코드는 다음과 같습니다. import sys #특정 원소가 속한 집합 찾기 def findParent(parent, v): # 루트노드가 아니라면 루트 노드를 찾을 때 까지 재귀적 호출 if parent[v] != v: parent[v] = findParent(parent, parent[v]) return parent[v] #부모 합치기 def unionParent(parent, v1, v2): v1 = findParent(parent, v1) v2 = findParent(parent, v2) if v1 < v2: par..

문제 : https://www.acmicpc.net/problem/2011 제출 코드 def solve(): code = list(map(int, input())) dp = [0] * (len(code)+1) dp[0] = 1 dp[1] = 1 if code[0] == 0: print(0) return N = len(code) code = [0] + code for i in range(2, N+1): one = code[i] if one > 0: dp[i] += dp[i-1] two = code[i-1]*10 + code[i] if 10

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB T = int(input()) # 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다. def dfs(start, depth): global ans ans = max(ans, depth) for next in graph[start]: if visited[next]: continue visited[next] = True dfs(next, depth + 1) visited[next] = False for test_case in range(1, T + 1): N, M = map(int, input().split()) graph = [..

문제 : https://programmers.co.kr/learn/courses/30/lessons/59045 제출 코드 SELECT ANIMAL_INS.ANIMAL_ID,ANIMAL_INS.ANIMAL_TYPE, ANIMAL_INS.NAME FROM ANIMAL_INS LEFT JOIN ANIMAL_OUTS ON ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID WHERE ANIMAL_INS.SEX_UPON_INTAKE != ANIMAL_OUTS.SEX_UPON_OUTCOME ORDER BY ANIMAL_INS.ANIMAL_ID 후기 단순하게 입양 당시 중성화의 유무와 보호소에서 나갈 당시 중성화의 유무가 틀린 경우를 시도해봤는데 한번에 답을 맞았습니다. 많이 어려운 문제..

문제 : https://programmers.co.kr/learn/courses/30/lessons/59044 제출코드 SELECT ANIMAL_INS.NAME, ANIMAL_INS.DATETIME FROM ANIMAL_INS LEFT JOIN ANIMAL_OUTS ON ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID WHERE ANIMAL_OUTS.ANIMAL_ID IS NULL ORDER BY ANIMAL_INS.DATETIME LIMIT 3 학습내용 (My SQL) 상위 n 개 출력 하는 방법 : LIMIT n 하위 n 개를 출력하는 방법: ORDER BY 순서를 DESC로 바꿔 LIMIT n 사용 NULL을 적용하는 Key: LEFT JOIN 적용 되는 TABLE의..

문제 : https://programmers.co.kr/learn/courses/30/lessons/59043# 제출 코드 SELECT DISTINCT ANIMAL_INS.ANIMAL_ID, ANIMAL_INS.NAME FROM ANIMAL_INS LEFT JOIN ANIMAL_OUTS ON ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID WHERE ANIMAL_INS.DATETIME > ANIMAL_OUTS.DATETIME ORDER BY ANIMAL_INS.DATETIME

문제 : https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 조건 요약 ''' 가장 처음 온도 0, 빈칸은 온도 0 1. 집에 있는 모든 온풍기에서 바람 한번 나옴 2. 온도 조절 3. 온도가 1이상인 가장 바깥쪽 칸의 온도 1 감소 4. 초콜릿 하나 먹음 5. 모든 5번칸 온도가 K 이상이 되었는지 검사 , 모든 칸의 온도가 K 이상이면 중단, 아니면 1반복 온풍기 나오는 방향: 동서남북 중 하나 나오는 칸 바로 옆은 5 증가. 그 다음 4 (x..

문제 : https://www.acmicpc.net/problem/2133 풀이 N 일때 dp[N]의 위 그림 오른쪽처럼 3개로 나누어 집니다. 1. dp[N] = dp[N-2] x 3 2. dp[N] += i는 2부터 N-4 까지 dp 값에 2를 곱하고 모두 더한 부분 3. N이 2씩 증가할 때 마다 나타나는 새로운 타일 배열 : +2 제출 코드 def solve(): n = int(input()) dp = [0] * (30+1) dp[1] = 0 dp[2] = 3 for i in range(4, n+1): if i%2 == 1: continue dp[i] = dp[i-2]*3 for j in range(0, i-2, 2): dp[i] += dp[j]*2 dp[i] += 2 print(dp[n]) re..

22.05.05 추가) PC에서 검색하고 들어오면 화면이 모바일 버전으로 나옵니다. 다른 페이지는 문제가 없는데 어항정리만 뒤에 url에 "/m/" 이 추가되는 것을 확인했습니다. https://osnim.tistory.com/entry/%EB%B0%B1%EC%A4%80-23291-%EC%96%B4%ED%95%AD%EC%A0%95%EB%A6%AC-%ED%8C%8C%EC%9D%B4%EC%8D%AC 위 사이트로 이동해서 글을 보시면 모바일 화면이 아닌 PC 화면으로 글을 보실수 있을 것입니다 빨리 문제를 해결하겠습니다. 문제 : https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이..

구현, 시뮬레이션 문제 : https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 문제 요약 및 정리 ''' 4x4, 물고기 M 마리, 이동방향 1부터 8까지 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 상어와 물고기 같은 칸 가능, 둘 이상의 물고기 같은 칸 가능 마법 한번 다음과 같은 작업 순서 1. 복제 마법 시전 (5번에서 물고기 복제) 2. 모든 물고기 한 칸 이동 상어가 있는 칸 X, 물고기 냄새가 있는 칸 X..

문제 : https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 문제 요약 ''' 1. NxM, 오른쪽 동쪽, 위쪽 북쪽, 주사위 각 면 1~6, 전개도 2. 전개도 2 4 1 3 5 6 3. 지도 윗 면 1, 동쪽을 바라보는 방향이 3 인 상태, 지도와 맞닿은 부분 6 4. 가장 처음 주사위 이동 방향 : 동쪽 주사위 이동 방식 1. 이동방향으로 한칸 구름, 칸이 없다면 반대방향으로 한 칸 구름 2. 도착한 칸 점수 획득 3. 주사..

문제 : https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 조건을 간단하게 정리하면 다음과 같습니다. ''' 1. 각 칸에 바구니, 바구니에 저장할 물의 양 제한 X 2. 1번행과 N 번 열이 연결되어 있음, 즉 맵 벗어나도 상관 x 3. 비바라기 > 맨 아래 1열 2열 맨 아래 위 행 1열 2열 비구름 생성 4. 비 구름을 M 번 이동, 방향 8개, 방향 d, 거리 s, 5. 방향 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 1. 모든 구름..

문제 : https://www.acmicpc.net/problem/2579 첫번째 풀이 (재귀, 시간초과) start: 시작 인덱스, seq: 연속 2개 선택하는 것 판단 result: 현재까지 선택한 계단의 합 def dfs(start, seq, result): global ans if seq > 2: return if start > N: return if start == 5: ans = max(ans, result) return if start + 1 < N: dfs(start + 1, seq+1, result+a[start+1]) if start + 2 < N: dfs(start + 2, 1, result+a[start+2]) N = int(input()) a = [] ans = 0 for i in..

문제 출처: https://www.acmicpc.net/problem/20055 첫번째 풀이 최적화 이전 방법 (Python3는 시간초과, pypy3 는 통과) 1. 한 칸 회전 deque의 rotate를 이용하여 구현, robot을 벨트 위 index로 저장 popleft를 사용하여 처음 넣은 로봇이 처음 이동하게 만듦 robot에 저장된 인덱스를 1씩 증가 시켜 벨트 N번 칸이 아닐 경우만 로봇을 저장 2. 모든 로봇 한 칸씩 이동 popleft로 먼저 올라간 로봇 먼저 로봇의 위치를 저장한 robots 배열에서 현재 로봇이 다음 칸에 로봇이 있는지 확인 not in 으로 확인 처음 로봇이 N번째 위치에 있다면 robots 배열에 다시 삽입 X 3. 로봇 추가 4. count로 내구도 0인 벨트 개수..

문제 출처: https://www.acmicpc.net/problem/19238 나의 접근법 그래프에 남은 연료를 넣기 위해 벽을 -1로 변경 손님들의 위치 정보와 도착정보를 따로 저장 BFS() 1. 먼저 현재 위치에 손님이 있는지 확인 2. BFS로 거리 1차이 나는 거리 확인 -> q에 넣기 3. 같은 거리에 또 다른 손님이 있는지, 첫 손님은 찾았는지, 거리가 같은지 -> custList에 추가 4. 현재 g에 넣는 연료 (남은 연료)가 첫 손님을 찾았을 때 남은 연료보다 작은지 -> 작다면 거리가 같은 손님은 다 찾은 것 -> 정렬 후 행이 낮고 열이 낮은 손님부터 목적지 찾기 5. 가까운 손님을 첫손님을 찾은 경우 -> custList에 추가 5-1 만약 그 첫 손님이 마지막 칸에 있는 경우 ..