์ ์ฒด ๊ธ
-
[2019 ๋๊ณ ๋ชจ๊ฐ์ฝ] 1์ฐจ์ - ๊ฒฐ๊ณผ๋ชจ์ฌ์ ๊ฐ์ ์ฝ๋ฉ/2019 ๋๊ณ ๋ชจ๊ฐ์ฝ 2022. 3. 12. 23:54
์ฐ๊ฒฐ๋ฆฌ์คํธ 2ํ๋ ์๋ฃ๊ตฌ์กฐ ์์ ๊ฐ์์๋ฃ๋ฅผ ํตํด ๊ณต๋ถํ๊ณ ์ดํด๊ฐ ๋์ง์๋ ๋ถ๋ถ์ ์ ๋ฐฐ์๊ฒ ์ง๋ฌธํจ. 1. ์ด๋ก โ ๋ ธ๋์ ๋ํ ์ดํด๋ฅผ ๋ฐํ์ผ๋ก ๋ ธ๋ ํด๋์ค ์์ฑํ์๋ค. ์ฐ๊ฒฐ๋ฆฌ์คํธ์ ์ซ์ ์ ๋ ฌ์ ์ํ ๋ฉ์๋์ธ ์ฝ์ ๋ฉ์๋์ ์ญ์ ๋ฉ์๋ ์์ฑํ์๋ค. โ ์ฝ์ ๋ฉ์๋ ํฌ์ธํฐ๋ฅผ ํตํด ์ฐ๊ฒฐ๋ฆฌ์คํธ์ ๋ฐ์ดํฐ๋ฅผ ํ์ธํ์ฌ ์ฝ์ ํ ์์น๋ฅผ ์ฐพ๊ณ ์๋ก์ด ๋ ธ๋๋ฅผ ๋ง๋ค์ด ํฌ์ธํฐ๋ก ์ฐ๊ฒฐํ๋ค. ์ด๋ ๋ ธ๋์ ์์ฑ์๋ intํ data๊ฐ๊ณผ Nodeํ next๋ฅผ ์ ์ฅํ๋ค. ์ฝ์ ํ ์์น๊ฐ ๋งจ ์์ผ ๊ฒฝ์ฐ start๋ฅผ ๋ฐ๊ฟ์ฃผ์ด์ผํ๋ฏ๋ก ์กฐ๊ฑด๋ฌธ์ ๋ฐ๋ก ์์ฑํด ์ฃผ์ด์ผํ๋ค. โ ์ญ์ ๋ฉ์๋ ํฌ์ธํฐ๋ฅผ ํตํด ์ฐ๊ฒฐ๋ฆฌ์คํธ์ ์ญ์ ํ ๊ฐ ์์น๋ฅผ ์ฐพ์ ํฌ์ธํฐ ์ฐ๊ฒฐ์ ๋ฐ๊ฟ ์ญ์ ํ๋ค. start๋ฅผ ์ญ์ ํ ๊ฒฝ์ฐ์ ์ฐ๊ฒฐ๋ฆฌ์คํธ ์์ ์ญ์ ํ ๊ฐ์ด ์์๊ฒฝ์ฐ ์กฐ๊ฑด๋ฌธ์ ๋ฐ๋ก ์์ฑํด..
-
[2019 ๋๊ณ ๋ชจ๊ฐ์ฝ] 1์ฐจ์ - ์์๋ชจ์ฌ์ ๊ฐ์ ์ฝ๋ฉ/2019 ๋๊ณ ๋ชจ๊ฐ์ฝ 2022. 3. 12. 23:49
๋ชจ๊ฐ์ฝ ์ฃผ์ ๋ฅผ 2ํ๊ธฐ ๋ ๋ฐฐ์ฐ๊ฒ ๋ ์ ๊ณต ์ค ํ๋๋ฅผ ์ ํํ์ฌ ์ ํํ์ตํ๋ฉด ๋์์ด ๋ง์ด ๋ ๊ฒ ๊ฐ์์ต๋๋ค. 2ํ๋ 1ํ๊ธฐ ์ ๊ณต์ด๋ฉด์ ์๊ณ ์์ผ๋ฉด 2ํ๊ธฐ ๋ค๋ฅธ ์ ๊ณต๋ค์๋ ๋์์ด ๋ ์ ์๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ๊ณต๋ถํ๊ธฐ๋ก ํ์ต๋๋ค. ์ค๋์ ์๋ฃ๊ตฌ์กฐ ์ค ์ฐ๊ฒฐ๋ฆฌ์คํธ์ ๋ํด ๊ณต๋ถํ๊ธฐ๋ก ํ์์ต๋๋ค. ์ฐ๊ฒฐ๋ฆฌ์คํธ 1.์ด๋ก ๋ ธ๋ ๊ฐ๋ ํฌ์ธํฐ๋ฅผ ํตํ ์ฐ๊ฒฐ๋ฆฌ์คํธ ์์ฑ๊ณผ ์ฌ์ฉ โ 2.์ค์ต ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ์ฌ์ฉํ ํ๋ก๊ทธ๋จ ์์ฑ -๋ค์ํ ๋ฉ์๋ ์ฝ๋ ์์ฑํ๊ธฐ โ
-
[BOJ] 4948๋ฒAlgorithm/Baekjoon Online Judge 2022. 3. 12. 17:05
https://www.acmicpc.net/problem/4948 4948๋ฒ: ๋ฒ ๋ฅดํธ๋ ๊ณต์ค ๋ฒ ๋ฅดํธ๋ ๊ณต์ค์ ์์์ ์์ฐ์ n์ ๋ํ์ฌ, n๋ณด๋ค ํฌ๊ณ , 2n๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์๋ ์ ์ด๋ ํ๋ ์กด์ฌํ๋ค๋ ๋ด์ฉ์ ๋ด๊ณ ์๋ค. ์ด ๋ช ์ ๋ ์กฐ์ ํ ๋ฒ ๋ฅดํธ๋์ด 1845๋ ์ ์ถ์ธกํ๊ณ , ํํ๋ํฐ ์ฒด๋น์ผ www.acmicpc.net Python3 code1 - Fail def sosu(n): if n == 1: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True if __name__ == '__main__': while True: N = int(input()) if N == 0: break cnt = 0 for nu..
-
[BOJ] 11653๋ฒAlgorithm/Baekjoon Online Judge 2022. 3. 12. 14:28
https://www.acmicpc.net/problem/11653 11653๋ฒ: ์์ธ์๋ถํด ์ฒซ์งธ ์ค์ ์ ์ N (1 ≤ N ≤ 10,000,000)์ด ์ฃผ์ด์ง๋ค. www.acmicpc.net Python3 code 1 if __name__ == '__main__': N = int(input()) for i in range(2, int(N**0.5)+1): while N % i == 0: print(i) N //= i if N > 1: print(N) ์ ๋ ฅ๋ฐ์ N์ ๋ํด์ 2๋ถํฐ N์ ์ ๊ณฑ๊ทผ๊น์ง์ ์๋ค๋ก ๋๋๊ธฐ๋ฅผ ์งํํ๋ค. ๋๋๋ ์๋ ์ ๊ณฑ๊ทผ๋ณด๋ค ํด ์ ์๊ธฐ ๋๋ฌธ์ ๋ฐ๋ณต๋ฌธ์ ๋ฒ์๋ฅผ ์ ๊ณฑ๊ทผ๊น์ง๋ก ์ ํ์๋ค. ๋ง์ฝ N์ด i๋ก ๋๋์ด์ง๋ค๋ฉด ๋๋ ์ i๋ฅผ ์ถ๋ ฅํ๊ณ i๋ก ๋๋ ์ ์์ ๋๊น์ง ๋ฐ๋ณตํด์ ๋๋์๋ค. ๋ง์ง..
-
[BOJ] 2581๋ฒAlgorithm/Baekjoon Online Judge 2022. 3. 12. 13:43
https://www.acmicpc.net/problem/2581 2581๋ฒ: ์์ M์ด์ N์ดํ์ ์์ฐ์ ์ค ์์์ธ ๊ฒ์ ๋ชจ๋ ์ฐพ์ ์ฒซ์งธ ์ค์ ๊ทธ ํฉ์, ๋์งธ ์ค์ ๊ทธ ์ค ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค. ๋จ, M์ด์ N์ดํ์ ์์ฐ์ ์ค ์์๊ฐ ์์ ๊ฒฝ์ฐ๋ ์ฒซ์งธ ์ค์ -1์ ์ถ๋ ฅํ๋ค. www.acmicpc.net Python3 if __name__ == '__main__': M = int(input()) N = int(input()) prime = [] for number in range(M, N+1): is_sosu = 1 if number == 1: continue for i in range(2, number): if number % i == 0: is_sosu = 0 break if is_sosu: prime...