공부해볼라는 스토리

1. 문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 후하후하 이거 어떻게 DP로 풀어야하나 했는데 ㅠㅠ 전혀 검색을 안해서 순전히 내생각으로 해보자면 1) 내가 지나가야하는 숫자들 2) 지나간 숫자들을 같은 인덱스로 또 다음 후보군으로 만났을때 그 수를 저장 이 두가지를 저장하는 느낌으로? 1. 위 말한 저장할 변수 두 가지를 선언한다. (대신 count변수는 첫째자리 바뀔때마다 매번 초기화) 2. 이제 첫째 자리(index=0)부터 시작한다. (1~9만 가능) ==> queue 선언해서 (i, 0) 로 시작 3. next 가 빌때까지 계속..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 그림으로 재현하자면 약간 이런느낌입니다. 최단거리니까 역시 BFS로 구현하는데, 1. 만약 target 단어가 words 안에 없으면 그건 안되는 거라 0 반환 2. word안에서 연결리스트로 그래프 딕셔너리 생성하기 3. 생성 기반으로 bfs돌려서 최단거리 확인하기 BFS 문제를 하도 풀다보니까 이젠 간편하다,, ## code ## import collections def ..

1. 문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 2. 풀이 사실 이문제는 열심히 풀었는데 계속 시간초과가 났다ㅠ 그래서 도움을 좀 받은,,, 그래도 덕분에 스택을 잘 사용하는 법을 알게됨. 처음엔 그냥 원래 스택 -> 이미 사용한 스택 이렇게 해서 다 검사하게 했는데 생각해보니 뒤에 보낼때 다~~ 검사하는게 아니라 한번이라도 어떤 수보다 작았으면 pop 하면 됐는데ㅠ 그걸몰랐다. 1) NGE, stack 변수를 설정한다. 2) i=n-1부터 돌..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42747# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 ## 내 code ## 1) 내림차순 정렬한다 2) 시작은 제일 큰 citation 3) hindex가 0까지 돌리면서 hindex가 ciations[i] 보다 커지는 순간을 찾는다 ==> 이때 만약 hindex보다 그 citations[i]까지의 길이가 더 길거나 같으면 최대 hindex임 4) 근데 hindex 가 citations 안에 있는 수들보다 작을 수도 있으니 ..

1. 문제 https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 2. 풀이 1) 숫자를 사용했는지 아닌지 파악하는 visited 변수 설정, max/min 변수 설정 2) bt 함수: 리스트에 숫자 하나는 넣고 시작 ==> 부등호 하나, visited에 방문안했던 (False)인 숫자 가져와서 부등호 만족하는지 확인하고 다음으로 넘김 ==> 만약 다음에 안되는 경우의 수면 더이상 진행안됨 3) idx == n 까지 다오면 그 숫자가 max/min인..

1. 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2.풀이 자세한 풀이는 위 사진으로 설명하겠습니다 !! ## code ## import sys from collections import * n = int(sys.stdin.readline()) grape = [] for _ in range(n): grape.append(int(sys.stdin.readline())) # 0: 이번거 안먹음 , 1: 연속적으로 안먹엇고 이번거 먹음, 2:..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43164# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 드디어 Lv 3 문제도 좀 적응한거같다 ㅠㅠ 이 문제는 dfs로 이용해서 풀었다,, 이유는 진입경로를 끝까지 파서 마지막까지 닿으면 되기 때문이다. 대신 그럴려면 sort로 알파벳 순서대로 정렬해줘야한당 1) 주어진 경로를 유방향 그래프 (directed graph) 의 인접리스트로 구현한다. ** 내가 추가해서 썼던 테케,, [["ICN", "B"], ["ICN", "C"..

1. 문제 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 2. 풀이 백트래킹도 좀 감이 오는거같다!! 후 코테 이제 드루와 (사실 들어오지 마세요ㅠ 문제는 연속된 숫자끼리의 차이 절댓값을 max로 만드는거고, 우선 백트래킹으로 푸는거에 중점을 뒀다. 1) total_max라는 전역변수 만들어주고, 어디서 처음 계산을 시작할지 한번씩 돌려준다. 2) 백트래킹 함수 내부: 다돌았을때 멈춘다 (return). total이 크면 바꿔준다. visited는 inde..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 후 하 후 하 드디어 탐색 감을 좀 잡은거 같다. 문제는 네트워크 개수를 찾는 문제인데, 최단거리도 아니고 깊이 있게 훑는게 효율적일거 같아서 DFS로 짰다. 사실 시행착오 한 번 겪긴 했는데,, 그 주어진 데이터 상태 그대로 풀려다가. 뭔가 서로 연결된 관계 matrix를 주니까 그렇게 풀어야할거 같앗는데 생각해보니까 차라리 그 관계 matrix로 연결 리스트를 만드는게 ..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 이런식으로 이동해서 도착하는건데, 생각해보니 최근 풀었던 코테랑 문제가 많이 비슷했네??,,, 오호 최단거리를 구해야했기 때문에 bfs로 풀어줬습니다. 1. (x, y, 현재까지 이동길이) 를 받는 bfs 함수를 만든다. 2. 상하좌우 이동가능해서 dx, dy는 그렇게 좌표 설정을 해준다. 3. queue에 계속 쌓아주면서 돌다가, 마지막 좌표에 도착하면 반환해준다. 4. 아참..