'PS' 카테고리의 글 목록 (5 Page)

[백준/4949] 균형잡힌 세상 | Stack

2023.01.21·

PS/BOJ&Programmers

알고리즘전형적인 스택 문제다. 우선 괄호의 여는 부분이 왼쪽으로 와야 하기 때문에, 문자열을 돌면서 ( 나 [ 일 때 스택에 넣어준다.만약 스택에 값이 들어있는데 )나 ]가 들어오면 ( or [ 와 짝이 맞아야 하므로, 스택의 탑(stack[-1])을 통해 쌍이 맞는지 확인하고,쌍이 맞다면 스택에서 여는 괄호를 팝해서 스택을 비워준다.쌍이 아니라면 스택에 닫힌 괄호를 넣어준다. 이 알고리즘을 입력 받은 문자열을 모두 검사할 때까지 반복한다. 최종 코드while True: s = input() if s == '.': break stack = [] for i in range(len(s)): if s[i] == '(' or s[i] == '[': stack..

[백준/14592] 2017 아주대학교 프로그래밍 경시대회(small) - 파이썬

2023.01.18·

PS/BOJ&Programmers

알고리즘N의 크기가 1이 문제를 구현하면서 조건 거를 때 if 문 사용과 중복을 어떻게 걸러낼 것인지에 대해서 조금 익숙해진 것을 느꼈다. 최종 코드n = int(input())total = []cnt = []t = []for _ in range(n): s,c,l = map(int, input().split()) total.append(s) cnt.append(c) t.append(l) for i in range(n): # 같은 값이 존재하면 if total.count(total[i]) >= n: # 제출 횟수 같은 경우 if cnt.count(cnt[i]) >= n: print(t.index(min(t))+1) ..

[백준/13424] Three Dots / 완전탐색 - 파이썬

2023.01.17·

PS/BOJ&Programmers

알고리즘이 문제는 완전탐색 방식으로 풀면 점의 개수가 1000 개일 때, 1000 * 1000 * 1000 = 10^9로 시간 초과를 하게 된다.따라서 세 점의 거리가 동일한 케이스를 모두 계산하는 방법이 아닌, 동일한 간격이 존재하는 점을 찾는 방식으로 구현하도록 한다. 수직선 상에 임의의 세 점 a,b,c가 있을 때 점 C는 b에서 a와 b의 거리만큼 더한 값이다.이 알고리즘을 활용하여 점 C를 찾고, 이 값이 입력받은 list에 존재한다면 세 점은 동일한 거리를 가진 점들이다. 최종 코드from collections import defaultdictt = int(input())for _ in range(t): n = int(input()) dots = sorted(list(map(int,..

[백준/12759] 틱! 택! 토! - 파이썬

2023.01.17·

PS/BOJ&Programmers

첫번째 시도개인적으로 이 문제가 어려웠던 이유는 게임이 끝나고 승부를 판단하는 게 아니라 입력이 될 때 누가 언제 이기는지 알아내야 하기 때문에 헤맸다. 만약에 승부만 판단하는 문제였다면, 플레이어 1과 2가 했던 게임을 입력 받고 승부 조건만 확인하면 되기 때문이다. 그래서 처음에는 이렇게만 이해하고 다음과 같이 코드를 작성했다.# 먼저 시작하는 사람n = int(input())g = [[' ']*3 for _ in range(3)]for i in range(9): r,c = map(int, input().split()) # 게임판 if i % 2 == 0: g[r-1][c-1] = 'X' else: g[r-1][c-1] = 'O' # 승부 확인을 위해서 새로운 배열에 대입. ..

[백준/1100] 하얀 칸 | 파이썬 2차원 리스트

2023.01.16·

PS/BOJ&Programmers

파이썬 2차원 리스트 이 문제를 풀 때 8x8의 체스판을 입력 받고 정의해야 한다. 파이썬 2차원 리스트를 선언하는 방법은 다음과 같다.파이썬 2차원 리스트는 좌표평면이나 행렬 등과 같은 표현을 해야할 때 쓰이므로, 익혀두는 게 좋을 것같다.# 방법1arr = [list(input()) for _ in range(8)]# 방법2arr = []for i in range(8): arr.append(list(input())) 문제 해설TFTFTF... FTFTF... TFT... 체크무늬 체스판을 떠올리면 된다. 하얀 칸 위에 말이 몇 개 있는지 출력해야 하기 때문에, 하얀 칸의 인덱스에 대한 정보를 알아야 한다. 이때 행..

[백준/11652] 카드 - 파이썬

2023.01.14·

PS/BOJ&Programmers

알고리즘처음에는 정수를 하나씩 입력 받으면 정렬해서, 양옆을 비교한 뒤 같은 값이면 카운팅을 해주는 방법을 고안했다. 그러나 같은 값이 몇개인지 세어볼 때는 딕셔너리를 이용하는 게 효율적이다.기준이 되는 값을 key에, 해당 개수를 value에 저장하면 된다.얼마 전에 풀었던 https://www.acmicpc.net/problem/1159 문제도 이와 비슷한 알고리즘으로 같은 값 개수 세기문제를 해결할 수 있다. 1159번: 농구 경기상근이는 농구의 세계에서 점차 영향력을 넓혀가고 있다. 처음에 그는 농구 경기를 좋아하는 사람이었다. 농구에 대한 열정은 그를 막을 수 없었고, 결국 상근이는 농구장을 청소하는 일을 시작www.acmicpc.net for _ in range(n): num = int..

[백준/14582] 오늘도 졌다 | 야구 | 파이썬 리스트 누적합

2023.01.14·

PS/BOJ&Programmers

문제 이해평소 야구를 즐겨보지 않아서 그런지 초와 말에 대한 개념이 없었다.그래서 처음엔 그냥 i번째에 이기고 있으면 역전패가 성립한다고 코드를 구현했는데 틀린 거다...!질문 게시판을 통해 반례를 찾아보니 출제자가 그래서 문제 마지막에 경기는 1회초 -> 1회말 -> 2회초 -> ... -> 9회초 -> 9회말이라는 설명까지 덧붙인 듯하다.역시 문제를 꼼꼼히 잘 읽는 것도 중요하다. 괜히 써진 문장은 없기 때문에 최대한 힌트를 많이 얻어가는 게 유리하다. 파이썬 리스트 원소 누적합 게임은 현재까지 얻었던 점수들의 합으로 판단을 하기 때문에, 누적합을 구해서 승부를 판단했다.a = list(map(int, input().split()))b = list(map(int, input().split()))fl..

[백준/7510] 고급 수학

2023.01.14·

PS/BOJ&Programmers

🔎 알고리즘 삼각형의 세 변의 길이가 주어졌을 때, 이 삼각형이 직각 삼각형인지 아닌지 판단하기 위해 피타고라스의 정리의 역을 이용하면 된다. 피타고라스의 정리 : 직각삼각형에서 빗변 길이의 제곱은 다른 두 변의 길이의 제곱의 합과 같다. 피타고라스 정리의 역 : 세 변의 길이가 a,b,c인 삼각형에서 a^2 + b^2 = c^2이면 c가 빗변인 직각삼각형이다. 💻 최종 코드 각 변의 길이 위치를 알아야 계산을 할 수 있기 때문에 sorted(s)로 입력 받은 값을 정렬해주고, 인덱싱을 통해서 피타고라스의 역을 계산해주었다. n = int(input()) for i in range(n): s = list(map(int, input().split())) s = sorted(s) print('Scenario..

[백준/6996] 애너그램.. 반례찾기

2023.01.10·

PS/BOJ&Programmers

🔎 처음시도 n = int(input())for _ in range(n): a, b = input().split() cnt = 0 for i in a: if i in b: cnt += 1 if cnt == len(a) and len(a) == len(b): print('{} & {} are anagrams.'.format(a,b)) else: print('{} & {} are NOT anagrams.'.format(a,b))반례: aaaa aaab. 이유: if i n b 코드에서 변수 a와 변수 b가 가진 a의 개수에 상관없이, 포함되어있는지 아닌지만 판단했기 때문에, 오류 발생..그래서 a,b 서로서로 검사..

[백준/1159] 농구경기

2023.01.10·

PS/BOJ&Programmers

문제 이해첫글자를 key값으로 넣고, 다음 입력값의 첫글자가 이미 딕셔너리 key로 저장되어 있다면 +1 해주는 로직이 떠올랐다. 첫번째 시도 _ 실패n = int(input())d = {}for i in range(n): name = input() key = name[0] # 만약 이미 d에 key 값이 존재하는 경우 if d.get(key): d[key] += 1 else: d[key] = 1 ans = list(d.values()) for i in ans: if i >= 5: for k,v in d.items(): print(k) 첫번째 시도 모든 key 값을 출력해버림. items 함수를..

[백준/15726] 이칙연산

2023.01.01·

PS/BOJ&Programmers

처음 작성한 코드 a,b,c = map(int,input().split()) # 가장 작은 값을 나누고 큰 값끼리 곱함 print(max(a*b/c)) 'float' object is not iterable 이라는 오류가 발생한다. max 함수는 iterable(반복가능한) data에 적용되는 함수이기 때문에 두 개 이상의 값을 작성하거나, list와 같은 여러 데이터의 집합에 적용해야 한다. 최종 코드 a,b,c = map(int,input().split()) # 가장 작은 값을 나누고 큰 값끼리 곱함 print(max(int(a*b/c), int(a/b*c))) 둘 중에 더 큰 값을 출력하면 되니까 위와 같이 코드를 작성하면 된다. 굳이 큰 수 작은 수 비교를 하지 않아도 연산을 하고나서 큰 값을 판..

[백준/1343] 폴리오미노

2022.12.31·

PS/BOJ&Programmers

🐤 처음 짠 코드 - 실패 board = list(input().split('.')) ans = str() for i in range(len(board)): target = len(board[i]) if target % 2 !=0: # X의 개수가 홀수인 게 하나라도 존재하면 print(-1) exit() if board[i] == '': ans += '.' else: if target % 4 == 0: ans += 'AAAA' elif target % 2 == 0: ans += 'BB' # 여기서 그리디 else: 문제는 이해 했는데 그리디 작성에서 실패했다. 만약 길이가 6이나 10인 X문자열을 만난다면 먼저 'AAAA'를 먼저 채워주고, 남은 2자리에 'BB'를 채워준다는 로직을 생각했는데 실패 💻..

[백준/1712] 손익분기점

2022.12.31·

PS/BOJ&Programmers

🐤 처음 푼 코드 a,b,c = map(int, input().split()) n = 0 #가변 비용이 수익 보다 큰 경우 if b > c: print(-1) exit() while True: income = a+b*n cost = c*n n += 1 if income == cost: print(n) break 시간 초과가 떠서 입력 문젠가~ 했는데 제한시간이 0.35초인거다.(일단 로직도 100% 정답도 아님.) 이건 입력 문제가 아니고 수학적 트릭이나 알고리즘이 존재할 거라는 생각이 들었다. 📝 간단한 항등식 종이에 쓰면서 풀어서 대놓고 항등식을 적었고, n을 구하는 문제인 걸 알았음에도 불구하고 식을 정리하지 않은 나! 반성해야한다. 식을 정리해주면 간단한 코드로 빠른 시간 내에 구할 수 있다. 항..

[백준/2609] 최대공약수와 최소공배수| 유클리드 호제법 | 확장 유클리드 알고리즘

2022.12.27·

PS/BOJ&Programmers

유클리드호제법(최대공약수와 최소공배수)두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법이다. 호 호제법: '서로 나눈다'라는 뜻.일반적으로 최대공약수를 구할 때 소인수분해를 하고 두 수의 공통인 소인수를 곱한다. 이 방법은 수가 커질수록 소인수분해하기 어려워진다는 단점이 있다. 이를 극복하기 위한 방법이 유클리드 호제법이다. 그렇다면, 유클리드 알고리즘을 어떻게 구현할 수 있을까?바로 mod 연산(나머지 구하기 : %)을 반복하는 방법이다. why mod p?답이 큰 정수인 경우, Overflow 에러를 막기 위해서 문제에서 큰 소수(보통 1,000,000,007)로 나눈 나머지를 요구자연수 a, b에 대해 a를 b로 나눈 나머지는 r이다. (단 a>b) r에 대해, b를 r로 나눈 나머지 r'..

[백준/1929] 소수 구하기 | 에라토스테네스의 체

2022.12.26·

PS/BOJ&Programmers

개요백준 소수 문제들이 눈에 들어와서 푸는데,, 이 문제만 같은 방식으로 해결이 안되는 거다.서칭한 결과 소수 구하기 문제는 시간초과를 주의해야 하고, 소수 문제에서 시간초과를 피하기 위해 에라토스테네스의 체라는 개념을 알아두면 유용하다는 결론을 내렸다.(하지만 공부 결과 모든 소수 문제에 적용되는 것은 아니다..!) 에라토스테네스의 체에라토스테네스의 체란?어떤 수 n 이하의 모든 소수를 찾는 간단하고 빠른 방법으로, 자기 자신을 제외한 배수를 모두 차례대로 지우는 방식이다.더이상 지울 수 없을 때 남아있는 수들이 소수이다. 에라토스테네스의 시간복잡도는 O(n log(logn))이다. 에라토스네네스의 체는 '특정 범위 내의 소수'를 판정하는 데에만 효율적이다. 만약 주어진 수 하나가 소수인가?만을 따..

티스토리툴바